Nimbers

FERMAT'S TWO-SQUARES THEOREM

\[p=a^{2}+b^{2}\]

$$p\equiv 1 \pmod 4$$

\[p=a^{2}+b^{2}\ \ (\text{with }p\ \text{prime})\iff p=2\ \text{or}\ p\equiv 1 \pmod 4\]

Fermat's theorem on sums of two squares settles exactly which primes are a sum of two squares. An odd prime $p$ can be written $p=a^{2}+b^{2}$ if and only if $p\equiv 1 \pmod 4$, and when it can, the representation is unique (up to order and signs). So $5=1^{2}+2^{2}$, $13=2^{2}+3^{2}$, $17=1^{2}+4^{2}$, while $3,7,11,19\equiv 3 \pmod 4$ admit no such form. The dividing line is precisely the non-principal Dirichlet character modulo $4$ : the value $\chi _4(p)=+1$ selects the primes that split as two squares, $\chi _4(p)=-1$ those that do not. Zagier famously compressed the proof into a single sentence using an involution on triples.

A002144 Pythagorean primes : the primes $p\equiv 1 \pmod 4$ that split as $a^2+b^2$.

5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181,193,197

A002144

A002331 The smaller leg $a$ in $p=a^{2}+b^{2}$ ($a<b$).

1,2,1,2,1,4,2,5,3,5,4,1,3,7,7,7,6,2,9,7,1

A002331

A002330 The larger leg $b$ in $p=a^{2}+b^{2}$ ($a<b$).

2,3,4,5,6,5,7,6,8,8,9,10,10,8,11,10,11,13,10,12,14

A002330


# Fermat : an odd prime is a sum of two squares  <=>  p = 1 mod 4
def two_squares(p):
    for a in range(isqrt(p)+1):
        b2 = p - a*a
        if b2 < 0: break
        b = isqrt(b2)
        if b*b == b2 and a <= b:
            return (a, b)
    return None

for p in primes(4, 60):
    print p, p % 4, two_squares(p)
# 5 (1,2)  13 (2,3)  17 (1,4)  29 (2,5) ... while 7,11,19,23 give None

# The representation, when it exists, is unique
print two_squares(101)      # (1, 10)  ->  1 + 100 = 101

THE OTHER HALF

The primes that are not a sum of two squares are exactly those with $p\equiv 3 \pmod 4$. They form the complementary family, and they are precisely the primes that stay inert where the $4n+1$ primes split — the arithmetic of the Gaussian integers $\mathbb{Z}[i]$ reading off the same $\chi _4$ dichotomy. Here $-1$ is a quadratic residue mod $p$ exactly when $p\equiv 1 \pmod 4$, which is the algebraic heart of why the two-square representation exists.

A002145 The primes $p\equiv 3 \pmod 4$ : never a sum of two squares.

3,7,11,19,23,31,43,47,59,67,71,79,83,103,107,127,131,139,151,163,167

A002145


# -1 is a quadratic residue mod p  <=>  p = 1 mod 4  (the algebraic key)
for p in primes(3, 40):
    print p, p % 4, kronecker_symbol(-1, p)
# p=5 ->  1   (residue, splits)      p=3 -> -1 (non-residue, inert)
# p=13 ->  1                          p=7 -> -1

A002144 Pythagorean primes : the primes \(p\equiv 1 \pmod 4\) that split as \(a^2+b^2\).

A002331 The smaller leg \(a\) in \(p=a^{2}+b^{2}\) (\(a<b\)).

A002330 The larger leg \(b\) in \(p=a^{2}+b^{2}\) (\(a<b\)).

A002145 The primes \(p\equiv 3 \pmod 4\) : never a sum of two squares.