Infinitude of the primes $p\equiv1 \operatorname{mod} n$

$\textbf{Theorem:}$ Fix $1 < n \in \mathbb{Z}$. There are infinitely many primes $p\equiv1 \operatorname{mod} n$.

$\textbf{Proof}$ Recall that the $n$-th cyclotomic polynomial $\Phi_n(x)$ is monic, has integer coefficients and has constant coefficient $\pm 1$. And $\Phi_n(x)$ is not constant. Suppose there were only finitely-many primes $p_1, \dots, p_t$ equal to $1 \operatorname{mod} n$. Then for large enough positive integer $l$, $$N = \Phi_n(l \cdot np_1 \dots p_t) > 1$$ and $N$ is an integer. Since $\Phi_n(x)$ has integer coefficients and has constant term $\pm 1$, "for each $p_i$ we have that $N= \pm 1 \operatorname{mod} p_i$"

How does the statement in quotations follow from $\Phi_n(x)$ having integer coefficients and constant term $\pm 1$. Can anyone elaborate upon this ?

• Notational issue: it's $\equiv 1 \mod n$, not $= 1 \mod n$ (and similarly, it's "congruent to $1$ modulo $n$", not "equal to $1$ modulo $n$", unless you are being very colloquial). – darij grinberg Jul 2 '15 at 19:42

If $f=a_nx^n+\cdots+a_1x\pm1$ with integer coefficients $a_i$, then for any given integer $m$, we have \begin{align*} f(km)&=a_n(km)^n+\cdots+a_1(km)\pm 1\\\\ &=m\cdot(a_nk^nm^{n-1}+\cdots+a_1k)\pm1\\\\ &\equiv \pm 1\bmod m \end{align*} for any integer $k$. In your situation, $m=p_1\cdots p_t$, so $$N=\Phi_n(\underbrace{l\cdot n}_{k}\cdot \underbrace{p_1\cdots p_t}_{m})\equiv \pm 1\bmod (p_1\cdots p_t)$$ which implies $N\equiv \pm1\bmod p_i$ for each $i$.
• Got it. Not bad if you think of $\Phi_n(x)$ as you have written $f(x)$. – Yuugi Jul 2 '15 at 19:47