frobenius_extremal_family_coprime
For any natural numbers n and q, the numbers q and (n - 2) * q + 1 are coprime.
Statement
theorem frobenius_extremal_family_coprime (n q : ℕ) : Nat.Coprime q ((n - 2) * q + 1)- Source
- scout/2610-32219-a-sharp-upper-bound-for-the-frobenius-number.md:456
- Verified
- 27 Oct 2026
- Axioms
Quot.soundpropext- Used by 1
- frobenius_extremal_family_frobenius_numberFor any integers n ≥ 3 and q ≥ 2, the Frobenius number of the extremal family
frobenius_extremal_family n qis equal to ((n - 2) * q +…
- frobenius_extremal_family_frobenius_numberFor any integers n ≥ 3 and q ≥ 2, the Frobenius number of the extremal family
Read back from the Lean
For all natural numbers n and q, q and (n - 2) * q + 1 are coprime (using truncated subtraction on ℕ).
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
The proof reduces coprimality to the base case that q is coprime to 1. Since adding any multiple of q preserves coprimality with q, q is coprime to 1 + (n - 2) * q. Applying commutativity of addition concludes that q and (n - 2) * q + 1 are coprime.
q and (n - 2) * q + 1 are coprime.
Every natural number q is coprime to 1 (by Nat.coprime_one_right). Adding any multiple of q to 1 preserves coprimality with q (by Nat.coprime_add_mul_right_right), showing that q is coprime to 1 + (n - 2) * q. Commuting the addition (via Nat.add_comm) gives that q is coprime to (n - 2) * q + 1.
uses
Nat.add_comm,Nat.coprime_add_mul_right_right,Nat.coprime_one_rightsimpa [Nat.add_comm] using (Nat.coprime_add_mul_right_right q 1 (n - 2)).mpr (Nat.coprime_one_right q)
Nat.add_comm- Addition of natural numbers is commutative: n + m = m + n.
Nat.coprime_add_mul_right_right- A number m is coprime to n + k * m if and only if m is coprime to n.
Nat.coprime_one_right- Every natural number n is coprime to 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.
/-- The generators q and (n - 2) * q + 1 are coprime. -/theorem frobenius_extremal_family_coprime (n q : ℕ) : Nat.Coprime q ((n - 2) * q + 1) := by simpa [Nat.add_comm] using (Nat.coprime_add_mul_right_right q 1 (n - 2)).mpr (Nat.coprime_one_right q)