integer_primitive_ray_coeff_coprime
Let u,v,x be integer-valued functions, with v primitive in the sense that every common natural divisor of its coordinates divides one. If gcd(a,b) is coprime to D and D*x=a*u+b*v coordinatewise, then a is coprime to D.
Statement
theorem integer_primitive_ray_coeff_coprime {ι : Type*} (u v x : ι → ℤ) (hprimv : ∀ d : ℕ, (∀ i, (d : ℤ) ∣ v i) → d ∣ 1) (D a b : ℕ) (htr : Nat.Coprime (Nat.gcd a b) D) (hrel : ∀ i, (D : ℤ) * x i = (a : ℤ) * u i + (b : ℤ) * v i) : Nat.Coprime a D
- Source
- Helper for OP-197 / arXiv:2610.16562 Conjecture1, continuing the already verified two_ray_integer_atom_coeff_sum_le from deep session1. This closes primitive-ray denominator normalization and weighted length bookkeeping, not extraction of the two circuit rays or the box conjecture. No research advance claimed.
- Verified
- 28 Oct 2026
- Axioms
Quot.soundpropext- Used by 1
- two_ray_integer_atom_coeff_sum_le_primitiveFor an additive subgroup of integer-valued functions, let x have no proper nonzero nonnegative subgroup subvector. Given nonnegative…
The proof, explained
To prove that a and D are coprime, we consider g = gcd(a, D). By associativity and commutativity of the gcd, gcd(b, g) = gcd(gcd(a, b), D) = 1, so b and g are coprime. Since g divides both D and a, the relation D * x(i) = a * u(i) + b * v(i) implies that g divides b * v(i) for all coordinates i, and coprimality of b and g forces g to divide each v(i). Finally, the primitivity assumption on v implies g ∣ 1, whence g = 1 and a is coprime to D.
Setting g = gcd(a, D), the numbers b and g are coprime.
We define g = gcd(a, D). To show that b and g are coprime, it suffices by Nat.coprime_iff_gcd_eq_one.mpr to show gcd(b, g) = 1. Expanding g and applying the associativity and commutativity of the gcd (Nat.gcd_assoc and Nat.gcd_comm), gcd(b, gcd(a, D)) rewrites to gcd(gcd(a, b), D). The coprimality hypothesis htr gives gcd(gcd(a, b), D) = 1, so gcd(b, g) = 1.
uses
Nat.coprime_iff_gcd_eq_one.mpr,Nat.gcd_assoc,Nat.gcd_commlet g := Nat.gcd a D have hbg : Nat.Coprime b g := by apply Nat.coprime_iff_gcd_eq_one.mpr dsimp [g] rw [← Nat.gcd_assoc, Nat.gcd_comm b a] exact htr.gcd_eq_one
As integers, g divides both D and a.
By definition of greatest common divisor, g divides D and a in ℕ (Nat.gcd_dvd_right and Nat.gcd_dvd_left). Casting to ℤ gives (g : ℤ) ∣ (D : ℤ) and (g : ℤ) ∣ (a : ℤ).
uses
Nat.gcd_dvd_right,Nat.gcd_dvd_lefthave hgD : (g : ℤ) ∣ (D : ℤ) := by exact_mod_cast Nat.gcd_dvd_right a D have hga : (g : ℤ) ∣ (a : ℤ) := by exact_mod_cast Nat.gcd_dvd_left a D
For every coordinate i, (g : ℤ) divides v(i).
Fix an index i. Since g divides D and a, it divides the difference D * x(i) - a * u(i) using dvd_sub and dvd_mul_of_dvd_left. Rewriting D * x(i) using the relation hrel as a * u(i) + b * v(i), the a * u(i) terms cancel via add_sub_cancel_left, showing that g divides b * v(i). Next, since b and g are coprime, their integer gcd is 1 (Int.gcd). Euclid's lemma for integers (Int.dvd_of_dvd_mul_right_of_gcd_one) then implies that g divides v(i).
uses
dvd_sub,dvd_mul_of_dvd_left,add_sub_cancel_left,Int.dvd_of_dvd_mul_right_of_gcd_one,Int.gcd,Nat.gcd_commhave hvdiv (i : ι) : (g : ℤ) ∣ v i := by have hp : (g : ℤ) ∣ (b : ℤ) * v i := by have hh := dvd_sub (dvd_mul_of_dvd_left hgD (x i)) (dvd_mul_of_dvd_left hga (u i)) rw [hrel] at hh simpa only [add_sub_cancel_left] using hh apply Int.dvd_of_dvd_mul_right_of_gcd_one hp simpa [Int.gcd, Nat.gcd_comm] using hbg.gcd_eq_one
a and D are coprime.
Because g divides each coordinate v(i), the primitivity hypothesis hprimv implies that g divides 1. A natural number dividing 1 must be 1 (Nat.dvd_one.mp). Since g = gcd(a, D) = 1, Nat.coprime_iff_gcd_eq_one.mpr concludes that a and D are coprime.
uses
Nat.coprime_iff_gcd_eq_one.mpr,Nat.dvd_one.mpexact Nat.coprime_iff_gcd_eq_one.mpr (Nat.dvd_one.mp (hprimv g hvdiv))
Nat.coprime_iff_gcd_eq_one.mpr- Two natural numbers are coprime if their greatest common divisor is 1.
Nat.gcd_assoc- The greatest common divisor of natural numbers is associative: gcd(gcd(m, n), k) = gcd(m, gcd(n, k)).
Nat.gcd_comm- The greatest common divisor of natural numbers is commutative: gcd(m, n) = gcd(n, m).
Nat.gcd_dvd_right- The greatest common divisor gcd(m, n) divides n.
Nat.gcd_dvd_left- The greatest common divisor gcd(m, n) divides m.
dvd_sub- If a divides b and a divides c, then a divides b - c.
dvd_mul_of_dvd_left- If a divides b, then a divides b * c for any c.
add_sub_cancel_left- In an additive group, (a + b) - a = b.
Int.dvd_of_dvd_mul_right_of_gcd_one- If an integer a divides b * c and gcd(a, b) = 1, then a divides c (Euclid's lemma for integers).
Int.gcd- The greatest common divisor of two integers as a natural number.
Nat.dvd_one.mp- If a natural number divides 1, then it equals 1.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem integer_primitive_ray_coeff_coprime {ι : Type*} (u v x : ι → ℤ) (hprimv : ∀ d : ℕ, (∀ i, (d : ℤ) ∣ v i) → d ∣ 1) (D a b : ℕ) (htr : Nat.Coprime (Nat.gcd a b) D) (hrel : ∀ i, (D : ℤ) * x i = (a : ℤ) * u i + (b : ℤ) * v i) : Nat.Coprime a D := by let g := Nat.gcd a D have hbg : Nat.Coprime b g := by apply Nat.coprime_iff_gcd_eq_one.mpr dsimp [g] rw [← Nat.gcd_assoc, Nat.gcd_comm b a] exact htr.gcd_eq_one have hgD : (g : ℤ) ∣ (D : ℤ) := by exact_mod_cast Nat.gcd_dvd_right a D have hga : (g : ℤ) ∣ (a : ℤ) := by exact_mod_cast Nat.gcd_dvd_left a D have hvdiv (i : ι) : (g : ℤ) ∣ v i := by have hp : (g : ℤ) ∣ (b : ℤ) * v i := by have hh := dvd_sub (dvd_mul_of_dvd_left hgD (x i)) (dvd_mul_of_dvd_left hga (u i)) rw [hrel] at hh simpa only [add_sub_cancel_left] using hh apply Int.dvd_of_dvd_mul_right_of_gcd_one hp simpa [Int.gcd, Nat.gcd_comm] using hbg.gcd_eq_one exact Nat.coprime_iff_gcd_eq_one.mpr (Nat.dvd_one.mp (hprimv g hvdiv))