38 1. Elementary Prime Number Theory, I

16. (Continuation; Kronecker [Kro88], Dirichlet, Bauer [Bau06]) Define

Φm(X, Y ) as the homogenization of Φm(T), so that

Φm(X, Y ) =

ζm=1

ζj

=1 if 1 ≤ j m

(X − ζY ).

(a) Suppose m 2. Show that Φm(X + Y, X − Y ) = Gm(X, Y

2)

for

some polynomial Gm (say) with integer coeﬃcients. Show also that

d|m

dµ(m/d)

is the coeﬃcient of

Xϕ(m)

in Φm(X + Y, X − Y ).

(b) Let F be a field of characteristic not dividing m. Suppose s is a

nonsquare integer, and let

√

s denote a fixed square root of s from

the algebraic closure of F . Show that the roots of Gm(T, s) ∈ Z[T]

in the algebraic closure of F are precisely the elements

√

s

ζ + 1

ζ − 1

,

where ζ runs through the primitive mth roots of unity.

(c) Suppose s is as in (b), and let p be a prime for which p(s2ms. Show

that p is a prime divisor of Gm(T, s) if and only if p ≡

p

)

(mod m).

(d) Show that if p ≡ −1 (mod 4) is a prime divisor of Gm(T, −1) which

does not divide m, then p ≡ −1 (mod m). Use Exercise 14 to

show that Gm(T, −1) has infinitely many such prime divisors, and

deduce that there are infinitely many primes p ≡ −1 (mod m).

17. (M. Hirschhorn [Hir02]) Let p1 p2 p3 · · · denote the sequence of

odd primes.

(a) Let N ∈ N. Prove that the number of odd positive integers ≤ N

which can be written in the form p11

e

· · · pkk

e

does not exceed

k

i=1

log N

log pi

+ 1 (log

(pkN))k

√

2k! pkN.

Hint: Show that (log

u)ku−1/2

≤

(2k/e)k

whenever u ≥ 1. Now

invoke the inequality m! ≥

(m/e)m,

valid for every integer m ≥ 0.

(b) Supposing that p1,...,pk exist (i.e., that there are at least k odd

primes), prove that pk+1 exists and satisfies pk+1 ≤ 4(2k!)pk + 1.

18. Suppose that A is a commutative monoid (written multiplicatively) and

that P is a system of generators for A, so that each element of A can be

written in the form

p∈P

pep

, where each ep ≥ 0 and only finitely many

of the ep are nonzero. (We do not require that this representation be

unique.) Suppose also that there is a function · : A → N with the

following two properties:

(a) · respects multiplication, i.e., ab = a b for all a, b ∈ A.