Maths Olympiad Prep

Library / /1 of 4

Number theory Difficulty 3.5 AMC 10/12 Find the answer Hong Kong

Find the remainder when 19171519^{17^{15}} is divided by 100.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

For convenience we define f(1)=1f(1) = 1 and f(n+2)=(n+2)f(n)f(n + 2) = (n + 2)^{f(n)} for odd positive integers nn. Then the question asks for the last two digits of f(19)f(19).

Since f(13)=13f(11)f(13) = 13^{f(11)} is odd, we have f(15)=15f(13)(1)f(13)=13(mod4)f(15) = 15^{f(13)} \equiv (-1)^{f(13)} = -1 \equiv 3 \pmod 4.

As f(17)=17f(15)f(17) = 17^{f(15)} and the units digits of the powers of 7 (also the powers of 17) follows the pattern 7, 9, 3, 1, 7, 9, 3, 1, which repeats itself every four terms, we conclude that the units digit of f(17)f(17) is the same as that of 17317^3, which is 3.

Finally, if we look at the last two digits of the powers of 19, we will see the pattern 19, 61, 59, 21, 99, 81, 39, 41, 79, 01, 19, 61, which repeats itself every 10 terms. As f(17)f(17) has units digit 3, the last two digits of f(19)=19f(17)f(19) = 19^{f(17)} are the same as those of 19319^3, which are 59.

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 and solution reproduced as published; topic and difficulty added by this site.