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

How can I show that Fermat number $F_{5}=2^{2^5}+1$ is divisible by $641$.

-

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.

-
Thanks so much! This is very easy to understand. –  Kns May 25 '12 at 13:55
after I got that $64.4$ means $64\cdot 4$, I agree: +1 nice answer! –  draks ... May 25 '12 at 14:50
"If we notice that...". I can't imagine many people noticing such things. Brilliant! (+1). –  Ragib Zaman May 25 '12 at 14:55
@Ragib I wouldn't be able to come up with that solution. As I write in the answer, I saw it in Hardy-Wright. –  Martin Sleziak May 25 '12 at 14:59
@MartinSleziak Ah, I didn't know the trick came from them. I remember it from one of Nathanson's books. –  Andres Caicedo May 25 '12 at 15:44

$\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}$

-
Very nice. To complement this clever answer, here's the un-clever(est) answer. $2^{32}$ has, in decimal notation, only 10 digits. You can multiply it out by hand (if you happen to know that $2^{16}=65536$, just square that); add one; divide by 641. (I know this is less fun than doing mathematics, but it's no worse than calculating my taxes.) –  Andreas Blass Jul 24 '14 at 4:16