AFTD Auto-Formalizing Theoretical Domains

scalar_sampler_m_pairwise_coprime

theoremverified

For integers q ≥ 3 and r ≥ 1, the parameters m_j = 1 + (q-1)!(12r(q-1) + j) for 0 ≤ j < q are pairwise coprime.

Statement

theorem scalar_sampler_m_pairwise_coprime (q r : ℕ) (hq : 3 ≤ q) (hr : 1 ≤ r)
    {j k : ℕ} (hj : j < q) (hk : k < q) (hjk : j ≠ k) :
    let m : ℕ → ℤ := fun i => 1 + (q - 1).factorial * (12 * r * (q - 1) + i)
    Nat.Coprime (m j).natAbs (m k).natAbs
Source
arXiv:2611.13281, Section 2, equation (1)
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

Read back from the Lean

For all natural numbers $q$ and $r$ with $3 \le q$ and $1 \le r$, and for any natural numbers $j$ and $k$ such that $j < q$, $k < q$, and $j \ne k$, let $m : \mathbb{N} \to \mathbb{Z}$ be defined by $m(i) = 1 + (q - 1)! \cdot (12 \cdot r \cdot (q - 1) + i)$. Then the absolute values $|m(j)|$ and $|m(k)|$ (as natural numbers) are coprime.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

To prove that the moduli m_j and m_k (for j ≠ k and j, k < q) are coprime, we assume for contradiction that they share a common prime factor p. The difference m_j - m_k is (q - 1)!(j - k), which forces p to divide (q - 1)! since 0 < |j - k| ≤ q - 1. But by construction m_k ≡ 1 (mod (q - 1)!), so p ∣ (q - 1)! implies that p divides m_k - (q - 1)!(12r(q - 1) + k) = 1, contradicting that p is prime.

  1. To prove that |m_j| and |m_k| are coprime, suppose for contradiction that some prime p divides both.

    By Nat.coprime_of_dvd, two natural numbers are coprime if they share no common prime factor. We introduce the assumption that a prime p divides both |m_j| and |m_k|, reducing the goal to deriving a contradiction (False).

    lines 6–9

    uses Nat.coprime_of_dvd

      have _ := hr
      intro m
      apply Nat.coprime_of_dvd
      intro p hp hj_dvd hk_dvd
  2. As integers, p divides the difference m_j - m_k, which simplifies to (q - 1)!(j - k).

    Since p divides |m_j| and |m_k|, casting to integers shows that p ∣ m_j and p ∣ m_k using Int.dvd_natAbs.mp and Int.natCast_dvd_natCast.mpr. By dvd_sub, p divides their difference m_j - m_k. Expanding the definition of m reveals that the constant 1 and the leading terms cancel out, leaving m_j - m_k = (q - 1)!(j - k) by ring arithmetic. Substituting this identity gives p ∣ (q - 1)!(j - k) in ℤ.

    lines 10–16

    uses Int.dvd_natAbs.mp, Int.natCast_dvd_natCast.mpr, dvd_sub

      have hj_int : (p : ℤ) ∣ m j := Int.dvd_natAbs.mp (Int.natCast_dvd_natCast.mpr hj_dvd)
      have hk_int : (p : ℤ) ∣ m k := Int.dvd_natAbs.mp (Int.natCast_dvd_natCast.mpr hk_dvd)
      have hdiff_int : (p : ℤ) ∣ m j - m k := dvd_sub hj_int hk_int
      have hm : m j - m k = ((q - 1).factorial : ℤ) * ((j : ℤ) - (k : ℤ)) := by
        dsimp [m]
        ring
      rw [hm] at hdiff_int
  3. In ℕ, p divides the product (q - 1)! * |j - k|.

    Using the equivalence between divisibility of integers and divisibility of absolute values via Int.natCast_dvd_natCast, Int.natCast_natAbs, and dvd_abs, the integer divisibility translates to p dividing |(q - 1)!(j - k)|. By Int.natAbs_mul and Int.natAbs_natCast, this becomes p ∣ (q - 1)! * |j - k| in ℕ.

    lines 17–20

    uses Int.natCast_dvd_natCast, Int.natCast_natAbs, dvd_abs, Int.natAbs_mul, Int.natAbs_natCast

      have hdvd : p ∣ (((q - 1).factorial : ℤ) * ((j : ℤ) - (k : ℤ))).natAbs := by
        rw [← Int.natCast_dvd_natCast, Int.natCast_natAbs, dvd_abs]
        exact hdiff_int
      rw [Int.natAbs_mul, Int.natAbs_natCast] at hdvd
  4. The prime p divides (q - 1)!.

    Since p is prime and divides (q - 1)! * |j - k|, by Nat.Prime.dvd_mul it must divide (q - 1)! or |j - k|. If p ∣ (q - 1)!, we are done directly. If p ∣ |j - k|, then since j ≠ k and j, k < q, linear arithmetic (omega) yields 0 < |j - k| ≤ q - 1. Since p divides this positive integer, Nat.le_of_dvd gives p ≤ |j - k| ≤ q - 1. Finally, by Nat.Prime.dvd_factorial, any prime at most q - 1 divides (q - 1)!.

    lines 21–27

    uses Nat.Prime.dvd_mul, Nat.le_of_dvd, Nat.Prime.dvd_factorial

      have hp_fac : p ∣ (q - 1).factorial := by
        rcases (Nat.Prime.dvd_mul hp).mp hdvd with h1 | h2
        · exact h1
        · have h_pos : 0 < ((j : ℤ) - (k : ℤ)).natAbs := by omega
          have h_le : ((j : ℤ) - (k : ℤ)).natAbs ≤ q - 1 := by omega
          have hp_le : p ≤ q - 1 := (Nat.le_of_dvd h_pos h2).trans h_le
          exact (Nat.Prime.dvd_factorial hp).mpr hp_le
  5. In ℤ, p divides the difference m_k - (q - 1)!(12r(q - 1) + k).

    Casting p ∣ (q - 1)! back to ℤ via Int.natCast_dvd_natCast.mpr, dvd_mul_of_dvd_left shows that p divides the product (q - 1)!(12r(q - 1) + k). Since p also divides m_k, by dvd_sub it divides their difference.

    lines 28–32

    uses Int.natCast_dvd_natCast.mpr, dvd_mul_of_dvd_left, dvd_sub

      have hfac_int : (p : ℤ) ∣ ((q - 1).factorial : ℤ) := Int.natCast_dvd_natCast.mpr hp_fac
      have h_prod : (p : ℤ) ∣ ((q - 1).factorial : ℤ) * (12 * r * (q - 1) + k) :=
        dvd_mul_of_dvd_left hfac_int _
      have h1 : (p : ℤ) ∣ m k - ((q - 1).factorial : ℤ) * (12 * r * (q - 1) + k) :=
        dvd_sub hk_int h_prod
  6. A contradiction is reached because p must divide 1.

    By definition of m, the difference m_k - (q - 1)!(12r(q - 1) + k) simplifies algebraically to 1. Thus p ∣ 1 in ℤ, which by Int.natCast_dvd_natCast.mp implies p ∣ 1 in ℕ. But a prime cannot divide 1 (hp.not_dvd_one), yielding a contradiction.

    lines 33–38

    uses Int.natCast_dvd_natCast.mp, hp.not_dvd_one

      have hm1 : m k - ((q - 1).factorial : ℤ) * (12 * r * (q - 1) + k) = 1 := by
        dsimp [m]
        ring
      rw [hm1] at h1
      have hp_dvd_one : p ∣ 1 := Int.natCast_dvd_natCast.mp h1
      exact hp.not_dvd_one hp_dvd_one
Nat.coprime_of_dvd
Two natural numbers are coprime if no prime divides both of them.
Int.dvd_natAbs.mp
If an integer divides the absolute value of an integer, it divides the integer itself.
Int.natCast_dvd_natCast.mpr
If a natural number divides another, then the divisibility also holds when both are cast to integers.
dvd_sub
If an element divides two elements, it divides their difference.
Int.natCast_dvd_natCast
Divisibility of natural numbers is equivalent to divisibility of their integer casts.
Int.natCast_natAbs
The integer cast of the absolute value of an integer equals its absolute value.
dvd_abs
An element divides the absolute value |b| if and only if it divides b.
Int.natAbs_mul
The absolute value of a product of integers is the product of their absolute values.
Int.natAbs_natCast
The absolute value of a natural number cast to an integer is the natural number itself.
Nat.Prime.dvd_mul
If a prime divides a product of two natural numbers, it divides at least one of the factors.
Nat.le_of_dvd
If a natural number divides a positive natural number, it is less than or equal to that number.
Nat.Prime.dvd_factorial
A prime divides n! if and only if it is less than or equal to n.
dvd_mul_of_dvd_left
If a divides b, then a divides b * c for any c.
Int.natCast_dvd_natCast.mp
If the integer cast of a natural number divides that of another, then the divisibility holds in the natural numbers.
hp.not_dvd_one
A prime number does not divide 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

/-- The moduli m_j = 1 + (q-1)!(12r(q-1) + j) are pairwise coprime for 0 ≤ j < q. -/theorem scalar_sampler_m_pairwise_coprime (q r : ℕ) (hq : 3 ≤ q) (hr : 1 ≤ r)    {j k : ℕ} (hj : j < q) (hk : k < q) (hjk : j ≠ k) :    let m : ℕ → ℤ := fun i => 1 + (q - 1).factorial * (12 * r * (q - 1) + i)    Nat.Coprime (m j).natAbs (m k).natAbs := by  have _ := hr  intro m  apply Nat.coprime_of_dvd  intro p hp hj_dvd hk_dvd  have hj_int : (p : ℤ) ∣ m j := Int.dvd_natAbs.mp (Int.natCast_dvd_natCast.mpr hj_dvd)  have hk_int : (p : ℤ) ∣ m k := Int.dvd_natAbs.mp (Int.natCast_dvd_natCast.mpr hk_dvd)  have hdiff_int : (p : ℤ) ∣ m j - m k := dvd_sub hj_int hk_int  have hm : m j - m k = ((q - 1).factorial : ℤ) * ((j : ℤ) - (k : ℤ)) := by    dsimp [m]    ring  rw [hm] at hdiff_int  have hdvd : p ∣ (((q - 1).factorial : ℤ) * ((j : ℤ) - (k : ℤ))).natAbs := by    rw [← Int.natCast_dvd_natCast, Int.natCast_natAbs, dvd_abs]    exact hdiff_int  rw [Int.natAbs_mul, Int.natAbs_natCast] at hdvd  have hp_fac : p ∣ (q - 1).factorial := by    rcases (Nat.Prime.dvd_mul hp).mp hdvd with h1 | h2    · exact h1    · have h_pos : 0 < ((j : ℤ) - (k : ℤ)).natAbs := by omega      have h_le : ((j : ℤ) - (k : ℤ)).natAbs ≤ q - 1 := by omega      have hp_le : p ≤ q - 1 := (Nat.le_of_dvd h_pos h2).trans h_le      exact (Nat.Prime.dvd_factorial hp).mpr hp_le  have hfac_int : (p : ℤ) ∣ ((q - 1).factorial : ℤ) := Int.natCast_dvd_natCast.mpr hp_fac  have h_prod : (p : ℤ) ∣ ((q - 1).factorial : ℤ) * (12 * r * (q - 1) + k) :=    dvd_mul_of_dvd_left hfac_int _  have h1 : (p : ℤ) ∣ m k - ((q - 1).factorial : ℤ) * (12 * r * (q - 1) + k) :=    dvd_sub hk_int h_prod  have hm1 : m k - ((q - 1).factorial : ℤ) * (12 * r * (q - 1) + k) = 1 := by    dsimp [m]    ring  rw [hm1] at h1  have hp_dvd_one : p ∣ 1 := Int.natCast_dvd_natCast.mp h1  exact hp.not_dvd_one hp_dvd_one
See it in the graphDiscuss this resultChallenge it