LemmaStatement: AI-adaptedProof: AI-adaptedprecheck passaudited 2026-08-13

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

There are arbitrarily large primes congruent to $2$ modulo $3$

Statement

For every natural $M$ , there is a prime $p > M$ with $p \equiv 2 (m o d 3)$ .

Facts & Assumptions

Given: A natural number $M$ .

[L1]

Every positive integer has a finite prime factorisation, including multiplicities; $1$ is represented by the empty product (Every integer $n \geq 1$ is a finite product of primes: there are $r \in N$ and a list $p : r \to Z$ of primes with $n = \prod_{i < r} p_{i}$ , the case $n = 1$ being the empty product).

[L2]

Congruence modulo $3$ and multiplication of residue classes obey integer modular algebra (Congruence modulo an integer: $a \equiv b (m o d n)$ when $n ∣ (a - b)$ , including the moduli $0$ and $1$ , For every natural $n$ , $(Z / n, +)$ is an abelian group, multiplication is a commutative monoid operation, and both distributive laws hold).

[L3]

A finite product in a monoid is $1$ on the empty family and obeys the product recursion (The product $g_{0} g_{1} \dots g_{n - 1}$ of a finite list in a monoid, by recursion, with the empty product ( $n = 0$ ) equal to the identity).

Proof

technique · constructive

1.1

Let $q_{1}, \dots, q_{r}$ be all primes at most $M$ that are congruent to $2$ modulo $3$ , allowing $r = 0$ , and put $N = 3 q_{1} \dots q_{r} - 1$ . Then $N \equiv 2 (m o d 3)$ and $N > 1$ ; when the list is empty, $N = 2$ .

L2L3construct

2.1

No $q_{i}$ divides $N$ , because $N \equiv - 1 (m o d q_{i})$ . Also $3$ does not divide $N$ .

step 1.1L2

3.1

In a prime factorisation of the positive integer $N$ , not every factor can be congruent to $1$ modulo $3$ , since their product is congruent to $2$ ; no factor is congruent to $0$ by step 2.1, so some prime factor $p$ is congruent to $2$ modulo $3$ .

step 1.1step 2.1L1L2

4.1

That $p$ is not among the $q_{i}$ by step 2.1, hence $p > M$ . It is the required prime.

step 2.1step 3.1discharge-construct∎

Depends on

Used by

Every nonempty finite set of n nonzero integers has a sum-free subset of size greater than n/3 Theorem

Dependency tree · two levels

26 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

M. Bucic, Probabilistic Method, proof of Theorem 2.3 (standard reference, not scraped)

There are arbitrarily large primes congruent to 22 modulo 33