116 II Divisibility
The general case of Proposition 34 was first proved by Warning (1936), after
the particular case had been proved by Chevalley (1936). As an illustration, the par-
ticular case implies that, for any integersa,b,cand any primep, the congruence
ax^2 +by^2 +cz^2 ≡0modphas a solution in integersx,y,znot all divisible byp.
Ifmis not a prime, thenZ(m)is not a field. However, we now show that the group
Z×(m)is cyclic also ifm=p^2 is the square of a prime.
Letgbe a primitive root ofp. It follows from the binomial theorem that
(g+p)p≡gpmodp^2.Hence, ifgp≡gmodp^2 ,then(g+p)p≡g+pmodp^2. Thus, by replacinggby
g+pif necessary, we may assume thatgp−^1 ≡1modp^2. If the order ofginZ×(p (^2) )is
d,thenddividesφ(p^2 )=p(p− 1 ).Butφ(p)=p−1dividesd,sincegd≡1modp^2
impliesgd≡1modpandgis a primitive root ofp.Sincepis prime andd=p−1,
it follows thatd=p(p− 1 ),i.e.Z×(p (^2) )is cyclic withgas generator.
We briefly state some further results about primitive roots, although we will not use
them. Gauss (D.A.,§89–92) showed thatthe groupZ×(m)is cyclic if and only if
m∈{ 2 , 4 ,pk, 2 pk},wherepis an odd prime andk ∈N. Evidently 1 is a primi-
tive root of 2 and 3 is a primitive root of 4.If g is a primitive root of p^2 ,where p is an
odd prime, then g is a primitive root of pkfor every k∈N;and if g′=gorg+pk,
according as g is odd or even, then g′is a primitive root of 2 pk.
By Fermat’s little theorem, ifpis prime, thenap−^1 ≡1modpfor everya∈Z
such that(a,p)=1. With the aid of primitive roots we will now show that there
exist also composite integersnsuch thatan−^1 ≡1modnfor everya∈Zsuch that
(a,n)=1.
Proposition 35For any integer n> 1 , the following two statements are equivalent:
(i)an−^1 ≡1modn for every integer a such that(a,n)= 1 ;
(ii)n is a product of distinct primes and, for each prime p|n,p− 1 divides n− 1.
Proof Suppose first that (i) holds and assume that, for some primep,p^2 |n.Aswe
have just proved, there exists a primitive rootgofp^2. Evidentlypg. It is easily
seen that there existsc∈Nsuch thata=g+cp^2 is relatively prime ton; in fact we
can takecto be the product of the distinct prime factors ofn, other thanp, which do
not divideg.Sincendividesan−^1 −1, alsop^2 dividesan−^1 −1. Buta, likeg,isa
primitive root ofp^2 , and so its order inZ×(p (^2) )isφ(p^2 )=p(p− 1 ). Hencep(p− 1 )
dividesn−1. But this contradictsp|n.
Now letpbe any prime divisor ofnand letgbe a primitive root ofp.Inthesame
way as before, there existsc∈Nsuch thata=g+cpis relatively prime ton. Arguing
as before, we see thatφ(p)=p−1dividesn−1. This proves that (i) implies (ii).
Suppose next that (ii) holds and letabe any integer relatively prime ton.Ifpis a
prime factor ofn,thenpaand henceap−^1 ≡1modp.Sincep−1dividesn−1,
it follows thatan−^1 ≡1modp. Thusan−^1 −1 is divisible by each prime factor ofn
and hence, sincenis squarefree, also bynitself.
Proposition 35 was proved by Carmichael (1910), and a composite integernwith
the equivalent properties stated in the proposition is said to be aCarmichael number.