112 II Divisibility
then
xn− 1 =f ̄(x)g ̄(x)h ̄(x), g ̄(xp)=f ̄(x)k ̄(x).Butg ̄(xp)= ̄g(x)p,sinceFp[x] is a ring of characteristicpandap=afor every
a∈Fp. Hence any irreducible factore ̄(x)off ̄(x)inFp[x] also dividesg ̄(x). Con-
sequentlye ̄(x)^2 dividesxn−1inFp[x]. Butxn−1 is relatively prime to its formal
derivativenxn−^1 ,sincepn, and so is square-free. This is the desired contradiction.
By applying this repeatedly for the same or different primesp, we see thatζmis
a root off(x)for any positive integermless thannand relatively prime ton.Ifωis
anyn-th root of unity, thenω=ζkfor a uniqueksuch that 0≤k<n.If(k,n)=1,
thenωd=1 for some proper divisordofn(cf. Lemma 31 below). If such anωwere a
root off(x),thenf(x)would dividexd−1, which is impossible sinceζis not a root
ofxd−1. Hencef(x)does not depend on the original choice of primitiven-th root
of unity, its roots being all the primitiven-th roots of unity. The polynomialf(x)will
now be denoted byΦn(x).Sincexn−1 is square-free, we have
xn− 1 =∏
d|nΦd(x).This yields a new proof of Proposition 24, sinceΦd(x)has degreeφ(d).
As an application of Fermat’s little theorem (Corollary 26) we now prove
Proposition 27If p is a prime, then(p− 1 )!+ 1 is divisible by p.
Proof Since 1!+ 1 =2, we may suppose that the primepis odd. By Corollary 26,
the polynomialf(t)=tp−^1 −1 has the distinct roots 1, 2 ,...,p−1inthefieldFp.
But the polynomialg(t)=(t− 1 )(t− 2 )···(t−p+ 1 )has the same roots. Since
f(t)−g(t)is a polynomial of degree less thanp−1, it follows from Proposition 15
thatf(t)−g(t)is the zero polynomial. In particular, f(t)andg(t)have the same
constant coefficient. Since(− 1 )p−^1 =1, this yields the result.
Proposition 27 is known asWilson’s theorem, although the first published proof
was given by Lagrange (1773). Lagrange observed also that(n− 1 )!+1 is divisible
byn onlyifnis prime. For supposen=n′n′′,where1<n′,n′′<n.Ifn′=n′′,then
bothn′andn′′occur as factors in (n− 1 )! and hencendivides (n− 1 )!Ifn′=n′′> 2
then, sincen> 2 n′, bothn′and 2n′occur as factors in(n− 1 )! and againndivides
(n− 1 )! Finally, ifn=4, thenndivides(n− 1 )!+2.
As another application of Fermat’s little theorem, we proveEuler’s criterion for
quadratic residues.Ifpis a prime andaan integer not divisible byp, we say thata
is aquadratic residue,orquadratic nonresidue,ofpaccording as there exists, or does
not exist, an integercsuch thatc^2 ≡amodp. Thusais a quadratic residue ofpif
and only if it is a square inF×p. Euler’s criterion is the first statement of the following
proposition:
Proposition 28If p is an odd prime and a an integer not divisible by p, then
a(p−^1 )/^2 ≡ 1 or−1modp,according as a is a quadratic residue or nonresidue of p.
Moreover, exactly half of the integers 1 , 2 ,...,p− 1 are quadratic residues of p.