Primes And Perfect Squares

Relevant wiki: Quadratic Residues - Problem Solving

If $p \equiv 1 \pmod{4}$ , then $-1$ is a quadratic residue modulo $p$ , therefore there is $m \in \mathbf Z$ such that $m^2 + 1$ is divisible by $p$ . This shows that for $p = 29, 37, 41$ , the pair $(m, 1)$ will work. If $p = 2$ , then the obvious choice $(1, 1)$ works.

To see that no prime $p \equiv 3 \pmod {4}$ can divide $a^2 + b^2$ , note that if $a$ and $b$ are coprime, then at least one of them is nonzero modulo $p$ . Assume that it is $b$ without loss of generality, then we may multiply by the square of its inverse to get that $(a b^{-1})^2 + 1 \equiv 0 \pmod{p}$ so that $-1$ is a quadratic residue modulo $p$ . This is only possible if $p \equiv 1 \pmod{4}$ or $p = 2$ , contradiction. Therefore, the primes $23, 31$ can never divide $a^2 + b^2$ .

Alternatively, note that the ring $\mathbf Z[i]$ is factorial and primes that are 3 modulo 4 are inert, therefore $a^2 + b^2 = (a + bi)(a - bi)$ implies that one, and therefore both, of the factors on the right hand side are divisible by $p$ . This gives that both $a, b$ are divisible by $p$ , contradicting coprimality.