Advanced book on Mathematics Olympiad

5.2 Arithmetic 267

Solution.We show that any subset ofShavingnelements that are pairwise coprime can
be extended to a set withn+1 elements. Indeed, ifNis the product of the elements
of the subset, then since the elements ofSare coprime toa, so must beN. By Euler’s
theorem,

aφ(N)+^1 +aφ(N)− 1 ≡a+ 1 − 1 ≡a(modN).

It follows thataφ(N)+^1 +aφ(N)−1 is coprime toN and can be added toS. We are
done. 

We now challenge you with the following problems.

775.Prove that for any positive integern,
∑

k|n

φ(k)=n.

Herek|nmeanskdividesn.

776.Prove that for any positive integernother than 2 or 6,

φ(n)≥

√

n.

777.Prove that there are infinitely many positive integersnsuch that(φ(n))^2 +n^2 is a
perfect square.

778.Prove that there are infinitely many even positive integersmfor which the equation
φ(n)=mhas no solutions.

779.Prove that for every positive integersthere exists a positive integerndivisible by
sand with the sum of the digits equal tos.

780.Prove that the equation

2 x+ 3 =z^3

does not admit positive integer solutions.

781.Prove for every positive integernthe identity

φ( 1 )

⌊n

1

⌋

+φ( 2 )

⌊n

2

⌋

+φ( 3 )

⌊n

3

⌋

+···+φ(n)

⌊n

n

⌋

=

n(n+ 1 )

2

.

782.Given the nonzero integersaandd, show that the sequence

a, a+d,a+ 2 d,...,a+nd,...

contains infinitely many terms that have the same prime factors.