AFTD Auto-Formalizing Theoretical Domains

exists_infinite_primes_mod_three_two_and_mod_m_one

theoremverified

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.

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

    lines 4–13

    uses Nat.coprime_mul_iff_right, Nat.gcd_comm, Nat.gcd_rec, mul_comm, Nat.coprime_mul_left_add_left, Nat.coprime_one_left

      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
  2. 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.

    lines 14–16

    uses Nat.infinite_setOfPred_prime_and_modEq

      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
  3. 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.

    lines 17–18

    uses Set.finite_lt_nat

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

    lines 19–21

    uses Set.Infinite.mono

      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, ?_, ?_, ?_⟩
  5. 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.

    lines 22–24

    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
  6. 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.

    lines 25–30

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

    line 31

    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

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