Advanced book on Mathematics Olympiad

Number Theory 707

Ifn=pα 11 ···pαkk, then

φ(n)=pα 11 −^1 ···pkαk−^1 (p 1 − 1 )···(pk− 1 ).

If at least two of the primesp 1 ,...,pkare odd, thenφ(n)is divisible by 4, so is not
equal tom.
Ifn= 2 α,orn= 2 αpβ, withα>2, thenφ(n)is again divisible by 4, so again
φ(n) =m. The only cases left aren= 2 αpβ, withα=0,α=1, orα=2. In the
first case,

φ(n)=pβ−^1 (p− 1 ).

This impliesp=7, but even then equality cannot hold. For the other two cases,

φ(n)= 2 α−^1 pβ−^1 (p− 1 ).

The equalityφ(n)=mimplies right away thatα=1,p=7, but 7β−^1 ·6 cannot equal
2 · 7 r. Hence the conclusion.

779.Lets= 2 α 5 βt, wheretis coprime to 10. Define

n= 10 α+β

(

10 φ(t)+ 102 φ(t)+···+ 10 sφ(t)

)

.

The sum of the digits ofnis 1+ 1 +···+ 1 =s. By Euler’s theorem, 10φ(t)≡ 1 (modt),
and so 10kφ(t)≡ 1 (modt),k= 1 , 2 ,...,s. It follows that

n≡ 10 α+β( 1 + 1 +···+ 1 )=s· 10 α+β(modt),

sonis divisible byt. This number is also divisible by 2α 5 βand therefore has the desired
property.
(W. Sierpinski) ́

780.To have few residues that are cubes, 3 should divide the Euler totient function of the
number. This is the case with 7, 9, and 13, sinceφ( 7 )=6,φ( 9 )=6, andφ( 13 )=6.
The cubes modulo 7 and 9 are 0,1, and−1; those modulo 13 are 0, 1,−1, 8, and−8.
So let us assume that the equation admits a solutionx, z. Reducing modulo 7, we
find thatx= 3 k+2, withka positive integer. The equation becomes 4· 8 k+ 3 =z^3 .A
reduction modulo 9 implies thatkis odd,k= 2 n+1, and the equation further changes
into 32· 64 n+ 3 =z^3. This is impossible modulo 13. Hence, no solutions.
(I. Cucurezeanu)

781.First solution: Here is a proof by induction onn. The casen=1 is an easy check.
Let us verify the inductive step fromnton+1. We transform the left-hand side as

∑n+^1

k= 1

φ(k)

⌊

n+ 1

k

⌋

=

∑n+^1

k= 1

φ(k)

⌊n

k

⌋

+

n∑+ 1

k= 1

φ(k)

(⌊

n+ 1

k

⌋

−

⌊n

k

⌋)

.