Advanced book on Mathematics Olympiad

5.2 Arithmetic 265

Here are more examples.

769.For each positive integern, find the greatest common divisor ofn!+1 and(n+ 1 )!.

770.Prove that there are no positive integersnsuch that the set{n, n+ 1 ,n+ 2 ,n+
3 ,n+ 4 ,n+ 5 }can be partitioned into two sets with the product of the elements of
one set equal to the product of the elements of the other set.

771.Letpbe an odd prime. Show that if the equationx^2 ≡a(modp)has no solution
thena
p− 21
≡− 1 (modp).

772.Letpbe an odd prime number. Show that the equationx^2 ≡− 1 (modp)has a
solution if and only ifp≡ 1 (mod 4).

773.Letpbe a prime number andnan integer with 1≤n≤p. Prove that

(p−n)!(n− 1 )!≡(− 1 )n(modp).

774.Letpbe an odd prime anda 1 ,a 2 ,...,apan arithmetic progression whose common
difference is not divisible byp. Prove that there exists an indexisuch that the
numbera 1 a 2 ···ap+aiis divisible byp^2.

5.2.6 Euler’s Totient Function...................................

Euler’s totient function associates to a positive integernthe numberφ(n)of positive
integers less than or equal tonthat are coprime ton. It has a simple formula in terms of
the prime factorization ofn.

Proposition.If the distinct prime factors ofnarep 1 ,p 2 ,...,pk, then

φ(n)=n

(

1 −

1

p 1

)(

1 −

1

p 2

)

···

(

1 −

1

pk

)

.

Proof.This is just an easy application of the inclusion–exclusion principle. From then
numbers between 1 andn, we eliminate then/pinumbers that are divisible bypi, for
each 1≤i≤n. We are left with

n−n

(

1

p 1

+

1

p 2

+···+

1

pk

)

numbers. But those divisible by bothpiandpjhave been subtracted twice, so we have
to add them back, obtaining

n−n

(

1

p 1

+

1

p 2

+···+

1

pk

)

+n

(

1

p 1 p 2

+

1

p 3

+···+

1

pk− 1 pk

)

.