Maths Olympiad Prep

Library / /6 of 24

, 2003

Number theory Difficulty 5.7 AIME, harder Prove it Canada

Problem:
Find the last three digits of the number 2003200220012003^{2002^{2001}}.

Solution

Solution:
We must find the remainder when 2003200220012003^{2002^{2001}} is divided by 10001000, which will be the same as the remainder when 3200220013^{2002^{2001}} is divided by 10001000, since 20033(mod1000)2003 \equiv 3 \pmod{1000}. To do this we will first find a positive integer nn such that 3n1(mod1000)3^{n} \equiv 1 \pmod{1000} and then try to express 200220012002^{2001} in the form nk+rn k + r, so that
2003200220013nk+r(3n)k3r1k3r3r(mod1000) 2003^{2002^{2001}} \equiv 3^{n k + r} \equiv (3^{n})^{k} \cdot 3^{r} \equiv 1^{k} \cdot 3^{r} \equiv 3^{r} \pmod{1000}
Since 32=1013^{2} = 10 - 1, we can evaluate 32m3^{2m} using the binomial theorem:
32m=(101)m=(1)m+10m(1)m1+100m(m1)2(1)m2++10m. 3^{2m} = (10 - 1)^{m} = (-1)^{m} + 10 m (-1)^{m-1} + 100 \frac{m(m-1)}{2} (-1)^{m-2} + \cdots + 10^{m}.
After the first 3 terms of this expansion, all remaining terms are divisible by 10001000, so letting m=2qm = 2q, we have that
34q120q+100q(2q1)(mod1000) 3^{4q} \equiv 1 - 20q + 100q(2q-1) \pmod{1000}
Using this, we can check that 31001(mod1000)3^{100} \equiv 1 \pmod{1000} and now we wish to find the remainder when 200220012002^{2001} is divided by 100100.
Now 2002200122001(mod100)421999(mod425)2002^{2001} \equiv 2^{2001} \pmod{100} \equiv 4 \cdot 2^{1999} \pmod{4 \cdot 25}, so we'll investigate powers of 22 modulo 2525. Noting that 210=10241(mod25)2^{10} = 1024 \equiv -1 \pmod{25}, we have
21999=(210)19929(1)1995121213(mod25). 2^{1999} = (2^{10})^{199} \cdot 2^{9} \equiv (-1)^{199} \cdot 512 \equiv -12 \equiv 13 \pmod{25}.
Thus 22001413=52(mod100)2^{2001} \equiv 4 \cdot 13 = 52 \pmod{100}. Therefore 200220012002^{2001} can be written in the form 100k+52100k + 52 for some integer kk, so
200320022001352(mod1000)12013+130025241(mod1000) 2003^{2002^{2001}} \equiv 3^{52} \pmod{1000} \equiv 1 - 20 \cdot 13 + 1300 \cdot 25 \equiv 241 \pmod{1000}
using equation (1). So the last 3 digits of 2003200220012003^{2002^{2001}} are 241241.

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.