# Alternative proof of Euler's result that $641$ divides $2^{32} + 1$

I am looking for an alternative proof of Euler's result that $641$ divides $2^{32} + 1$. I've seen a solution so far, understood the solution, but unfortunately I don't know how to think in order to approach such a solution, so I'd like to see another solution easy to approach.

Here's the solution I have so far:

Observe that $641 = 2^7*5 + 1 = 2^4+5^4.$ Hence $2^7*5 \equiv -1 \space mod \space641.$

Now, $2^7*5 \equiv -1 \pmod{641}$ yields $5^4*2^{28}=(5*2^7)^4 \equiv 1 \space \pmod{641}.$ This last congruence and $5^4 \equiv -2^4 \pmod{641}$ yields $-2^4*2^{28} \equiv 1 \pmod{641}$, which means that $641$ divides $2^{32}+1.$

• Oh I forgot something, the reason why I don't like this proof is that I didn't know why $641 = 2^7*5+1 \space = \space 2^4+5^4,\space$ This step was hard for me to approach, I didn't know that 641 equals specifically those 2 expressions above and the solution is entirely based on them. – Kareem May 18 '16 at 10:23
• @almagest I know it was easy to proof it by dividing or by a calculator, the point wasn't to divide it, the point was to learn how to prove it without dividing, the problem with the proof was that when I was thinking, I did that generally, tried many ways to proof it but failed, and was annoyed when seeing the solution, made me feel like it's tailored specifically for this problem and I was wondering .. isn't there any other better and general proof? – Kareem May 18 '16 at 10:35
• Since $2^{32}+1$ is the Fermat number $F_5$ the possible factors are $k 2^{5+2}+1$. So the smallest possible factors are $129, 257, 385, 513, 641, \dots$ Bingo! – gammatester May 18 '16 at 10:43
• @almagest It takes far les than $5$ seconds to factor $2^{32}+1$ with a computer. – Peter May 18 '16 at 11:00
• @Peter Obviously it takes the computer far less than 5 seconds. But you have to get to the computer, find the right program and enter the data. 5 seconds is not bad for that. – almagest May 18 '16 at 11:02

$$2^{32} + 1 \equiv (2^{16})^2 + 1 \equiv (65536)^2 + 1$$
$$\equiv (154)^2 + 1 \equiv 23717 \equiv 0 \pmod{641}$$
In the prime field $\mathbb F_{641}$ we have $2^{640}=(2^{32})^{20}=1\Rightarrow2^{32}=\pm 1$
Besides $2^{32}-1=(2^{16}+1)(2^{16}-1)=65537\cdot65535=155\cdot153=639\ne 0$
Hence $2^{32}+1=0\in \mathbb F_{641}\iff 641 \text{ divides}\space 2^{32}+1$