AFTD Auto-Formalizing Theoretical Domains

infinite_primes_five_mod_six

theoremverified

There are infinitely many prime numbers p such that p ≡ 5 [MOD 6].

Statement

lemma infinite_primes_five_mod_six : {p : ℕ | Nat.Prime p ∧ p ≡ 5 [MOD 6]}.Infinite
Source
arXiv:2611.07607, proof of Corollary 1.3
Verified
07 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

Read back from the Lean

The set of natural numbers $p$ such that $p$ is prime and $p \equiv 5 \pmod 6$ (i.e., $p \bmod 6 = 5 \bmod 6$) is infinite.

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 theorem follows directly from Dirichlet's theorem on primes in arithmetic progressions (`Nat.infinite_setOfPred_prime_and_modEq`), which guarantees infinitely many primes congruent to $a$ modulo $q$ whenever $q \neq 0$ and $\gcd(a, q) = 1$. Specializing to $a = 5$ and $q = 6$, the required side conditions $6 \neq 0$ and $\gcd(5, 6) = 1$ are established by straightforward numerical evaluation.

  1. The set of primes congruent to 5 modulo 6 is infinite. automation

    The result follows by applying Dirichlet's theorem on arithmetic progressions (`Nat.infinite_setOfPred_prime_and_modEq`) with modulus $q = 6$ and residue $a = 5$. The two hypotheses of the theorem—that the modulus is nonzero ($6 \neq 0$) and that the residue is coprime to the modulus ($\gcd(5, 6) = 1$)—are both verified by direct computation (`decide`).

    line 2

    uses Nat.infinite_setOfPred_prime_and_modEq

    lemma infinite_primes_five_mod_six : {p : ℕ | Nat.Prime p ∧ p ≡ 5 [MOD 6]}.Infinite := Nat.infinite_setOfPred_prime_and_modEq (by decide) (by decide)
Nat.infinite_setOfPred_prime_and_modEq
For any modulus $q \neq 0$ and residue $a$ coprime to $q$, there are infinitely many primes congruent to $a$ modulo $q$.

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

/-- There are infinitely many primes congruent to 5 modulo 6. -/lemma infinite_primes_five_mod_six : {p : ℕ | Nat.Prime p ∧ p ≡ 5 [MOD 6]}.Infinite := Nat.infinite_setOfPred_prime_and_modEq (by decide) (by decide)
See it in the graphDiscuss this resultChallenge it