Question on modulo

Question

Find the last two digits of $3^{2002}$.

How should I approach this question using modulo? I obtained 09 as my answer however the given answer was 43.

My method was as follows:

$2002\:=\:8\cdot 250+2$

$3^{2002}=\:3^{8\cdot 250+2}\:=\:3^{8\cdot 250}\cdot 3^2$

The last two digits is the remainder when divided by 100. Thus we need to compute the sum mod 100.

$3^8\equiv 61\:\left(mod\:100\right)$

Thus,

$3^{2002}=\:3^{8\cdot 250+2}\:=\:3^{8\cdot 250}\cdot 3^2$ $\equiv 61^{250}\cdot 9\:\equiv 61^{5\cdot 50}\cdot 9\equiv \:9\:\left(mod\:100\right)$

Therefore my answer would be 09. Am I doing it the right way?

Thanks in advanced

Answer 1

Observe that $\text{gcd(3,100)} = 1$, by Euler totient formula: $3^{\phi(100)} \cong 1(\mod 100)$. But $\phi (100) = 100\left(1-\dfrac{1}{2}\right)\left(1-\dfrac{1}{5}\right) = 40$. Thus: $3^{40} \cong 1(\mod 100)$. So $3^{2002} = (3^{40})^{50}\cdot 3^2 \cong 1\cdot 9(\mod 100) \cong 9(\mod 100)$. Thus the remainder is $9$ as claimed.

Answer 2

Using Carmichael function, $\lambda(100)=20$

As $(3,100)=1$ and $2002\equiv2\pmod{20},$ $$\implies3^{2002}\equiv3^2\pmod{100}$$

---

$$3^{2002}=(3^2)^{1001}=9^{1001}=(10-1)^{10001}$$

$$=-1+\binom{1001}110\pmod{100}\equiv10010-1\equiv9$$

Answer 3

We have $3^{2000}=(10-1)^{1000}$. By the Binomial Theorem, this is congruent to $1$ modulo $10000$. It follows that $3^{2002}\equiv 9\pmod{10000}$. Thus the last four digits are $0009$.