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$.

Solution 1:

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$.

Solution 2:

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);
}
} 

Solution 3:

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$