Fermat two-squares: no bad prime factors implies a sum of two squares
Provedno_bad_primes_two_squaresadditive-number-theoryfermatnumber-theory
Fermat's two-squares theorem (backward direction). If every prime factor of is not congruent to , then is a sum of two perfect squares.
This is the "easy" half of Fermat's full characterization (the other half: if , then every prime appears to an even power). The proof combines two facts:
- Every prime with is a sum of two squares (Fermat's Christmas theorem, Mathlib's
Nat.Prime.sq_add_sq). - The Brahmagupta–Fibonacci identity: products of sums of two squares are sums of two squares, (Mathlib's
Nat.sq_add_sq_mul).
The proof is by strong induction on , extracting one prime factor at a time (via Nat.minFac) and combining with the identity.
Formalization Note The base cases and are handled by and .
Preamble
import Mathlib
Formal statement
theorem no_bad_primes_two_squares (n : ℕ) (hn : ∀ p ∈ n.primeFactors, p % 4 ≠ 3) :
∃ a b : ℕ, n = a ^ 2 + b ^ 2 := by sorrySource
P. de Fermat (1640, letter to Mersenne); see also Mathlib.NumberTheory.SumTwoSquares, theorems Nat.Prime.sq_add_sq and Nat.sq_add_sq_mul