Question

Find the last $3$ digits of the numbers ${2003}^{{2002}^{2001}}$

Answer 1

Given

${2003}^{{2002}^{2001}}$

$2003\equiv 3mod1000$

SO

$3^{\left({2002}^{2001}\right)}mod1000$.

$\lambda \left(1000\right)=1000(1-\frac{1}{2})(1-\frac{1}{5})=400$.

So $3^{400}\equiv 1mod1000$.

So we need to find

${2002}^{2001}mod400$.

$2002\equiv 2mod400$, so we find

$2^{2001}mod400$.

$\lambda \left(400\right)=400(1-\frac{1}{2})(1-\frac{1}{5})=160$.

So $2^{160}\equiv 1mod400$.

$2001=160\times 12+81$ so $2^{2001}mod400$ is congruent to

$2^{81}mod400$.

$400=25\times 16$, and

$2^{81}mod16\equiv 0$ (as $2^4=16$)

$2^{81}mod25\equiv 2mod25$ (as $\lambda \left(25\right)=20$).

The only number less than 400 that is 2 more than a multiple of 5, and divisible by 16 is 352. Therefore,

$2^{81}mod400=352$.

So

$3^{\left({2002}^{2001}\right)}\equiv 3^{352}mod1000$.

$1000=125\times 8$

$\lambda \left(8\right)=4\to 3^4\equiv 1mod8$

$\Rightarrow 3^{352}\equiv 3^{(4\times 88)}\equiv 1mod8$.

$\lambda \left(125\right)=100\to 3^{100}\equiv 1mod125$

$\Rightarrow 3^{352}mod125\equiv 3^{52}mod125$.

$3^{52}mod125$

$\equiv 9^{26}mod125$

$\equiv {81}^{13}mod125$

${81}^2\equiv 6561\equiv 61mod125$

${61}^2\equiv 3721\equiv 96mod125$

So

${81}^{13}mod125$

$\equiv 81\times {81}^{12}mod125$

$\equiv 81\times ({81}^4{)}^{3}mod125$

$\equiv 81\times {96}^{3}mod125$

${96}^2\equiv 9216\equiv 91mod125$

and

$81\times 96\equiv 7776\equiv 26mod125$

so

$81\times {96}^{3}mod125$

$\equiv 26\times 91mod125$

$\equiv 2366mod125$

$\equiv 116mod125.$

The only number simultaneously of the form 8k + 1 and 125m + 116 that is also less than 1000 is 241. Thus

$3^{352}mod1000\equiv 241$

Hence answer is $241$