Proving the divisibility of large numbers without making large calculations How would you you show that $2^{32}+1$ is divisible by $641$ without making large calculations?
 A: Note that $641=5^4+2^4$. So
$$2^{32}=2^4\cdot 2^{28}\equiv -5^4\cdot 2^{28}=-(5\cdot 2^7)^4\equiv -(-1)^4=-1 \;(\mathrm{mod}\; 641).$$
A: Here's the way I like to present this classical proof:
$\rm\begin{eqnarray}\! mod\ 641\!:\,\  {-}1 &\equiv&\rm\: 5\,\ 2^7\\
\rm above^4\  \Rightarrow\:\ \ 1 &\equiv&\rm\!\! \underbrace{5^4\!}_{\Large\!\!\!\!\!\! \equiv\,\,-2^4}\:\! 2^{28}\equiv\, -2^{32}\ \Rightarrow\ \ 641\mid 1+2^{32}\end{eqnarray}$
Remark $\ $ Rewriting into powers of $2$ often proves handy, e.g. below from a recent question.
$\begin{eqnarray} 
{\rm mod}\ 47\!:\quad && 1+ \color{#c00}{7^8} +\, 8^9 +\ \color{#0a0}{9^7}\\
\equiv && 1+  \color{#c00}{2^4} + 2^{27} + \color{#0a0}{7\cdot 7^6\cdot 8^7}\quad {\rm by}\ \ \color{#0a0}{9\equiv 7\cdot 8},\ \ \color{#c00}{7^2\equiv 2}\\
\equiv&& 1+ 2^4 + 2^{27} + 7\cdot \color{#c00}{2^3}\cdot 2^{21}\\
\equiv&& 1+ 2^4 + 2^{4} +\ 7\cdot 2\,\equiv\, 0\quad {\rm by}\ \ \color{#c00}2^{23}\equiv (\color{#c00}{7^2})^{23}\equiv 7^{46}\equiv 1,\ \ \rm by\ little \ Fermat\\
\end{eqnarray}$
