Remainder when $11^{2402}$ is divided by $3000$?

Question

What is the remainder when $11^{2402}$ is divided by $3000$? I just came across this question. I am a beginner in number theory. Your help would mean a lot.Thanks!!

Answer 1

Use Euler theorem $$x^{\varphi(n)}\equiv 1 \pmod n$$

in this case $\varphi(3000)=800$ so $$11^{2402}\equiv 11^2 \pmod{3000}$$

Answer 2

Usage of Carmichael function is often more beneficial for composite numbers as $$\lambda(3000)=\cdots=100\implies 11^{100}\equiv1\pmod{3000}$$

and $\displaystyle2402\equiv2\pmod{100}$

Answer 3

As $(3,1000)=1$

$$11^{2402}=(1+10)^{2402}\equiv1+\binom{2402}110^1+\binom{2402}210^2\pmod{1000}$$

$$\equiv1+2\cdot10+\frac{2402\cdot2401}2100\equiv1+20+100$$

$$\implies11^{2402}\equiv121\pmod{1000}\ \ \ \ (1)$$

$$11\equiv-1\pmod3\implies11^{2402}\equiv(-1)^{2402}\equiv1\ \ \ \ (2)$$

$$\implies11^{2402}\equiv1\equiv121\pmod3\ \ \ \ (3)$$

Combining $(1),(3)$ we get $$\implies11^{2402}\equiv121\pmod{3\cdot1000}$$

or apply CRT on $(1),(2)$

Answer 4

If you don't know Euler/Carmichael's theorem then you can instead use the Binomial theorem.

First $\,{\rm mod}\ 1000\!:\ 11^n = (1+10)^n \equiv 1 + 10 n + 100 n(n\!-\!1)/2,\ $ which is $\equiv 1$ if $\,1000$ divides the last two terms, e.g. if $\,100\mid n.\,$ Therefore $\,11^{100}\equiv 1.\,$ Next $\,{\rm mod}\ 3\!:\ 11^2\equiv 2^2\equiv 1,\,$ so $\,11^{2n}\equiv 1.\,$

So $\, 3,1000\mid 11^{100}\!-1\,\Rightarrow\, 3000\mid \color{#0a0}{11^{100}}\!-\color{#c00}1,\,$ so ${\rm mod}\ 3000\!:\ 11^{2402} = 11^2(\color{#0a0}{11^{100}})^{24} \equiv 11^2 \color{#c00}1^{24}\equiv 11^2$