Number Theory: An Introduction to Mathematics

5 Congruences 111

(a+b)p=

∑p

k= 0

pCkakbp−k,

where the binomial coefficients

pC

k=(p−k+^1 )···p/^1 ·^2 ·····k

are integers. MoreoverpdividespCkfor 0<k<p,sincepdividespCk·k!andis
relatively prime tok! It follows that

(a+b)p≡ap+bpmodp.

In particular,(a+ 1 )p≡ap+1modp, from which we obtain by inductionap≡
amodpfor every integera.Ifpdoes not dividea, the factoracan be cancelled to
giveap−^1 ≡1modp.
The first part of the second proof actually shows thatin any commutative ring R,
of prime characteristic p,the map a→apis a homomorphism:

(a+b)p=ap+bp,(ab)p=apbp.

(As defined in§8 of Chapter I,Rhascharacteristic kifkis the least positive integer
such that the sum ofk1’s is 0, and hascharacteristic zeroif there is no such positive
integer.) By way of illustration, we give one important application of this result.
We s h ow e d i n§3 that, for any primep, the polynomial

Φp(x)=xp−^1 +xp−^2 +···+ 1

is irreducible inQ[x]. The roots inCofΦp(x)are thep-th roots of unity, other
than 1. By a quite different argument we now show that, for any positive integern,the
‘primitive’n-th roots of unity are the roots of a monic polynomialΦn(x)with integer
coefficients which is irreducible inQ[x]. The uniquely determined polynomialΦn(x)
is called then-thcyclotomic polynomial.
Letζbe aprimitive n-th root of unity, i.e.ζn=1butζk =1for0<k <n.
It follows from Corollary 18 thatζ is a root of some monic irreducible polynomial
f(x)∈Z[x] which dividesxn−1. Ifpis a prime which does not dividen,thenζpis
also a primitiven-th root of unity and, for the same reason,ζpis a root of some monic
irreducible polynomialg(x)∈Z[x] which dividesxn−1.
We show first thatg(x)=f(x). Assume on the contrary thatg(x)=f(x).Then

xn− 1 =f(x)g(x)h(x)

for someh(x)∈Z[x]. Sinceζis a root ofg(xp),wealsohave

g(xp)=f(x)k(x)

for somek(x)∈Z[x]. If f ̄(x),...denotes the polynomial inFp[x] obtained from
f(x),...by reducing the coefficients modp,