14
$\begingroup$

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

  • 0
    Yeah, there are easy procedures for a^b mod c2012-02-13

3 Answers 3

18

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

  • 0
    +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.2012-02-13
4

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); } }  
  • 0
    Uh-ok,not as mathematically impressive as mercio's, but that's creative and works,too..........LOL2012-02-13
4

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$