Sum of two squares

Fermat proved that an odd prime \(p\) is a sum of two squares if and only if \(p \equiv 1 \pmod{4}\). For a general integer, the identity \((a^2+b^2)(c^2+d^2) = (ac-bd)^2 + (ad+bc)^2\) shows that a product of sums of two squares is again a sum of two squares, and the complete criterion requires every prime \(q \equiv 3 \pmod{4}\) to appear with even exponent.

Take \(n = 45 = 3^2 \cdot 5\). The prime 3 appears with even exponent and \(5 \equiv 1 \pmod{4}\), so \(45\) is a sum of two squares; in fact \(45 = 3^2 + 6^2\).

A typical mistake is thinking that \(n \equiv 1 \pmod{4}\) is enough. For example, \(21 \equiv 1 \pmod{4}\), but \(21 = 3 \cdot 7\) has two primes \(\equiv 3 \pmod{4}\) with odd exponent, so it is not a sum of two squares.