Number Theory: An Introduction to Mathematics

110 II Divisibility

In other words,

φ(m)=m

∏

p|m

( 1 − 1 /p).

The functionφ(m)was first studied by Euler and is known as Euler’sphi-function
(or ‘totient’ function), although it was Gauss who decided on the letterφ.Gauss(D.A.,
§39) also established the following property:

Proposition 24For any positive integer n,

∑

d|n

φ(d)=n,

where the summation is over all positive divisors d of n.

Proof Letdbe a positive divisor ofnand letSddenote the set of all positive integers
m≤nsuch that(m,n)=d.Since(m,n)=dif and only if(m/d,n/d)=1, the
cardinality ofSdisφ(n/d). Moreover every positive integerm≤nbelongs to exactly
one such setSd. Hence

n=

∑

d|n

φ(n/d)=

∑

d|n

φ(d),

sincen/druns through the positive divisors ofnat the same time asd.

Much of the significance of Euler’s function stems from the following property:

Proposition 25If m is a positive integer and a an integer relatively prime to m, then

aφ(m)≡1modm.

Proof Letc 1 ,...,ch,whereh=φ(m), be the distinct elements ofZ×(m).Aswesaw

in the proof of Proposition 22, the elementsac 1 ,...,achofZ×(m)are just a permu-

tation ofc 1 ,...,ch. Forming their product, we obtainahc 1 ···ch≡c 1 ···chmodm.
Since thec’s are relatively prime tom, they can be cancelled and we are left with
ah≡1modm.

Corollary 26If p is a prime and a an integer not divisible by p, then ap−^1 ≡1modp.

Corollary 26 was stated without proof by Fermat (1640) and is commonly known
as ‘Fermat’s little theorem’. The first published proof was given by Euler (1736), who
later (1760) proved the general Proposition 25.
Proposition 25 is actually a very special case of Lagrange’s theorem that the order
of a subgroup of a finite group divides the order of the whole group. In the present case
the whole group isZ×(m)and the subgroup is the cyclic group generated bya.
Euler gave also another proof of Corollary 26, which has its own interest. For any
two integersa,band any primepwe have, by the binomial theorem,