What are the possible remainders when the $110^{th}$ power of an integer is divided by $121$?

Question

I was checking the following Euler's theorem exercise:

What are the possible remainders when the $110^{th}$ power of an integer is divided by $121$?

I've started working from calculating $\phi (110) = 40$

Now I'm thinking about applying $\mod 121$ but I'm unable to. So now I'm maybe in the wrong way. Any help or clue will be really appreciated.

Answer 1

We need $\phi(121)=11\cdot10\implies a^{110}\equiv1\pmod{121}$ for $11\nmid a\iff(a,11)=1$

What if $11\mid a?$

Answer 2

$\phi (110)$ is utterly irrelevent.

Euler's theorem tells us about $a^k \pmod {n}$ and how $k$ and $\phi(n)$ relate.

$\phi (k)$ has got sod all to do with fish and fishsticks.

So we want to know how $110$ and $\phi(121)= \phi(11^2) = 11(11-1)$ relate.

How do they relate?

....

So we can break your task into the following.

1) Figuring out what $\phi(121)=\phi(11^2) = 11(11-1)$ is.

2) Figuring how $110$ relates to $\phi(121)$. In particular what $100 \mod \phi(121)$ is.

3) Figuring if $\gcd(a,121)=1$ then what is $110 \pmod {\phi(121)}\equiv a^{(110 \%{\phi(121)})}$ are for the different values of $a$ so that $\gcd(a,121) = 1$.

4) Figure out what happens when $\gcd(a,121) \ne 1$.

Now as the prime factorization of $121 = 11^2$ and $\phi(11^2) = 11(11-1)$.....

Those become fairly easy questions.