Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Fermat two-squares: no bad prime factors implies a sum of two squares

Proved
no_bad_primes_two_squares

by moona3k · Oct 4, 2026 · Mathlib 0df444a (Lean v4.33.1)

additive-number-theoryfermatnumber-theory

Fermat's two-squares theorem (backward direction). If every prime factor of nnn is not congruent to 3(mod4)3 \pmod{4}3(mod4), then nnn is a sum of two perfect squares.

(∀p∣n: p prime∧p≢3(mod4))  ⟹  ∃a,b∈N: n=a2+b2.\left(\forall p \mid n:\ p \text{ prime} \wedge p \not\equiv 3 \pmod{4}\right) \implies \exists a, b \in \mathbb{N}:\ n = a^2 + b^2.(∀p∣n: p prime∧p≡3(mod4))⟹∃a,b∈N: n=a2+b2.

This is the "easy" half of Fermat's full characterization (the other half: if n=a2+b2n = a^2 + b^2n=a2+b2, then every prime p≡3(mod4)p \equiv 3 \pmod{4}p≡3(mod4) appears to an even power). The proof combines two facts:

  1. Every prime ppp with p≢3(mod4)p \not\equiv 3 \pmod{4}p≡3(mod4) is a sum of two squares (Fermat's Christmas theorem, Mathlib's Nat.Prime.sq_add_sq).
  2. The Brahmagupta–Fibonacci identity: products of sums of two squares are sums of two squares, (x2+y2)(u2+v2)=(xu+yv)2+(xv−yu)2(x^2 + y^2)(u^2 + v^2) = (xu + yv)^2 + (xv - yu)^2(x2+y2)(u2+v2)=(xu+yv)2+(xv−yu)2 (Mathlib's Nat.sq_add_sq_mul).

The proof is by strong induction on nnn, extracting one prime factor at a time (via Nat.minFac) and combining with the identity.

Formalization Note The base cases n=0n = 0n=0 and n=1n = 1n=1 are handled by 0=02+020 = 0^2 + 0^20=02+02 and 1=12+021 = 1^2 + 0^21=12+02.

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 sorry
Source
P. de Fermat (1640, letter to Mersenne); see also Mathlib.NumberTheory.SumTwoSquares, theorems Nat.Prime.sq_add_sq and Nat.sq_add_sq_mul

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me