Number Theory: An Introduction to Mathematics

5 Congruences 109

Proposition 22The setZ×(m)is a commutative group under multiplication.

Proof By Proposition 3(iv),Z×(m)is closed under multiplication. Since multiplication

is associative and commutative, it only remains to show that anya ∈Z×(m)has an

inversea−^1 ∈Z×(m).

The elements ofZ×(m)may be taken to be the positive integersc 1 ,...,chwhich
are less thanmand relatively prime tom, and we may choose the notation so that
c 1 =1. Sinceacj≡ackmodmimpliescj≡ckmodm, the elementsac 1 ,...,ach
are distinct elements ofZ×(m)and hence are a permutation ofc 1 ,...,ch. In particular,
aci≡c 1 modmfor one and only one value ofi. (The existence of inverses also fol-
lows from the B ́ezout identityau+mv=1, since this impliesau≡1modm. Hence
the Euclidean algorithm provides a way of calculatinga−^1 .)

Corollary 23If p is a prime, thenZ(p)is a finite field with p elements.

Proof We already know thatZ(p)is a commutative ring, whose distinct elements are
represented by the integers 0, 1 ,...,p−1. Sincepis a prime,Z×(p)consists of all

nonzero elements ofZ(p).SinceZ×(p)is a multiplicative group, by Proposition 22, it
follows thatZ(p)is a field.

The finite fieldZ(p)will be denoted from now on by the more usual notationFp.
Corollary 23, in conjunction with Proposition 15, implies that ifpis a prime andfa
polynomial of degreen≥1, then the congruence

f(x)≡0modp

has at mostnmutually incongruent solutions modp. This is no longer true if the mod-
ulus is not a prime. For example, the congruencex^2 − 1 ≡0 mod 8 has the distinct
solutionsx≡ 1 , 3 , 5 ,7 mod 8.
Theorderof the groupZ×(m), i.e. the number of positive integers less thanmand rel-
atively prime tom, is traditionally denoted byφ(m), with the convention thatφ( 1 )=1.
For example, ifpis a prime, thenφ(p)= p−1. More generally, for any positive
integerk,

φ(pk)=pk−pk−^1 ,

since the elements ofZ(pk)which are not inZ×(pk)are the multiplesjpwith 0≤j<

pk−^1. By Proposition 4, ifm=m′m′′,where(m′,m′′)=1, thenφ(m)=φ(m′)φ(m′′).
Together with what we have just proved, this implies that if an arbitrary positive integer
mhas the factorization

m=pk 11 ···pkss

as a product of positive powers of distinct primes, then

φ(m)=p 1 k^1 −^1 (p 1 − 1 )···pkss−^1 (ps− 1 ).