there are an infinite number of primes $\equiv 1\mathrm{@}mod+.1667em+.1667emm$

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(modm)$.

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

If $a\in \mathbb{Z}$ with $p\mid {\mathrm{\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 $amodp$ is precisely $m$, for if it were not, say $a^d\equiv 1(modp)$ for , then $a$ would be a root $modp$ of ${\mathrm{\Phi }}_d(x)$ and thus $x^m-1$ would have multiple roots $modp$, which is a contradiction. But then, by Fermat’s little theorem, we have $a^{p-1}\equiv 1(modp)$, so since $m$ is the least integer with this property, we have $m\mid p-1$ so that $p\equiv 1(modm)$.

We have thus shown that if $p\nmid m$ and $p\mid {\mathrm{\Phi }}_m(a)$, then $p\equiv 1(modm)$. 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),\mathrm{\dots }$$

contain infinitely many primes. The proof is to Euclid’s proof of the infinitude of primes. Assume not, and let $p_1,\mathrm{\dots },p_k$ be all of the primes. Since $f$ is nonconstant, choose $n$ with $f(n)=a\ne 0$. Then $f(n+a{p}_1\cdot p_2\mathrm{\cdots }{p}_{k}x)$ is clearly divisible by $a$, so $g(x)=a^{-1}f(n+a{p}_1\cdot p_2\mathrm{\cdots }{p}_{k}x)\in \mathbb{Z}[x]$, and $g(m)\equiv 1(mod{p}_1\mathrm{\cdots }{p}_k)$ for each $m\in \mathbb{Z}$. $g$ is nonconstant, so choose $m$ such that $g(m)\ne 1$. Then $g(m)$ is clearly divisible by some prime other that the $p_i$ and thus $f(n+a{p}_1\cdot p_2\mathrm{\cdots }{p}_{k}x)$ is as well. Contradiction.

Thus the set ${\mathrm{\Phi }}_m(1),{\mathrm{\Phi }}_m(2),\mathrm{\dots }$ 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(modm)$.

Title	there are an infinite number of primes $\equiv 1\mathrm{@}mod+.1667em+.1667emm$
Canonical name	ThereAreAnInfiniteNumberOfPrimesequiv1modM
Date of creation	2013-03-22 17:43:02
Last modified on	2013-03-22 17:43:02
Owner	rm50 (10146)
Last modified by	rm50 (10146)
Numerical id	7
Author	rm50 (10146)
Entry type	Theorem
Classification	msc 11N13
Related topic	SpecialCaseOfDirichletsTheoremOnPrimesInArithmeticProgressions