Find smallest $a \geq 0 \ s.t. \ a \equiv 11^{100} \ (mod \ 15)$

Question

Having a bit of a struggle understanding problems like these.

This problem was presented under the section of Eulers Totient function (I guess I am supposed to use it), and the solution is like this:

$$11^{\phi(15)} \equiv 1 \ (mod \ 15)$$ $$11^8 \equiv 1 \ (mod \ 15)$$ $$(11^8)^{12} \equiv 1^{12} \ (mod 15)$$ $$11^{96} \cdot 11^4 \equiv 1^4 \ (mod \ 15)$$ $a = 1$

Now manipulating exponents is one thing, I can do that. But I don't understand the first line. Why $11^{\phi(15)}$? And how to approach this problem?

Answer 1

The first line is the Euler-Fermat theorem $$n^{\phi(m)}\equiv 1\pmod m\qquad \text{ if }\gcd(n,m)=1$$

---

A different method, using the Chinese Remainder Theorem:

We have $$11^{100}\equiv(-1)^{100}\equiv 1 \pmod 3 $$ and $$11^{100}\equiv(1)^{100}\equiv 1 \pmod 5 $$ and so see that $a01$ works as that makes $a\equiv1\equiv 11^{100}\pmod 3$ and $a\equiv 1\equiv 11^{100}\pmod 5$ and consequently $a\equiv 11^{100}\pmod{15}$.

Answer 2

Another approach: $$11^2=121$$ $$11^2\equiv 1\quad\mathrm{(mod 15)}$$ $$(11^2)^{50}\equiv 1^{50}\quad\mathrm{(mod 15)}$$ $$11^{100}\equiv 1\quad\mathrm{(mod 15)}$$