Find number x such that $x\equiv 4^{1002}\pmod{55}$ Find a natural number x, for $0 \le x \le 54$ such that is a solution for the following equation:
$$x\equiv 4^{1002}\pmod{55}$$
This question was asked in an exam, so I expect that the answer is without the use of computers. Any help is appreciated.
 A: Using Carmichael function $\displaystyle\lambda(55)=$lcm$(10,4)=20$
and
$$1002\equiv2\pmod{20}$$
Alternatively, using Euler's totient theorem, $\displaystyle\phi(55)=4\cdot10=40$ and $$1002\equiv2\pmod{40}$$
Either case $$\implies4^{1002}\equiv4^2\pmod{55}$$
A: We have
$$\phi(55)=\phi(5\times11)=4\times10=40\ .$$
Since $4$ is coprime to $55$, Euler's Theorem gives
$$4^{40}\equiv1\pmod{55}$$
and therefore
$$4^{1002}=(4^{40})^{25}4^2\equiv1^{25}4^2\equiv16\pmod{55}\ .$$
Addendum.  If you can't use Euler's Theorem, you can calculate
$$4^1\equiv4\,,\ 4^2\equiv16\,,\ 4^3\equiv64\equiv9\,,\ 4^4\equiv36\pmod{55}$$
and so on; eventually you will find $4^{10}\equiv1$, and then use a method similar to the above.
Possibly a bit simpler: we have
$$4^{1002}\equiv(-1)^{1002}\equiv1\pmod5$$
and
$$4^{1002}\equiv(4^5)^{200}4^2\equiv1^{200}4^2\equiv5\pmod{11}\ .$$
Now solve
$$x\equiv1\pmod5\ ,\quad x\equiv5\pmod{11}$$
by using the Chinese Remainder Theorem.
A: Since the OP asked for a direct proof, note that $4^{3} \equiv 9$ (mod $55$), and that $9^{3} \equiv 14$ (mod $55$). Hence $4^{10} \equiv 4 \times 14 \equiv 1$ (mod $55$), so $4^{1002} \equiv 16$ (mod $55$). Or you can just go through the powers of $4$ one by one (mod $55$), until you notice that $4^{10} \equiv 1$. However, the answers already given illustrate that knowing a little theory can reduce laborious calculation to something much more manageable.
A: Hint $\ \ \begin{eqnarray} {\rm mod}\ 5\!:\ \ \ 2^4\equiv1\,\Rightarrow\, \color{#0a0}{2^{20}}\equiv 1\\ {\rm mod}\ 11\!:\ 2^{10}\equiv1\,\Rightarrow\, \color{#0a0}{2^{20}}\equiv 1\end{eqnarray}\,\color{#c00}\Rightarrow\, {\rm mod}\ 55\!:\ \color{#0a0}{2^{\large 20}}\equiv 1\,\Rightarrow\, 2^{\large 20q+r}\equiv (\color{#0a0}{2^{\large 20}})^{\large q} 2^{\large r}\equiv 2^{\large r}$
where $(\color{#c00}\Rightarrow)$ follows by CRT, $ $ or by $\,5,11\mid 2^{20}\!-1\,\Rightarrow\, 5\cdot 11\mid 2^{20}\!-1,\,$ by $\,{\rm lcm}(5,11) = 5\cdot 11.$
Hence $\ {\rm mod}\ 55\!:\ 4^{\large 1002} = 2^{\large 2004} = 2^{\large 20\cdot 100+4}\equiv 2^{\large 4}$
