exists_infinite_primes_mod_three_two_and_mod_m_one
For any natural number $m \ge 2$ with $m \equiv 2 \pmod 3$, there are infinitely many primes $p$ such that $p \equiv 2 \pmod 3$, $p \equiv 1 \pmod m$, and $p \ge 3m + 2$.
Statement
theorem exists_infinite_primes_mod_three_two_and_mod_m_one (m : ℕ) (hm : 2 ≤ m) (hm3 : m % 3 = 2) :
{p : ℕ | Nat.Prime p ∧ p % 3 = 2 ∧ p % m = 1 ∧ 3 * m + 2 ≤ p}.Infinite- Source
- arXiv:2611.07607 Section 4.1
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
Read back from the Lean
For every natural number $m$ such that $2 \le m$ and $m \equiv 2 \pmod 3$, the set of prime natural numbers $p$ satisfying $p \equiv 2 \pmod 3$, $p \equiv 1 \pmod m$, and $3m + 2 \le p$ 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 proof applies Dirichlet's theorem on primes in arithmetic progressions to obtain infinitely many primes p ≡ 2m + 1 (mod 3m). Because m ≡ 2 (mod 3), 2m + 1 is coprime to both 3 and m, making it coprime to 3m. Any prime congruent to 2m + 1 modulo 3m automatically satisfies p ≡ 2 (mod 3) and p ≡ 1 (mod m) by divisibility. Finally, removing the finitely many primes strictly less than 3m + 2 preserves infinitude and guarantees the lower bound p ≥ 3m + 2.
2m + 1 and 3m are coprime.
By Nat.coprime_mul_iff_right, 2m + 1 is coprime to 3m if and only if it is coprime to both 3 and m. For 3, Euclidean reduction (Nat.gcd_comm, Nat.gcd_rec) simplifies gcd(2m + 1, 3) to gcd((2m + 1) % 3, 3); since m ≡ 2 (mod 3), linear arithmetic gives (2m + 1) % 3 = 2, and gcd(2, 3) = 1 is verified by computation. For m, subtracting 2m using mul_comm and Nat.coprime_mul_left_add_left reduces the coprimality of 2m + 1 and m to that of 1 and m, which holds by Nat.coprime_one_left.
uses
Nat.coprime_mul_iff_right,Nat.gcd_comm,Nat.gcd_rec,mul_comm,Nat.coprime_mul_left_add_left,Nat.coprime_one_lefthave hcoprime : (2 * m + 1).Coprime (3 * m) := by rw [Nat.coprime_mul_iff_right] refine ⟨?_, ?_⟩ · change (2 * m + 1).gcd 3 = 1 rw [Nat.gcd_comm, Nat.gcd_rec] have h : (2 * m + 1) % 3 = 2 := by omega rw [h] decide · rw [mul_comm, Nat.coprime_mul_left_add_left] exact Nat.coprime_one_left m
There are infinitely many primes congruent to 2m + 1 modulo 3m.
Since m ≥ 2, the modulus 3m is nonzero. Applying Dirichlet's theorem on arithmetic progressions (Nat.infinite_setOfPred_prime_and_modEq) with modulus 3m and coprime residue 2m + 1, the set of such primes is infinite.
uses
Nat.infinite_setOfPred_prime_and_modEqhave hne : 3 * m ≠ 0 := by omega have hinf : {p : ℕ | Nat.Prime p ∧ p ≡ 2 * m + 1 [MOD 3 * m]}.Infinite := Nat.infinite_setOfPred_prime_and_modEq hne hcoprime
The set of primes congruent to 2m + 1 modulo 3m that are at least 3m + 2 is infinite.
The set of natural numbers strictly less than 3m + 2 is finite by Set.finite_lt_nat. Removing this finite set from the infinite set of primes in the arithmetic progression leaves an infinite set.
uses
Set.finite_lt_nathave hinf_diff : ({p : ℕ | Nat.Prime p ∧ p ≡ 2 * m + 1 [MOD 3 * m]} \ {p : ℕ | p < 3 * m + 2}).Infinite := hinf.sdiff (Set.finite_lt_nat (3 * m + 2))To prove the target set of primes is infinite, it suffices to verify the congruence and inequality conditions for primes p ≡ 2m + 1 (mod 3m) with p ≥ 3m + 2.
By monotonicity of infinite sets (Set.Infinite.mono), an infinite subset implies the ambient set is infinite. We take an arbitrary element p from the infinite difference set constructed in the previous step and unpack its properties: p is prime, p ≡ 2m + 1 (mod 3m), and p is not strictly less than 3m + 2.
uses
Set.Infinite.monoapply Set.Infinite.mono (s := {p : ℕ | Nat.Prime p ∧ p ≡ 2 * m + 1 [MOD 3 * m]} \ {p : ℕ | p < 3 * m + 2}) _ hinf_diff rintro p ⟨⟨hp, hmod⟩, hnotlt⟩ refine ⟨hp, ?_, ?_, ?_⟩
Any such prime p satisfies p ≡ 2 (mod 3).
Because 3 divides 3m (dvd_mul_right), the congruence p ≡ 2m + 1 (mod 3m) implies p ≡ 2m + 1 (mod 3). Using the hypothesis m % 3 = 2, modular arithmetic gives (2m + 1) % 3 = 2, so p % 3 = 2.
uses
dvd_mul_right· have h3 : p ≡ 2 * m + 1 [MOD 3] := hmod.of_dvd (dvd_mul_right 3 m) change p % 3 = (2 * m + 1) % 3 at h3 omega
Any such prime p satisfies p ≡ 1 (mod m).
Because m divides 3m (dvd_mul_left), p ≡ 2m + 1 (mod m). Rewriting 2m + 1 as 1 + m * 2, Nat.add_mul_mod_self_left reduces (1 + m * 2) % m to 1 % m. Since m ≥ 2, we have 1 < m, so Nat.mod_eq_of_lt evaluates 1 % m = 1.
uses
dvd_mul_left,Nat.add_mul_mod_self_left,Nat.mod_eq_of_lt· have hm' : p ≡ 2 * m + 1 [MOD m] := hmod.of_dvd (dvd_mul_left m 3) change p % m = (2 * m + 1) % m at hm' rw [hm'] have : 2 * m + 1 = 1 + m * 2 := by omega rw [this, Nat.add_mul_mod_self_left] exact Nat.mod_eq_of_lt (by omega)
Any such prime p satisfies 3m + 2 ≤ p.
Since p does not belong to {p | p < 3m + 2}, the negated strict inequality ¬(p < 3m + 2) implies 3m + 2 ≤ p by not_lt.mp.
uses
not_lt.mp· exact not_lt.mp hnotlt
Nat.coprime_mul_iff_right- A number k is coprime to a product m * n if and only if k is coprime to both m and n.
Nat.gcd_comm- The greatest common divisor of m and n equals that of n and m.
Nat.gcd_rec- Euclidean algorithm step: gcd(m, n) = gcd(n % m, m).
mul_comm- Multiplication is commutative: a * b = b * a.
Nat.coprime_mul_left_add_left- Adding a multiple of n to m preserves coprimality with n: gcd(n * k + m, n) = 1 ↔ gcd(m, n) = 1.
Nat.coprime_one_left- 1 is coprime to any natural number n.
Nat.infinite_setOfPred_prime_and_modEq- Dirichlet's theorem on arithmetic progressions: if q ≠ 0 and gcd(a, q) = 1, then there are infinitely many primes p ≡ a (mod q).
Set.finite_lt_nat- The set of natural numbers strictly less than n is finite.
Set.Infinite.mono- If a subset s ⊆ t is infinite, then t is infinite.
dvd_mul_right- Any element a divides the product a * b.
dvd_mul_left- Any element a divides the product b * a.
Nat.add_mul_mod_self_left- Adding a multiple of y to x does not change the remainder modulo y: (x + y * z) % y = x % y.
Nat.mod_eq_of_lt- If a < b, then a % b = a.
not_lt.mp- If a is not strictly less than b, then b ≤ a.
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.
/-- There are infinitely many primes congruent to 2 mod 3 and 1 mod m that are at least 3m + 2. -/theorem exists_infinite_primes_mod_three_two_and_mod_m_one (m : ℕ) (hm : 2 ≤ m) (hm3 : m % 3 = 2) : {p : ℕ | Nat.Prime p ∧ p % 3 = 2 ∧ p % m = 1 ∧ 3 * m + 2 ≤ p}.Infinite := by have hcoprime : (2 * m + 1).Coprime (3 * m) := by rw [Nat.coprime_mul_iff_right] refine ⟨?_, ?_⟩ · change (2 * m + 1).gcd 3 = 1 rw [Nat.gcd_comm, Nat.gcd_rec] have h : (2 * m + 1) % 3 = 2 := by omega rw [h] decide · rw [mul_comm, Nat.coprime_mul_left_add_left] exact Nat.coprime_one_left m have hne : 3 * m ≠ 0 := by omega have hinf : {p : ℕ | Nat.Prime p ∧ p ≡ 2 * m + 1 [MOD 3 * m]}.Infinite := Nat.infinite_setOfPred_prime_and_modEq hne hcoprime have hinf_diff : ({p : ℕ | Nat.Prime p ∧ p ≡ 2 * m + 1 [MOD 3 * m]} \ {p : ℕ | p < 3 * m + 2}).Infinite := hinf.sdiff (Set.finite_lt_nat (3 * m + 2)) apply Set.Infinite.mono (s := {p : ℕ | Nat.Prime p ∧ p ≡ 2 * m + 1 [MOD 3 * m]} \ {p : ℕ | p < 3 * m + 2}) _ hinf_diff rintro p ⟨⟨hp, hmod⟩, hnotlt⟩ refine ⟨hp, ?_, ?_, ?_⟩ · have h3 : p ≡ 2 * m + 1 [MOD 3] := hmod.of_dvd (dvd_mul_right 3 m) change p % 3 = (2 * m + 1) % 3 at h3 omega · have hm' : p ≡ 2 * m + 1 [MOD m] := hmod.of_dvd (dvd_mul_left m 3) change p % m = (2 * m + 1) % m at hm' rw [hm'] have : 2 * m + 1 = 1 + m * 2 := by omega rw [this, Nat.add_mul_mod_self_left] exact Nat.mod_eq_of_lt (by omega) · exact not_lt.mp hnotlt