TheoremStatement: Literature-sourcedProof: AI-adaptedSession-authored (Fable 5 assisted)precheck passaudited 2026-08-26

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.

For every $n \geq 1$ there are infinitely many primes $p$ with $p \equiv 1 (m o d n)$

Statement

For every integer $n \geq 1$ , the set

$T_{n} : = {p \in Z : p is prime and p \equiv 1 ⁣ ⁣ (m o d n)}$

(Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ , Congruence modulo an integer: $a \equiv b (m o d n)$ when $n ∣ (a - b)$ , including the moduli $0$ and $1$ ) is not finite (Finite, countably infinite, countable, uncountable).

Facts & Assumptions

Given: An integer $n \geq 1$ and the cyclotomic polynomial $Φ_{n} \in Z [t]$ (The cyclotomic polynomials $Φ_{n} \in Z [t]$ , defined by $\prod_{d ∣ n} Φ_{d} = t^{n} - 1$ ); evaluation at an integer is the ring homomorphism $Z [t] \to Z$ of Universal property of $R [x]$ : a coefficient homomorphism and the image of $x$ determine a unique ring homomorphism and Evaluation and roots of a polynomial in a commutative target ring.

[L1]

$Φ_{n}$ is monic in $Z [t]$ of degree $φ (n) \geq 1$ and $\prod_{d ∣ n} Φ_{d} = t^{n} - 1$ (The recursion defines a unique monic $Φ_{n} \in Z [t]$ , of degree $φ (n)$ , Degree, leading coefficient and monic polynomial, with the zero polynomial having no degree, The unit group $(Z / n)^{\times}$ and Euler's totient $φ (n) = ∣ (Z / n)^{\times} ∣$ for $n \geq 1$ ).

[L2]

$Φ_{n} (0) = 1$ for every $n \geq 2$ ( $Φ_{1} (0) = - 1$ and $Φ_{n} (0) = 1$ for $n \geq 2$ ).

[L3]

Over a field $K$ with $char K ∤ n$ and a splitting field $E$ of $t^{n} - 1$ over $K$ , the roots of the image of $Φ_{n}$ in $E$ are exactly the primitive $n$ -th roots of unity in $E$ , that is the elements of order $n$ in $E^{\times}$ (Over a field whose characteristic does not divide $n$ , the roots of $Φ_{n}$ are exactly the primitive roots of unity, The group $μ_{n} (K)$ of $n$ -th roots of unity in a field, and primitive $n$ -th roots of unity, The order $∣ G ∣$ of a finite group and the order $ord (g)$ of an element, with $ord (g) = \infty$ when no positive power of $g$ is the identity).

[L4]

$Z / p$ is a field of characteristic $p$ for every prime $p$ (For every prime $p$ , the two operations on $Z / p$ make it a field, The characteristic of a ring: the least $n \geq 1$ with $n \cdot 1_{R} = 0$ when one exists, and $0$ otherwise, The characteristic of a field is zero or a prime number, The congruence class $[a]_{n}$ and the quotient set $Z / n$ ), and every nonzero polynomial over a field has a splitting field (Every nonzero polynomial over a field has a splitting field).

[L5]

$∣ (Z / p)^{\times} ∣ = φ (p) = p - 1$ for a prime $p$ ( $φ (1) = 1$ , and $φ (p) = p - 1$ for every prime $p$ , The unit group $(Z / n)^{\times}$ and Euler's totient $φ (n) = ∣ (Z / n)^{\times} ∣$ for $n \geq 1$ ); and for a finite group $G$ with $H \leq G$ , $∣ H ∣$ divides $∣ G ∣$ (Lagrange's theorem: $∣ G ∣ = [G : H] ∣ H ∣$ for every subgroup $H$ of a finite group $G$ ), while $∣ ⟨ x ⟩ ∣ = ord (x)$ (If $ord (g) = n$ then $g^{k} = e$ iff $k$ is an integer multiple of $n$ , the powers $g^{0}, \dots, g^{n - 1}$ are distinct, and $⟨ g ⟩$ has exactly $n$ elements; if $g$ has infinite order then $g^{j} = g^{k}$ only for $j = k$ ).

[L6]

Every integer greater than $1$ has a prime divisor (Every integer $n > 1$ has a prime divisor; indeed the least divisor of $n$ that exceeds $1$ is prime, Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ).

[L7]

A nonzero polynomial of degree $k$ over an integral domain has at most $k$ distinct roots in it (A nonzero polynomial of degree $n$ over an integral domain has at most $n$ distinct roots).

[L8]

The set of primes is not finite (Euclid's theorem: for every $n \in N$ and every list $p : n \to Z$ of primes there is a prime not among $p_{0}, \dots, p_{n - 1}$ ; consequently the set of primes is not finite).

Proof

technique · cases

1.1

In the case $n = 1$ , every integer is congruent to $1$ modulo $1$ , since $1$ divides every integer, so $T_{1}$ is the set of all primes, which is not finite by [L8].

assume-case oneL8given

1.2

In the case $n \geq 2$ , let $S \subseteq T_{n}$ be any finite set and put $M : = n \prod_{p \in S} p$ , an integer with $M \geq 2$ ; the goal is to produce a prime in $T_{n}$ outside $S$ .

assume-case biggiven

2.1

There is an integer $k \geq 1$ with $∣ Φ_{n} (k M) ∣ > 1$ : the three polynomials $Φ_{n}$ , $Φ_{n} - 1$ and $Φ_{n} + 1$ are nonzero of degree $φ (n) \geq 1$ by [L1], so by [L7] over the integral domain $Z$ at most $3 φ (n)$ integers $x$ satisfy $Φ_{n} (x) \in {- 1, 0, 1}$ ; the integers $M, 2 M, 3 M, \dots$ are pairwise distinct, so some $k M$ with $k \geq 1$ avoids that finite set.

step 1.2L1L7

2.2

Since $Φ_{n} (0) = 1$ by [L2], there is $h \in Z [t]$ with $Φ_{n} = 1 + t h$ ; evaluating at $k M$ gives $N : = Φ_{n} (k M) = 1 + k M h (k M)$ .

step 1.2L1L2given

3.1

By step 2.1 the integer $∣ N ∣$ exceeds $1$ , so it has a prime divisor $p$ by [L6], and $p ∣ N$ . That prime does not divide $k M$ : otherwise $p$ would divide $k M h (k M)$ and hence $N - k M h (k M) = 1$ , which is impossible for a prime. In particular $p ∤ M$ , so $p ∤ n$ and $p \notin S$ , both $n$ and every member of $S$ dividing $M$ .

step 2.1step 2.2L6given

4.1

Reduce modulo $p$ . Since $p ∣ Φ_{n} (k M)$ , the class $α : = [k M]_{p}$ is a root of the image of $Φ_{n}$ in $(Z / p) [t]$ , and $α \neq 0$ because $p ∤ k M$ by step 3.1. Let $E$ be a splitting field of $t^{n} - 1$ over $Z / p$ , which exists by [L4]; as $char (Z / p) = p$ does not divide $n$ , [L3] applies and $α$ , lying in $Z / p \subseteq E$ , has order exactly $n$ in $E^{\times}$ .

step 3.1L3L4

5.1

The order of $α$ in the subgroup $(Z / p)^{\times}$ of $E^{\times}$ is the same $n$ , so $n$ divides $∣ (Z / p)^{\times} ∣ = p - 1$ by [L5]; that is $p \equiv 1 (m o d n)$ , so $p \in T_{n}$ and $p \notin S$ .

step 3.1step 4.1L5given

6.1

In the case $n \geq 2$ , then, no finite subset of $T_{n}$ exhausts it, so $T_{n}$ is not finite; with step 1.1 the two cases are exhaustive and cover every $n \geq 1$ .

step 1.1step 5.1cases-exhaustive∎

Remarks

What replaces the archimedean estimate. The usual proof chooses $x$ large enough that $∣ Φ_{n} (x) ∣ > 1$ by a growth estimate. Step 2.1 replaces that by a root count, which needs no order structure on $Z$ beyond the distinctness of the multiples of $M$ , and gives exactly the same conclusion.
The case $n = 1$ is not a degenerate instance. For $n = 1$ one has $Φ_{1} (0) = - 1$ , not $1$ ( $Φ_{1} (0) = - 1$ and $Φ_{n} (0) = 1$ for $n \geq 2$ ), so step 2.2 is unavailable; the congruence is vacuous there and the statement is Euclid's theorem.

Depends on

Used by

Every finite abelian group is the Galois group of some finite Galois extension of ℚ Theorem

Dependency tree · two levels

105 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

P. L. Clark, Field Theory (course notes/monograph), Theorem 9.10 (standard reference, not scraped)
K. Conrad, Cyclotomic Extensions (expository blurb), Section 5 (standard reference, not scraped)

For every n≥1n≥1 there are infinitely many primes pp with p≡1(modn)p≡1(modn)