Use Euler’s $ϕ$-function to calculate $121^{1002}$ mod $100$

Question

Use Euler’s $ϕ$-function to calculate $121^{1002}$ mod $100$ without a calculator.

I know that $121^{1002} = (11^2)^{1002}$ = $11^{2004}$

Applying $ϕ$-function to $11^{2004}$, we get $ϕ$ = $11^{2004}-11^{2003}$ = $11^{2003}(11-1)$ = $10 \times 11^{2003}$

And then, how do I continue? Any help please?

Answer 1

Hint:

You're confusing the number to be exponentiated and the modulus.

We need $\varphi(100)==\varphi(2^2)\varphi(5^2)=40$, so $$ 121^{1002}=11^{2004}\equiv 11^{2004\bmod40}\mod 100. $$

Answer 2

By Euler's theorem (a generalization of Fermat's little theorem), if $m\geq 1$ and $\gcd(a,m)=1$, then

$$a^{\phi(m)} \equiv 1 \mod{m}$$

So

$$121^{40}\equiv 1 \mod{100}$$ and raising both sides to the power of 25, we have $$121^{1000} \equiv 1 \mod{100}$$ You should be able to finish from here.

Answer 3

Knowing that $\phi(11^{2004}) = 10*11^{2003}$ won't help you in any way that I can see to calculate what $11^{2004} \pmod {100}$ is.

But Are you familiar with Euler's Theorem that states if $\gcd(a,n) = 1$ then $a^{\phi n}\equiv \pmod {n}$?

So as $\phi(100) =40$ and $\gcd(11,100) = 1$, Euler's Theorem allows us to conclude:

$11^{40} \equiv 1 \pmod {100}$.

Can you take it from there?

$11^{2004} \equiv 11^{40*50 + 4}\pmod {100}$. Can you take it from there?

.

$11^{40*50+4} = (11^{40})^{50}*11^4\equiv 1^{50}*11^4 \pmod {100}$. Can you take it from there?

.

$11^4 = 121^2 = (100 + 21)^2$

Answer 4

In this case the $\phi-$function is not really required because the cycle of powers of $21$ is very short.

Indeed $21^r\equiv 01,21,41,61,81\pmod{100}$ for $r=0,1,2,3,4$

So $121^{1002}\equiv 21^{1002}\equiv 21^{(1002 \mod 5)}\equiv 21^2\equiv 41\pmod{100}$

Answer 5

Alternatively, using binomial theorem: $$121^{1002}\equiv 11^{2004}\equiv (10+1)^{2004}\equiv {2004\choose 1}\cdot 10+1\equiv 41\pmod{100}.$$