AFTD Auto-Formalizing Theoretical Domains

prime_coprime_of_mod_ne_zero

theoremverified

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.

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

    lines 3–4

    uses Nat.coprime_comm, hn.coprime_iff_not_dvd

      rw [Nat.coprime_comm]
      rw [hn.coprime_iff_not_dvd]
  2. 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`.

    line 5

    uses Nat.dvd_iff_mod_eq_zero

      rwa [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

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