WordGPT

Is 2³² + 1 prime? Euler's 641

Exercise · Level 4 (Hard)

Show that 2322^{32} + 1 is not prime.

232+12^{32}+1

wordgptpro.com

Solution 1/2

  1. Two ways to write 641:

    641=5⋅27+1=54+24\begin{aligned}641&=5\cdot2^7+1\\&=5^4+2^4\end{aligned}
    (1)
  2. From the first, 5⋅27≡−1(mod641)5\cdot2^7\equiv-1\pmod{641}. Raise to the 4th power:

    54⋅228≡(−1)4=1(mod641)5^4\cdot2^{28}\equiv(-1)^4=1\pmod{641}
    (2)

wordgptpro.com

Solution 2/2

  1. From the second, 54≡−245^4\equiv-2^4. Put that into the line above:

    −24⋅228=−232≡1(mod641)-2^4\cdot2^{28}=-2^{32}\equiv1\pmod{641}
    (3)
  2. Add 2³² to both sides:

    232+1≡0(mod641)2^{32}+1\equiv0\pmod{641}
    (4)
  3. So 641 divides 2³² + 1, and the number is composite. In fact it equals 641×6 700 417641\times6\,700\,417, which disproved Fermat's guess that all numbers 22n2^{2^n} + 1 are prime.

Answer232+1=641×67004172^{32}+1=641\times 6700417

wordgptpro.com

Need a hint?

641 can be written in two ways: 5 · 2⁷ + 1 and 5⁴ + 2⁴. Work modulo 641.

2322^{32} + 1 = 4,294,967,297 = 641 × 6,700,417, so it is not prime.

How to work it out

  1. Two ways to write 641:

    641=5⋅27+1=54+24\begin{aligned}641&=5\cdot2^7+1\\&=5^4+2^4\end{aligned}
    (1)
  2. From the first, 5⋅27≡−1(mod641)5\cdot2^7\equiv-1\pmod{641}. Raise to the 4th power:

    54⋅228≡(−1)4=1(mod641)5^4\cdot2^{28}\equiv(-1)^4=1\pmod{641}
    (2)
  3. From the second, 54≡−245^4\equiv-2^4. Put that into the line above:

    −24⋅228=−232≡1(mod641)-2^4\cdot2^{28}=-2^{32}\equiv1\pmod{641}
    (3)
  4. Add 2³² to both sides:

    232+1≡0(mod641)2^{32}+1\equiv0\pmod{641}
    (4)
  5. So 641 divides 2³² + 1, and the number is composite. In fact it equals 641×6 700 417641\times6\,700\,417, which disproved Fermat's guess that all numbers 22n2^{2^n} + 1 are prime.

LaTeX source of the formulas on this page
\[ 2^{32}+1=641\times 6700417 \]
\[ 641=5\cdot2^7+1=5^4+2^4 \]
\[ 5^4\cdot2^{28}\equiv(-1)^4=1\pmod{641} \]
\[ -2^4\cdot2^{28}=-2^{32}\equiv1\pmod{641} \]
\[ 2^{32}+1\equiv0\pmod{641} \]

Questions

What is the answer to: Is 2³² + 1 prime? Euler's 641?

2322^{32} + 1 = 4,294,967,297 = 641 × 6,700,417, so it is not prime.

What is the key idea?

Two different expressions for 641 force 2322^{32} ≡ −1 modulo 641.

Is there a hint?

641 can be written in two ways: 5 · 2⁷ + 1 and 5⁴ + 2⁴. Work modulo 641.

Related problems

More number theory problems

    Is 2³² + 1 prime? Euler's 641: answer and solution | WordGPT