structural:scholar_edition, quality:corruption
Primes that are sums of two squares

The difficult implication in Fermat's theorem on sums of two squares can be proven using Minkowski's bound on the shortest vector.

Theorem: Every prime with p ≡ 1 mod 4 {\textstyle p\equiv 1\mod 4} can be written as a sum of two squares.

Since 4 | p − 1 {\textstyle 4\,|\,p-1} and a a is a quadratic residue modulo a prime p {\textstyle p} if and only if a p − 1 2 = 1 (mod p) a^{\frac {p-1}{2}}=1~({\text{mod}}~p) (Euler's Criterion) there is a square root of − 1 {\textstyle -1} in Z / p Z {\textstyle \mathbb {Z} /p\mathbb {Z} }; choose one and call one representative in Z {\textstyle \mathbb {Z} } for it j {\textstyle j}. Consider the lattice L {\textstyle L} defined by the vectors (1, j), (0, p) {\textstyle (1,j),(0,p)}, and let B {\textstyle B} denote the associated matrix. The determinant of this lattice is p {\textstyle p}, whence Minkowski's bound tells us that there is a nonzero x = (x 1, x 2) ∈ Z 2 {\textstyle x=(x_{1},x_{2})\in \mathbb {Z} ^{2}} with 0 < ‖ B x ‖ 2 2 < 2 p {\textstyle 0<\|Bx\|_{2}^{2}<2p}. We have ‖ B x ‖ 2 = ‖ (x 1, j x 1 + p x 2) ‖ 2 = x 1 2 + (j x 1 + p x 2) 2 {\textstyle \|Bx\|^{2}=\|(x_{1},jx_{1}+px_{2})\|^{2}=x_{1}^{2}+(jx_{1}+px_{2})^{2}} and we define the integers a = x 1, b = (j x 1 + p x 2) {\textstyle a=x_{1},b=(jx_{1}+px_{2})}. Minkowski's bound tells us that 0 < a 2 + b 2 < 2 p {\textstyle 0<a^{2}+b^{2}<2p}, and simple modular arithmetic shows that a 2 + b 2 = x 1 2 + (j x 1 + p x 2) 2 = 0 mod p {\textstyle a^{2}+b^{2}=x_{1}^{2}+(jx_{1}+px_{2})^{2}=0\mod p}, and thus we conclude that a 2 + b 2 = p {\textstyle a^{2}+b^{2}=p}. Q.E.D.

Additionally, the lattice perspective gives a computationally efficient approach to Fermat's theorem on sums of squares: