Advanced Modular Arithmetic #2

We are going to prove some facts before we start figuring out the answer.

---

Fact 1.

Know that $2^{11}=2048$ and $2^3=8$ .

Divide each of them by $40$ and you'll see they have the same remainder.

So we can say that $2^{11}\equiv2^3 \pmod {40}$ .

Then, for positive integer $n$ and $p\geq3$ ,

$\boxed{2^{8n+p}\equiv2^p \pmod{40}}$

---

Fact 2.

Know that $3^5=243\equiv-7\pmod{50}$ .

Then you'll see $3^{10}=(3^5)^2\equiv7^2\equiv-1\pmod{50}$ .

Therefore, for positive integer $n$ ,

$\boxed{3^{10n}\equiv(-1)^n\pmod{50}}$

---

Fact 3.

Know that $76^2=5776\equiv776\pmod{1000}$ .

Then you'll see $576^2=500^2+2\times500\times76+76^2\equiv76^2\equiv776\pmod{1000}$ .

$576^3=576^2\times576\equiv776\times576\equiv700\times500+(1000+200)\times76+76^2\equiv200+776\equiv976\pmod{1000}$

Similarly,

$576^4\equiv176\pmod{1000}$

$576^5\equiv376\pmod{1000}$ .

Also, see that $376^2=300\times300+2\times300\times76+76^2\equiv600+776\equiv376\pmod{1000}$ .

Now, we can infer that $376^n\equiv376\pmod{1000}$ .

Therefore, $576^{5n+4}=(576^5)^n\times576^4\equiv376^n\times176\equiv376\times176\equiv176\pmod{1000}$ .

We can see that $4^{10}=2^{20}=(2^{10})^2=24^2=576\pmod{1000}$ .

Therefore, for positive integer $n$ ,

$\boxed{4^{50n+40}\equiv176\pmod{1000}}$

---

Now let's figure out the answer.

Firstly, note that $2001^{2000^{1999^{\cdots}}}\equiv1\pmod{8}$ .

Then for a positive number $k$ , using Fact 1 ,

$2002^{2001^{2000^{\cdots}}}=2002^{8k+1}\equiv2^{8(k-1)+9}\equiv2^9\equiv32\pmod{40}$ .

.

Then for a positive number $m$ , using Fact 2 ,

$2003^{2002^{2001^{\cdots}}}\equiv3^{40m+32}\equiv(3^{10})^{4m+3}\times3^2\equiv(-1)^{4m+3}\times9\equiv-9\equiv41\pmod{50}$ .

.

Then, for a positive number $n$ , using Fact 3 ,

$2004^{2003^{2002^{\cdots}}}\equiv4^{50n+41}\equiv4^{50n+40}\times4\equiv176\times4\equiv704\pmod{1000}$ .

Therefore, $\boxed{N\equiv704\pmod{1000}}$ .

Although @H.M. 유 's solution is faster, I would like to elaborate my solution, by using Euler Totient function here.

We have

$N\equiv 4^{2003^{2002^{...}}} (mod 1000)$

Because $gcd(4,1000) \neq 1$ , so we separate it to

$\begin{cases} N\equiv 0 (mod 8)\\ N\equiv 4^{n_1 \phi(125) +r_1} (mod 125)\\ \end{cases}$

which $n_i$ and $r_i$ are positive integer.

So $\phi(125)=100$ , we get

$N\equiv 4^{100n_1 +r_1} (mod 125)$

Then

$2003^{2002^{2001^{...}}}=100n_1+r_1$

$r_1\equiv 3^{2002^{2001^{...}}}\equiv 3^{n_2 \phi(100) +r_2} \equiv 3^{40n_2 +r_2}(mod100)$

$r_2\equiv 2002^{2001^{2000^{...}}}\equiv 2^{2001^{2000^{...}}} (mod 40)$

Again, since $gcd(2,40)\neq 1$ , separate it to

$\begin{cases} r_2\equiv 0 (mod 8)\\ r_2\equiv 2002^{2001^{2000^{...}}}\equiv 2^{2001^{2000^{...}}}\equiv 2^{4n_3+r_3}(mod 5)\\ \end{cases}$

Last step of this, we knew that $\phi(5)=4$ and $2001^{2000^{1999^{...}}}\equiv 1 (mod 4)$

It leads to,

$\begin{cases} r_2\equiv 0 (mod 8)\\ r_2\equiv 2(mod 5)\\ \end{cases}$

Then by Chinese Remainder Theorem , it gives us $r_2 \equiv 32 (mod 40)$

Then $r_1\equiv 3^{32}\equiv 81^8 \equiv (-19)^8\equiv 19^8 \equiv 361^4 \equiv 61^4 \equiv 39^4\equiv 1521^2 \equiv 21^2\equiv 441\equiv 41 (mod 100)$

Recall that

$\begin{cases} N\equiv 0 (mod 8)\\ N\equiv 4^{n_1 \phi(125) +r_1} (mod 125)\\ \end{cases}$

By solving the second case of that, we have

$\begin{cases} N\equiv 0 (mod 8)\\ N\equiv 79 (mod 125)\\ \end{cases}$

Using Chinese Remainder Theorem again, we approach the answer

$N\equiv \boxed{704} (mod 1000)$

In my approach I have used the Carmichael's Lambda Function .

$\large N=2004^{2003^{2002^{2001^{2000^{1999^{\cdots}}}}}}$

Now, since $gcd(2004,1000)=4\neq1$ , we cannot apply the theory of Carmichael's Lambda Function, directly.

Note that $N\equiv0\mod(8)$ so if we find $N\mod(125)$ , then by Chinese remainder theorum we can get $N\mod(1000)$ .

Now, since $gcd(2004,125)=1$ we can use the Carmichael's Lambda Function.

$\lambda(125)=100$

$\Rightarrow N\equiv2004^{2003^{2002^{\cdots}}\mod100}mod125$

Now again $gcd(2003,100)=1$ , so again we can use $\lambda(100)=20$

$\large\Rightarrow N\equiv2004^{2003^{2002^{2001^{\cdots} }\mod(20)}\mod(100)}\mod(125)$

Again we see that $gcd(2002,20)=2\neq1$ ,so again we cannot apply the theory of Carmichael's Lambda Function.

Note that $2002^{2001^{2000^{\cdots}}}\equiv0\mod(4)$ so, if we find $2002^{2001^{\cdots}}\mod(5)$ , then by Chinese Remainder theorum, we get $2002^{2001^{\cdots} }\mod(20)$ ,Now $2002^{2001^{\cdots}}\equiv2^{2001^{\cdots}}\mod(5)$

$2002^{2001^{\cdots}}\equiv2^{2001^{\cdots}}\mod(5)$

$\Rightarrow2002^{2001^{\cdots}}\equiv2^{2001^{\cdots}}\mod(5)$

$\lambda(5)=4$

$\Rightarrow2002^{2001^{\cdots}}\equiv2^{2001^{2000^{\cdots}}\mod(4)}\mod(5)$

Since $2001^{2000^{\cdots}}\equiv1\mod(4)$

$\Rightarrow2002^{2001^{\cdots}}\equiv2\mod(5)$

So we have

$2002^{2001^{2000^{\cdots}}}\equiv0\mod(4)$

$\text{ }\equiv2\mod(5)$

So by Chinese Remainder theorum:

$2002^{2001^{2000^{\cdots}}}\equiv12\mod(20)$

$\large\Rightarrow N\equiv2004^{2003^{2002^{2001^{\cdots} }\mod(20)}\mod(100)}\mod(125)\equiv2004^{2003^{12}\mod(100)}\mod(125)$

$\equiv2004^{41}\mod(125)\equiv79\mod125$

Finally we have, $N\equiv79\mod(125)$ and $N\equiv0\mod(8)$

So By CRT we conclude $N\equiv\boxed{704}\mod(1000)$