Number Theory: An Introduction to Mathematics

5 Congruences 115

The same argument shows that, for an arbitrary fieldK, any finite subgroup of the
multiplicative group ofKis cyclic.
In the terminology of number theory, an integer which generatesZ×(m)is said to be
aprimitive rootofm. Primitive roots may be used to replace multiplications modm
by additions modφ(m)in the same way that logarithms were once used in analysis. If
gis a primitive root ofm, then the elements ofZ×(m)are precisely 1,g,g^2 ,...,gn−^1 ,

wheren=φ(m). Thus for eacha∈Z×(m)we havea≡gαmodmfor a unique index
α( 0 ≤α<n). We can construct a table of these indices once and for all. Ifa≡gα
andb≡gβ,thenab≡gα+β. By replacingα+βby its least non-negative residueγ
modnand going backwards in our table we can determinecsuch thatab≡cmodm.
For any primep, an essentially complete proof for the existence of primitive roots
ofpwas given by Euler (1774). Jacobi (1839) constructed tables of indices for all
primes less than 1000.
We now use primitive roots to prove a general property of polynomials with coef-
ficients from a finite field:

Proposition 34If f(x 1 ,...,xn)is a polynomial of degree less than n in n variables
with coefficients from the finite fieldFp, then the number of zeros of f inFnpis divisible
by the characteristic p. In particular,( 0 ,..., 0 )is not the only zero of f if f has no
constant term.

Proof PutK=Fpandg= 1 −fp−^1 .Ifα=(a 1 ,...,an)is a zero off,then
g(α)=1. Ifαis not a zero off,thenf(α)p−^1 =1andg(α)=0. Hence the number
Nof zeros offsatisfies

N≡

∑

α∈Kn

g(α)modp.

We will complete the proof by showing that

∑

α∈Kn

g(α)= 0.

Sinceghas degree less thann(p− 1 ), it is a constant linear combination of poly-
nomials of the formx 1 k^1 ···xknn,wherek 1 +···+kn<n(p− 1 ). Thuskj<p−1for
at least onej.Since

∑

α∈Kn

ak 11 ···aknn=

(∑

a 1 ∈K

a 1 k^1

)

···

(∑

an∈K

ankn

)

,

it is enough to show thatSk:=

∑

a∈Ka

kis zero for 0≤k<p−1. Ifk=0, then

ak=1andS 0 =p· 1 =0. Suppose 1≤k<p−1andletbbe a generator for the
multiplicative groupK×ofK.Thenc:=bk=1and

Sk=

∑p−^1

j= 1

cj=c(cp−^1 − 1 )/(c− 1 )= 0.