# Find The Last 3 digits of the number $2003^{2002^{2001}}$

Find The Last 3 digits of the number $2003^{2002^{2001}}$

BY number theory or otherwise,

Also i would like to ask is there a property observed in the numbers of the form $k^n$, where for some $k, n$ is varied then the digits of $k^n$ are periodic,

for example,

$2^n$, its last digit is periodic with period 4, its second last digit is periodic $4\cdot 5 = 20$ its third last digit is periodic with periodic with period $20\cdot 5 =100$

I have observed this property with other numbers as well, though period might vary,for different values of $k$.

-
Just so we're clear about it, does 2003^2002^2001 mean $2003^{2002^{2001}}$ or $(2003^{2002})^{2001}$? –  lhf Feb 13 '12 at 13:12
do you know modular arithmetic (see for example here: link)? problems like this are pretty easy if you consider them modulo $10^k$ –  user20388 Feb 13 '12 at 13:14
@lhf i meant the former and not the latter, thanks for noticing –  Tomarinator Feb 13 '12 at 13:17
@s6robat no i donot know modular mathematics, –  Tomarinator Feb 13 '12 at 13:18
Start by noting that $2003 \equiv 3 \mod 1000$. So the last three digits of $2003^{2002^{2001}}$ are the same as the last three digits of $3^{2002^{2001}}$. Now consider the last three digits of powers of 3. –  lhf Feb 13 '12 at 13:19

First, $2003^n \equiv 3^n \mod 1000$.

$3$ is invertible modulo $1000$. The group of invertibles of $\mathbb{Z}/1000\mathbb{Z}$, $(\mathbb{Z}/1000\mathbb{Z})^\times$ has cardinality $\varphi(1000) = 1000 * 1/2 * 4/5 = 400$. This implies that $3^{400} \equiv 1 \mod 1000$, and so $3^n \equiv 3^{n \mod 400} \mod 1000$.

So in order to comptute $2003^{2002^{2001}} \mod 1000$, we need to know $2002^{2001} \mod 400$. $2002^n \equiv 2^n \mod 400$. This time, $2$ is not invertible modulo $400 = 2^4 * 25$. For $n \geq 4$, $2^n$ is always a multiple of $2^4$, so $2^n \mod 400 = (2^4*2^{n-4}) \mod (2^4*25) = 2^4*(2^{n-4} \mod 25)$.

Now, $2$ is invertible modulo 25, and the group $(\mathbb{Z}/25\mathbb{Z})^\times$ has cardinality $\varphi(25) = 25*4/5 = 20$. This implies that $2^{20} \equiv 1 \mod 25$, and so $2^n \equiv 2^{n \mod 20} \mod 25$.

Putting all of this together, we get : $2002^{2001} \mod 400 = 2^{2001} \mod 400 = 2^4 * (2^{1997} \mod 25) = 2^4 * (2^{1997 \mod 20} \mod 25)$ $=2^4 * (2^{17} \mod 25) = 2^4 * (131072 \mod 25) = 2^4 * 22 = 352$.

And finally $2003^{2002^{2001}} \mod 1000 = 3^{352} \mod 1000 = 241$.

-
+1 Looks good to me. Can't check everything, for I honestly cannot parse an expression, where mod is used as a binary operation. But the theory is sound. –  Jyrki Lahtonen Feb 13 '12 at 14:35
It is also worthy of mentioning that as a final step $3^{352} = 3^{52} \pmod{1000}$ since $3^{100} = 1 \pmod{1000}$. This follows from the fact that $\lambda(1000) = 100$ where $\lambda$ is the Carmichael Function. –  aelguindy Feb 13 '12 at 14:42
+1 for this beautiful calculation and terrific use of Lagrange's little theorem. It'll be interesting to see what other methods the others at the board come up with and which are better for hand computation. –  Mathemagician1234 Feb 13 '12 at 17:53

I wrote small Java code (see below) . According to it's calculation last three digits are $~241~$ .

import java.math.BigInteger;
public class LastThreeDigits
{
public static void main(String[] args)
{
int a = 2001;
BigInteger b = new BigInteger ("2002");
BigInteger n = new BigInteger ("2003");
BigInteger exponent;
exponent = b.pow(a);
BigInteger mod = new BigInteger ("1000");
BigInteger result = n.modPow(exponent,mod);
System.out.println("Result is  ==> " + result);
}
}

-
Uh-ok,not as mathematically impressive as mercio's, but that's creative and works,too..........LOL –  Mathemagician1234 Feb 13 '12 at 17:57

We have $\displaystyle2003^{(2002^{2001})}\equiv3^{(2002^{2001})}\pmod{1000}$

Using Carmichael Function, $\displaystyle\lambda(1000)=100$

So, $\displaystyle 3^{(2002^{2001})}\equiv3^{(2002^{2001}\pmod{100})}\pmod{1000}$

Now, $\displaystyle 2002^{2001}\pmod{100}\equiv2^{2001}\pmod{100}$

As $\displaystyle(2^{2001},100)=2^2,$ we start with $\displaystyle2^{2001-2}\pmod{\frac{100}{2^2}}$ i.e., $\displaystyle2^{1999}\pmod{25}$

As $\displaystyle\phi(25)=20,2^{20}\equiv1\pmod{25},$

$\displaystyle2^{2000}\equiv1\pmod{25}\implies\displaystyle2^{1999}\equiv2^{-1}$

As $\displaystyle2\cdot13=26\equiv1\pmod{25},2^{1999}\equiv13$

$\displaystyle\implies2^{2001}=2^2\cdot2^{1999}=2^2\cdot13\pmod{2^2\cdot25}\equiv52$

$\displaystyle\implies3^{(2002^{2001})}\equiv3^{52}\pmod{1000}$

Now, $\displaystyle3^{52}=(3^2)^{26}=(10-1)^{26}=(1-10)^{26}\equiv1-\binom{26}110+\binom{26}210^2\pmod{1000}$

Again, $\displaystyle\binom{26}2=\frac{26\cdot25}2=13\cdot25=325\equiv5\pmod{10}$

$\displaystyle\implies(1-10)^{26}\equiv1-260+5\cdot10^2\pmod{1000}\equiv1-260+500$

-