Is 2³² + 1 prime? Euler's 641
Need a hint?
641 can be written in two ways: 5 · 2⁷ + 1 and 5⁴ + 2⁴. Work modulo 641.
+ 1 = 4,294,967,297 = 641 × 6,700,417, so it is not prime.
How to work it out
Two ways to write 641:
(1)From the first, . Raise to the 4th power:
(2)From the second, . Put that into the line above:
(3)Add 2³² to both sides:
(4)So 641 divides 2³² + 1, and the number is composite. In fact it equals , which disproved Fermat's guess that all numbers + 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?
+ 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 ≡ −1 modulo 641.
Is there a hint?
641 can be written in two ways: 5 · 2⁷ + 1 and 5⁴ + 2⁴. Work modulo 641.