prime_coprime_of_mod_ne_zero
For any prime n and natural number s, if s is not divisible by n (s % n ≠ 0), then s and n are coprime.
Statement
theorem prime_coprime_of_mod_ne_zero (n s : ℕ) (hn : n.Prime) (hs : s % n ≠ 0) : Nat.Coprime s n- Source
- arXiv:2610.24758 Lemma 1 proof
- Verified
- 22 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext
Read back from the Lean
For any natural numbers $n$ and $s$, if $n$ is prime and $s \pmod n \neq 0$ (that is, $n$ does not divide $s$), then $s$ and $n$ are coprime (i.e., $\gcd(s, n) = 1$).
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 show that a natural number s and a prime n are coprime, we reduce the problem to showing that n does not divide s, using the fact that a prime is coprime to every number it does not divide. Divisibility n ∣ s is equivalent to s % n = 0. Since the remainder s % n is assumed to be non-zero, n cannot divide s, which completes the proof.
It suffices to show that n does not divide s (¬(n ∣ s)).
By the symmetry of coprimality (`Nat.coprime_comm`), s and n are coprime if and only if n and s are coprime. Since n is prime (`hn`), n is coprime to s if and only if n does not divide s (`hn.coprime_iff_not_dvd`).
uses
Nat.coprime_comm,hn.coprime_iff_not_dvdrw [Nat.coprime_comm] rw [hn.coprime_iff_not_dvd]
The non-divisibility condition ¬(n ∣ s) holds, concluding the proof.
Divisibility n ∣ s is equivalent to the remainder being zero, s % n = 0 (`Nat.dvd_iff_mod_eq_zero`). Rewriting the goal with this equivalence transforms ¬(n ∣ s) into s % n ≠ 0, which holds immediately by the hypothesis `hs`.
uses
Nat.dvd_iff_mod_eq_zerorwa [Nat.dvd_iff_mod_eq_zero]
Nat.coprime_comm- Two natural numbers are coprime if and only if they are coprime in reverse order: m is coprime to n if and only if n is coprime to m.
hn.coprime_iff_not_dvd- For any prime p and natural number n, p and n are coprime if and only if p does not divide n.
Nat.dvd_iff_mod_eq_zero- A natural number m divides n if and only if the remainder n % m is zero.
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.
/-- A prime n and a natural number s not divisible by n are coprime. -/theorem prime_coprime_of_mod_ne_zero (n s : ℕ) (hn : n.Prime) (hs : s % n ≠ 0) : Nat.Coprime s n := by rw [Nat.coprime_comm] rw [hn.coprime_iff_not_dvd] rwa [Nat.dvd_iff_mod_eq_zero]