To show that Fermat number $F_{5}$ is divisible by $641$.

Solution 1:

If you know at least a few basic facts about congruences, it's not difficult to do this by hand, e.g. as follows:

$\newcommand{\kong}[3]{{#1}\equiv{#2}\pmod{#3}}$ $\kong{2^8}{256}{641}$

$2^{16} \equiv 256^2= 64\cdot4\cdot256 =1024\cdot64=102\cdot640+256 \equiv \kong{256-102}{154}{641}$

$2^{32} \equiv 154^2 = 14^2\cdot11^2 = 196\cdot121 = (3\cdot64+4)(2\cdot64-7)= 6\cdot64^2+8\cdot64-21\cdot64-28=(384+8-21)\cdot64-28 = 371\cdot64-28 = 37\cdot640+64-28\equiv \kong{-37+36}{-1}{641}$

The last line means that $641\mid F_5=2^{32}+1$.

We have just used $\kong{640}{-1}{641}$ a few times.


Hardy and Wright give in their book a different argument, see p.18.

If we notice that $$641=5^4+2^4=5\cdot 2^7+1$$ then we have that $$641\mid 5^4\cdot2^{28}+2^{32}$$ (we multiplied the first expression by $2^{28}$) and we also have $$641\mid 5^4\cdot2^{28}-1$$ if we use $x+1\mid x^4-1$ for $x=5\cdot2^7$.

If we subtract the above numbers, we get $$641\mid 2^{32}+1=F_5$$

They attribute this proof to Coxeter, see p.27.

Solution 2:

$\!\!\bmod\, 641\!:\,\ {-}1\, \equiv\:\, 5\,\cdot\, 2^{\large 7},\,$ so by Power & Product Rules
$\rm above^{\large 4}\, \Longrightarrow\ 1^{\phantom{|^{|^|}}}\!\! \equiv \underbrace{\color{#c00}{5^{\large 4}}\!}_{\Large\!\!\!\!\! \color{#c00}{\equiv\,-2^{\Large 4}}}\:\! 2^{\large 28}\equiv\, -2^{\large 32}\ \ \ \ {\small\bf QED}$