AFTD Auto-Formalizing Theoretical Domains

gcd_self_add_five

theoremverified

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.

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

    line 3

    uses Nat.gcd_self_add_right

      rw [Nat.gcd_self_add_right]
  2. 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`.

    line 4

    uses Nat.gcd_dvd_right

      exact 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

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