Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

up vote 13 down vote accepted

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.

share|improve this answer
    
Thanks so much! This is very easy to understand. –  Kns May 25 '12 at 13:55
2  
after I got that $64.4$ means $64\cdot 4$, I agree: +1 nice answer! –  draks ... May 25 '12 at 14:50
1  
"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}$

share|improve this answer
    
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 at 4:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.