there are an infinite number of primes 1@\symoperatorsmod\tmspace+.1667em\tmspace+.1667emm

This article proves a special case of Dirichlet’s theorem, namely that for any integer m>1, there are an infiniteMathworldPlanetmathPlanetmath number of primes p1(modm).

Let p be an odd prime not dividing m, let Φk(x) be the kth cyclotomic polynomialMathworldPlanetmath, and note that


If a with pΦm(a), then clearly pam-1 and thus gcd(a,p)=1. In fact, the order ( of amodp is precisely m, for if it were not, say ad1(modp) for d<m, then a would be a root modp of Φd(x) and thus xm-1 would have multiple roots modp, which is a contradictionMathworldPlanetmathPlanetmath. But then, by Fermat’s little theorem, we have ap-11(modp), so since m is the least integer with this property, we have mp-1 so that p1(modm).

We have thus shown that if pm and pΦm(a), then p1(modm). The result then follows from the following claim: if f(x)[x] is any polynomialPlanetmathPlanetmath of degree at least one, then the factorizations of


contain infinitely many primes. The proof is to Euclid’s proof of the infinitude of primes. Assume not, and let p1,,pk be all of the primes. Since f is nonconstant, choose n with f(n)=a0. Then f(n+ap1p2pkx) is clearly divisible by a, so g(x)=a-1f(n+ap1p2pkx)[x], and g(m)1(modp1pk) for each m. g is nonconstant, so choose m such that g(m)1. Then g(m) is clearly divisible by some prime other that the pi and thus f(n+ap1p2pkx) is as well. Contradiction.

Thus the set Φm(1),Φm(2), contains an infinite number of primes in their factorizations, only a finite number of which can divide m. The remainder must be primes p1(modm).

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