9. Primes represented by general polynomials 25

those d dividing m, we have (1.11). Applying M¨ obius inversion to (1.11)

yields

Φm(T) =

d|m

T

d

− 1

µ(m/d)

=

d|m, µ(m/d)=1

(

T

d

− 1

)

d|m, µ(m/d)=−1

(T

d

− 1)

=

F

G

,

say. Now F and G are monic polynomials in Z[T] with G = 0, and so we

can write

(1.12) F = GQ + R,

where Q, R ∈ Z[T] and deg R deg Q. Of course (1.12) remains valid over

C[T] and expresses in that ring one result of division by G. But we know

that over C[T], we have F = GΦm, so that G goes into F with no remainder.

By the uniqueness of quotient and remainder in the division algorithm for

polynomials, we must have R = 0 above. Consequently, Φm = F/G = Q ∈

Z[T].

Lemma 1.19. If p is a prime divisor of Φm, then either p | m or p ≡

1 (mod m).

Proof. If p is a prime divisor of Φm, then p divides Φm(n) for some integer

n. Since the cyclotomic polynomials have integer coeﬃcients, it follows from

(1.11) that p |

d|m

Φd(n) =

nm

− 1, so that the order of n modulo p is a

divisor of m.

Suppose now that p does not divide m. We claim that in this case,

m is the precise order of n modulo p. Thus m divides p − 1, whence p ≡

1 (mod m). To prove the claim, suppose for the sake of contradiction that

f m is the exact order of n mod p. Then f is a proper divisor of m.

Moreover, p divides

nf

−1 =

e|f

Φe(n), so that p divides Φe(n) for some e |

f. Hence the residue class n mod p is a zero of both Φe(T) and Φm(T). The

polynomials Φe and Φm both appear in the factorization (1.11) of T

m

−1, so

that T

m

− 1 has a zero of order ≥ 2 over Z/pZ. But T

m

− 1 has no multiple

roots over Z/pZ, since T

m

− 1 has no roots in common with its derivative

mT

m−1.

Since only finitely many primes divide m, Lemmas 1.17 and 1.19 have

the following corollary:

Corollary 1.20. For each natural number m, there are infinitely many

primes p ≡ 1 (mod m).

This proof of Corollary 1.20 is essentially due to Wendt [Wen95].

How far can one take this algebraic approach? The following result is

due to Schur (op. cit.).