Advanced book on Mathematics Olympiad

708 Number Theory

The last term in the first sum can be ignored since it is equal to zero. To evaluate the
second sum, we observe that

⌊

n+ 1

k

⌋

−

⌊n

k

⌋

=

{

1ifkdividesn,

0 otherwise.

Therefore,

∑n+^1

k= 1

φ(k)

⌊

n+ 1

k

⌋

=

∑n

k= 1

φ(k)

⌊n

k

⌋

+

∑

k|n+ 1

φ(k).

Using the induction hypothesis and Gauss’ identity

∑

k|nφ(k)=n, we find that this is
equal ton(n 2 +^1 )+(n+ 1 ), which is further equal to the desired answer(n+^1 )(n 2 +^2 ). This
completes the induction, and the solution to the problem.

Second solution: Using the Gauss identity for Euler’s totient function (the first problem
in this section), we can write

n(n+ 1 )

2

=

∑n

m= 1

m=

∑n

m= 1

∑

k|m

φ(k)=

∑n

k= 1

φ(k)

∑n/k

m= 1

1.

This is clearly equal to the left-hand side of the identity from the statement, and we are
done.
(M.O. Drimbe, 200de Identita ̧ ̆ti ̧si Inegalita ̧ ̆ti cu “Partea Întreaga ̆( 200 Identities
and Inequalities about the “Greatest Integer Function’’), GIL, 2004, second solution by
R. Stong)

782.We may assume gcd(a, d)=1,d≥1,a>d. Sinceaφ(d)≡ 1 (modd), it follows
thatakφ(d)≡ 1 (modd)for all integersk. Hence for allk≥1,

akφ(d)= 1 +mkd,

for some positive integersmk. Ifweletnk=amk,k≥1, then

a+nkd=akφ(d)+^1 ,

so the prime factors ofa+nkd,k≥1, are exactly those ofa.
(G. Pólya, G. Szego, ̋Aufgaben und Lehrsätze aus der Analysis, Springer-Verlag, 1964)

783.The customer picks a numberkand transmits it securely to the bank using the
algorithm described in the essay. Using the two large prime numberspandq, the bank
findsmsuch thatkm≡ 1 (mod(p− 1 )(q− 1 )).Ifαis the numerical information that
the customer wants to receive, the bank computesαm(modn), then transmits the answer