# there are an infinite number of primes $\equiv 1\penalty 0@\mskip 12.0mu {\symoperators mod}\tmspace+{.1667em}\tmspace% +{.1667em}m$

This article proves a special case of Dirichlet’s theorem, namely that for any integer $m>1$, there are an infinite number of primes $p\equiv 1\pmod{m}$.

Let $p$ be an odd prime not dividing $m$, let $\Phi_{k}(x)$ be the $k^{\mathrm{th}}$ cyclotomic polynomial, and note that

 $x^{m}-1=\Phi_{m}(x)\cdot\prod_{\begin{subarray}{c}d\mid m\\ d

If $a\in\mathbb{Z}$ with $p\mid\Phi_{m}(a)$, then clearly $p\mid a^{m}-1$ and thus $\gcd(a,p)=1$. In fact, the order (http://planetmath.org/OrderGroup) of $a\mod p$ is precisely $m$, for if it were not, say $a^{d}\equiv 1\pmod{p}$ for $d, then $a$ would be a root $\mod p$ of $\Phi_{d}(x)$ and thus $x^{m}-1$ would have multiple roots $\mod p$, which is a contradiction. But then, by Fermat’s little theorem, we have $a^{p-1}\equiv 1\pmod{p}$, so since $m$ is the least integer with this property, we have $m\mid p-1$ so that $p\equiv 1\pmod{m}$.

We have thus shown that if $p\nmid m$ and $p\mid\Phi_{m}(a)$, then $p\equiv 1\pmod{m}$. The result then follows from the following claim: if $f(x)\in\mathbb{Z}[x]$ is any polynomial of degree at least one, then the factorizations of

 $f(1),f(2),f(3),\ldots$

contain infinitely many primes. The proof is to Euclid’s proof of the infinitude of primes. Assume not, and let $p_{1},\ldots,p_{k}$ be all of the primes. Since $f$ is nonconstant, choose $n$ with $f(n)=a\neq 0$. Then $f(n+ap_{1}\cdot p_{2}\cdots p_{k}x)$ is clearly divisible by $a$, so $g(x)=a^{-1}f(n+ap_{1}\cdot p_{2}\cdots p_{k}x)\in\mathbb{Z}[x]$, and $g(m)\equiv 1\pmod{p_{1}\cdots p_{k}}$ for each $m\in\mathbb{Z}$. $g$ is nonconstant, so choose $m$ such that $g(m)\neq 1$. Then $g(m)$ is clearly divisible by some prime other that the $p_{i}$ and thus $f(n+ap_{1}\cdot p_{2}\cdots p_{k}x)$ is as well. Contradiction.

Thus the set $\Phi_{m}(1),\Phi_{m}(2),\ldots$ contains an infinite number of primes in their factorizations, only a finite number of which can divide $m$. The remainder must be primes $p\equiv 1\pmod{m}$.

Title there are an infinite number of primes $\equiv 1\penalty 0@\mskip 12.0mu {\symoperators mod}\tmspace+{.1667em}\tmspace% +{.1667em}m$ ThereAreAnInfiniteNumberOfPrimesequiv1modM 2013-03-22 17:43:02 2013-03-22 17:43:02 rm50 (10146) rm50 (10146) 7 rm50 (10146) Theorem msc 11N13 SpecialCaseOfDirichletsTheoremOnPrimesInArithmeticProgressions