Euler > Fermat

Consider $a$ as an element of the multiplicative group $\mathbb{Z}_p^\times$ of nonzero integers modulo $p$ . We are told that $a^{32} = -1$ in $\mathbb{Z}_p^\times$ , and hence the order of $a \in \mathbb{Z}_p^\times$ is $64$ . Thus $64$ must divide the order $p-1$ of the group $\mathbb{Z}_p^\times$ , and hence $p \equiv 1 \pmod{64}$ as required.

Assume a prime $p$ is not a factor of an even number $a$ but is a factor of $a^2 + 1$ . Then $p$ must odd and in the form of either $4k + 1$ or $4k + 3$ for some integer $k$ . Assume $p = 4k + 3$ for some integer $k$ . Then by Fermat's Little Theorem, $p$ is a factor of $a^{p - 1} - 1 = a^{4k + 3 - 1} - 1 = a^{4k + 2} - 1$ . But since $p$ is a factor of $a^2 + 1$ , it is also a factor of $(a^2 + 1)(a^{4k} - a^{4k - 2} + a^{4k - 4} - ... + a^4 - a^2 + 1) = a^{4k + 2} + 1$ . This means that $p$ is a factor of $(a^{4k + 2} + 1) - (a^{4k + 2} - 1) = 2$ , which contradicts the assumption that $p$ is not a factor of an even number. Therefore, we reject the assumption that $p = 4k + 3$ for some integer $k$ , which means $p = 4k + 1$ for some integer $k$ . In summary,

If a prime $p$ is not a factor of an even number $a$ but is a factor of $a^2 + 1$ , then $p = 4k + 1$ for some integer $k$ .

Similarly, assume a prime $p$ is not a factor of an even number $a$ but is a factor of $a^4 + 1$ . Since $a^4 + 1 = (a^2)^2 + 1$ , by the theorem above $p$ in the form $4k + 1$ for some integer $k$ , or in the form of either $8k + 1$ or $8k + 5$ for some integer $k$ . Assume $p = 8k + 5$ for some integer $k$ . Then by Fermat's Little Theorem, $p$ is a factor of $a^{p - 1} - 1 = a^{8k + 5 - 1} - 1 = a^{8k + 4} - 1$ . But since $p$ is a factor of $a^4 + 1$ , it is also a factor of $(a^4 + 1)(a^{8k} - a^{8k - 4} + a^{8k - 8} - ... + a^8 - a^4 + 1) = a^{8k + 4} + 1$ . This means that $p$ is a factor of $(a^{8k + 4} + 1) - (a^{8k + 4} - 1) = 2$ , which contradicts the assumption that $p$ is not a factor of an even number. Therefore, we reject the assumption that $p = 8k + 5$ for some integer $k$ , which means $p = 8k + 1$ for some integer $k$ . In summary,

If a prime $p$ is not a factor of an even number $a$ but is a factor of $a^4 + 1$ , then $p = 8k + 1$ for some integer $k$ .

Each similar argument introduces a new theorem that increases by powers of two, so that for any $n > 1$ we can conclude

If a prime $p$ is not a factor of an even number $a$ but is a factor of $a^{2^n} + 1$ , then $p = 2^{n + 1}k + 1$ for some integer $k$ .

Therefore, when $n = 5$ ,

If a prime $p$ is not a factor of an even number $a$ but is a factor of $a^{32} + 1$ , then $p = 64k + 1$ for some integer $k$ .

So the statement in the problem is true .

---

Note: Euler discovered and used this theorem to quickly find factors of $2^{2^5} + 1$ (specifically $641$ and $6700417$ ), which disproved Fermat’s conjecture that all numbers in the form of $2^{2^n} + 1$ are prime numbers.