scalar_sampler_m_pairwise_coprime
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.
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).
uses
Nat.coprime_of_dvdhave _ := hr intro m apply Nat.coprime_of_dvd intro p hp hj_dvd hk_dvd
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 ℤ.
uses
Int.dvd_natAbs.mp,Int.natCast_dvd_natCast.mpr,dvd_subhave 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
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 ℕ.
uses
Int.natCast_dvd_natCast,Int.natCast_natAbs,dvd_abs,Int.natAbs_mul,Int.natAbs_natCasthave 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
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)!.
uses
Nat.Prime.dvd_mul,Nat.le_of_dvd,Nat.Prime.dvd_factorialhave 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
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.
uses
Int.natCast_dvd_natCast.mpr,dvd_mul_of_dvd_left,dvd_subhave 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
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.
uses
Int.natCast_dvd_natCast.mp,hp.not_dvd_onehave 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.
- The hypothesis `1 ≤ r` (named `hr`) is stated in the theorem and retained on line 6, but is not used in the divisibility argument.
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.
/-- 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