2
$\begingroup$

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.$

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Kareem May 18 '16 at 10:23
  • 1
    $\begingroup$ @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? $\endgroup$ – Kareem May 18 '16 at 10:35
  • 2
    $\begingroup$ 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! $\endgroup$ – gammatester May 18 '16 at 10:43
  • 1
    $\begingroup$ @almagest It takes far les than $5$ seconds to factor $2^{32}+1$ with a computer. $\endgroup$ – Peter May 18 '16 at 11:00
  • 2
    $\begingroup$ @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. $\endgroup$ – almagest May 18 '16 at 11:02
3
$\begingroup$

Computational. But simpler.

$$2^{32} + 1 \equiv (2^{16})^2 + 1 \equiv (65536)^2 + 1$$

$$\equiv (154)^2 + 1 \equiv 23717 \equiv 0 \pmod{641}$$

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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