Advanced book on Mathematics Olympiad

706 Number Theory

775.We use strong induction. The property is true forn=1. Letn=pαq, wherepis
a prime number andqis relatively prime top(qis allowed to be 1). Assume that the
formula holds forq. Any numberkthat dividesnis of the formpjm, where 0≤j≤α,
andmdividesq. Hence we can write

∑α

j= 0

∑

m|q

φ(pjm)=

∑α

j= 0

∑

m|q

φ(pj)φ(m)=

∑α

j= 0

φ(pj)

∑

m|q

φ(m)

=

⎛

⎝ 1 +

∑α

j= 1

pj−^1 (p− 1 )

⎞

⎠q=pαq=n.

This completes the induction.
(C.F. Gauss)

776.Ifn= 2 m,m≥2, then

φ(n)= 2 m− 2 m−^1 = 2 m−^1 ≥

√

2 m=

√

n.

Ifn=pm, wherem≥2 andpis an odd prime, then

φ(n)=pm−^1 (p− 1 )≥

√

pm=

√

n.

Observe, moreover, that ifn=pm,m≥2, wherepis a prime greater than or equal to
5, thenφ(n)≥

√

2 n.

Now in general, ifnis either odd or a multiple of 4, then

φ(n)=φ(pα 11 )···φ(pkαk)≥

√

pα 11 ···

√

pαkk=

√

n.

We are left with the casen= 2 t, withtodd and different from 1 or 3. If any prime
factor oftis greater than or equal to 5, thenφ(n)=φ(t)≥

√

2 t. It remains to settle the
casen= 2 · 3 i,i≥2. Fori=2,φ( 18 )= 6 >

√

18. Fori≥3,φ(n)= 2 · 3 i−^1 , and
    the inequality reduces to

√

2 · 3

i 2 − 1

>1, which is obvious.

777.An example isn=15. In that caseφ( 15 )=φ( 3 · 5 )= 2 · 4 =8, and 8^2 + 152 = 172.
Observe that forα, β≥1,

φ( 3 α· 5 β)= 3 α−^1 · 5 β−^1 ( 3 − 1 )( 5 − 1 )= 3 α−^1 · 5 β−^1 · 8

and

( 3 α−^1 · 5 β−^1 · 8 )^2 +( 3 α· 5 β)^2 =( 3 α−^1 · 5 β−^1 · 17 )^2 ,

so any number of the formn= 3 α· 5 βhas the desired property.

778.We will prove that ifm= 2 · 7 r,r≥1, then the equationφ(n)=mhas no solutions.