6
$\begingroup$

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

2 Answers 2

16

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.

  • 0
    Thanks so much! This is very easy to understand.2012-05-25
  • 2
    after I got that $64.4$ means $64\cdot 4$, I agree: +1 nice answer!2012-05-25
  • 1
    "If we notice that...". I can't imagine many people noticing such things. Brilliant! (+1).2012-05-25
  • 0
    @Ragib I wouldn't be able to come up with that solution. As I write in the answer, I saw it in Hardy-Wright.2012-05-25
  • 0
    @MartinSleziak Ah, I didn't know the trick came from them. I remember it from one of Nathanson's books.2012-05-25
  • 0
    @Peter Tamaroff Thanks for editing the answer and replacing $a.b$ by $a\cdot b$. I know that more people here are used to the later convention, but I was too lazy to rewrite that. If you have a look at the page 18 from Hardy-Wright - link is in my answer - they also use $a.b$, so I thought it's not that bad if I leave it that way. But after your edit the answer is definitely better readable for more people here. Comma vs. $\cdot$ as decimal separator was discussed at MSE a few times, e.g. [here](http://math.stackexchange.com/questions/86823/continuous-functions-on-omega-1#comment205169_86850).2012-06-09
  • 0
    Unfortunately this not generalize to any known method for larger Fermat numbers , so the Q of which regular polygons are constructible with unmarked ruler and a drawing compass is still not completely answered.2017-07-16
6

$\rm\begin{eqnarray} \bmod\, 641\!:\,\ {-}1 &\equiv&\rm\:\, 5\,\cdot\, 2^{\large 7}\\[.2em] \rm above^{\large 4}\ \Rightarrow\:\ \ 1 &\equiv&\rm\!\! \underbrace{5^{\large 4}\!}_{\Large\!\!\!\!\! \equiv\,\,-2^{\Large 4}}\:\! 2^{\large 28}\equiv\, -2^{\large 32}\ \ \ {\bf QED}\end{eqnarray}$

  • 2
    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.)2014-07-24
  • 1
    This solution is the same as Martin Sleziak's $2$nd (second) solution, except it uses different notation. After looking at his edit history, his solution was posted about $2$ weeks before yours.2017-09-03
  • 0
    @user236182 We'll have to disagree about "the same". In any case, I've posted this numerous places over the years, going back to ancient sci.math days. It is my condensed version of a well-known classic proof that appears in various forms in some elementary number theory textbooks.2017-09-03