Maths Olympiad Prep

Library / /9 of 28

Number theory Difficulty 7.6 National Olympiad, round 2 Prove it Hong Kong

a. Let aa, nn, kk be positive integers. Prove that a4n+ka^{4n+k} and aka^k have identical first (rightmost) digits in their decimal representations.

b. Find the first digit of the decimal representation of the number
21999+71999+91999. 2^{1999} + 7^{1999} + 9^{1999}.

Solution

a. By the Euler-Fermat theorem, since φ(10)=4\varphi(10) = 4 and 4n+kk(mod4)4n + k \equiv k \pmod{4}, we have
a4n+kak(mod10) a^{4n+k} \equiv a^k \pmod{10}
for any positive integers aa, nn, kk. This means a4n+ka^{4n+k} and aka^k have the same rightmost digit.

b. The rightmost digit is 00.
By part (a), since 19993(mod4)1999 \equiv 3 \pmod{4}, we have
21999+71999+9199923+73+938+3+90(mod10). 2^{1999} + 7^{1999} + 9^{1999} \equiv 2^3 + 7^3 + 9^3 \equiv 8 + 3 + 9 \equiv 0 \pmod{10}.
This shows the rightmost digit of the given number is 00.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.