9. Primes represented by general polynomials 25
those d dividing m, we have (1.11). Applying M¨ obius inversion to (1.11)
say. Now F and G are monic polynomials in Z[T] with G = 0, and so we
(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 ∈
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 |
− 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
Φ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
− 1 has a zero of order ≥ 2 over Z/pZ. But T
− 1 has no multiple
roots over Z/pZ, since T
− 1 has no roots in common with its derivative
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.).