AFTD Auto-Formalizing Theoretical Domains

integer_primitive_ray_coeff_coprime

theoremverified

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

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.

  1. 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.

    lines 11–16

    uses Nat.coprime_iff_gcd_eq_one.mpr, Nat.gcd_assoc, Nat.gcd_comm

      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
  2. 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 : ℤ).

    lines 17–18

    uses Nat.gcd_dvd_right, Nat.gcd_dvd_left

      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
  3. 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).

    lines 19–25

    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_comm

      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
  4. 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.

    line 26

    uses Nat.coprime_iff_gcd_eq_one.mpr, Nat.dvd_one.mp

      exact 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

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))
See it in the graphDiscuss this resultChallenge it