Advanced book on Mathematics Olympiad

266 5 Number Theory

Again, we see that the numbers divisible bypi,pj, andplhave been subtracted and then
added back, so we need to subtract these once more. Repeating the argument, we obtain
in the end

n−n

(

1

p 1

+

1

p 2

+···+

1

pk

)

+n

(

1

p 1 p 2

+

1

p 3

+···+

1

pk− 1 pk

)

−···±

n

p 1 p 2 ···pk

.

Factoring this, we obtain the formula from the statement. 

In particular,nis prime if and only ifφ(n)=n−1, and ifn=p 1 p 2 ···pk, where

piare distinct primes, 1≤i≤k, thenφ(n)=(p 1 − 1 )(p 2 − 1 )···(pn− 1 ). Also, ifm

andnare coprime, thenφ(mn)=φ(m)φ(n).

Fermat’s little theorem admits the following generalization.

Euler’s theorem.Letn> 1 be an integer andaan integer coprime ton. Then

aφ(n)≡ 1 (modn).

Proof.The group of unitsZ∗nin the ringZnconsists of the residue classes coprime ton.

Its order isφ(n). By the Lagrange theorem, the order of an element divides the order of

the group. Hence the conclusion.

Here is a more elementary argument. Consider the setS={a 1 ,a 2 ,...,aφ(n)}of all

residue classes modulonthat are coprime ton. Because gcd(a, n)=1, it follows that,

modulon,aa 1 ,aa 2 ,...,aaφ(n)is a permutation ofa 1 ,a 2 ,...,aφ(n). Then

(aa 1 )(aa 2 )···(aaφ(n))≡a 1 a 2 ···aφ(n)(modn).

Since gcd(ak,n)=1, fork= 1 , 2 ,...,φ(n), we can divide both sides bya 1 a 2 ···aφ(n)

to obtainaφ(n)≡ 1 (modn), as desired. 

We apply Euler’s theorem to a problem by I. Cucurezeanu.

Example.Letnbe an even positive integer. Prove thatn^2 −1 divides 2n!−1.

Solution.Letn=m−1, so thatmis odd. We must show thatm(m− 2 )divides
2 (m−^1 )!−1. Becauseφ(m)<m,φ(m)divides(m− 1 )!,so2φ(m)−1 divides 2(m−^1 )!−1.
Euler’s theorem implies thatmdivides 2φ(m)−1. Therefore,mdivides 2(m−^1 )!−1.
Arguing similarly form−2, we see thatm−2 divides 2(m−^1 )!−1 as well. The numbers
mandm−2 are relatively prime, som(m− 2 )divides 2(m−^1 )!−1, as desired. 
A second example comes from the 1997 Romanian Mathematical Olympiad.

Example.Leta>1 be an integer. Show that the set

S={a^2 +a− 1 ,a^3 +a^2 − 1 ,a^4 +a^3 − 1 ,...}

contains an infinite subset whose elements are pairwise coprime.