# How did Euler stumble on this proof?

Euler proved $n=641$ divides $2^{32}+1$ by noting $n=5^4+2^4=5\times 2^7+1$ so $$2^{32}\equiv-5^4\times 2^{28}=-(5\times 2^7)^4\equiv-1\,(\text{mod}\, n).$$How did he happen upon this realisation? One possibility is he tried long division until he saw $641|2^{32}+1$, then saw if $641$ could be expressed in terms of powers of $2$ in a way that explains why this would be so. Another is that he realised he could prove $2^{32}+1$ is composite if he found an equation of the right form, then solved some Diophantine equations. Is it known what happened historically?

• Euler's paper: eulerarchive.maa.org/docs/originals/E026.pdf -- according to the summary at the Euler Archive, the paper gives no hint how the factorization was discovered. – Michael E2 Dec 3 '17 at 18:38
• Here is one answer: maa.org/sites/default/files/pdf/editorial/euler/…; See E134, p. 9 -- I felt a heuristic might be that if $p \mathrel{|} 2^{2^5}+1$, then since $2^{2^6} \equiv 1 \ (p)$, one might first look for $p$ for which $2^6 \mathrel{|} p - 1$. Euler proved the equivalent in a later paper and used it to explain how he found 641. – Michael E2 Dec 3 '17 at 19:44
• Basically, he was very smart and all sorts of "intuitions" came to him that would not come to us mere mortals. – Carl Witthoft Dec 5 '17 at 14:23
• @CarlWitthoft I think MichaelE2's second comment provides a deeper explanation than that. – J.G. Dec 5 '17 at 14:31