gcd_self_add_five
For any natural number k, the greatest common divisor of k and k + 5 divides 5.
Statement
theorem gcd_self_add_five (k : ℕ) : Nat.gcd k (k + 5) ∣ 5- Source
- arXiv:2611.05623 Theorem 3.3 proof -- Partitions with designated summands: k-tuples and their congruences
- Verified
- 09 Nov 2026
- Axioms
Quot.soundpropext
Read back from the Lean
For every natural number $k$, the greatest common divisor of $k$ and $k + 5$ divides $5$.
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 simplifies gcd(k, k + 5) using the Euclidean reduction gcd(m, m + n) = gcd(m, n), which reduces the expression to gcd(k, 5). The claim then follows immediately because the greatest common divisor of any two numbers divides each of its arguments, in particular 5.
The goal reduces to showing that gcd(k, 5) divides 5.
By the Euclidean property that gcd(m, m + n) = gcd(m, n) (`Nat.gcd_self_add_right`), gcd(k, k + 5) simplifies to gcd(k, 5).
uses
Nat.gcd_self_add_rightrw [Nat.gcd_self_add_right]gcd(k, 5) divides 5, completing the proof.
By definition, the greatest common divisor of two natural numbers divides each of them; specifically, gcd(k, 5) divides 5 by `Nat.gcd_dvd_right`.
uses
Nat.gcd_dvd_rightexact Nat.gcd_dvd_right k 5
Nat.gcd_self_add_right- For any natural numbers m and n, the greatest common divisor of m and m + n equals the greatest common divisor of m and n.
Nat.gcd_dvd_right- For any natural numbers m and n, the greatest common divisor of m and n divides n.
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 gcd of k and k + 5 divides 5 for any natural number k. -/theorem gcd_self_add_five (k : ℕ) : Nat.gcd k (k + 5) ∣ 5 := by rw [Nat.gcd_self_add_right] exact Nat.gcd_dvd_right k 5