Maths Olympiad Prep

Library / /49 of 75

Number theory Difficulty 5.4 AIME, harder Prove it Italy

Problem:
Prove that all powers of 33 have an even tens digit.

Solution

Solution:
Let r(k)r(k) be the remainder of 3k3^{k} upon division by 2020. In order to prove the claim, it is sufficient to show that for every natural number kk one has r(k)<10r(k)<10. It is clear that 3r(k)3 \cdot r(k) and r(k+1)r(k+1) have the same remainder upon division by 2020: one thus has r(0)=1r(0)=1, r(1)=3r(1)=3, r(2)=9r(2)=9, r(3)=7r(3)=7, r(4)=r(0)=1r(4)=r(0)=1, r(5)=r(1)=3r(5)=r(1)=3, ,\ldots, and the sequence of the r(k)r(k) turns out to be periodic with period 44. It follows that the condition r(k)<10r(k)<10 is satisfied by every natural number kk, since it is satisfied by the first 44, and the claim is proved.

Alternative solution:
The units digit of a number of the form 3k3^{k} necessarily belongs to the set {1,3,7,9}\{1,3,7,9\}, since such a number is odd and not divisible by 55. We then proceed by induction on kk: the claim is true in the case k=0k=0; assuming that the tens digit of 3k3^{k} is yy, the tens digit of 3k+13^{k+1} coincides with the units digit of 3y3y or of 3y+23y+2, hence it is even by the induction hypothesis.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty) added by this project.