An easy way to calculate $12^{101} \bmod 551$? We learn about encryption methods, and in one of the exercises we need to calculate: $12^{101} \bmod 551$.
There an easy way to calculate it?
We know that: $M^5=12 \mod 551$
And $M^{505}=M$ ($M\in \mathbb{Z}_{551}$).
(Our goal is to find $M$).
I try to use Fermat, Euler but they can't help me here, right?
P.S. - The idea is to calculate it without calculator...
Thank you!
 A: If I asked you to find $12^{2^6} \pmod{551}$, will you be able to do it relatively quickly using an ordinary calculator? If so, then you might be able to see how to reduce other exponents to powers of $2$.
A: If the goal is to find  $M$, given $M^5\equiv 12\mod 551$, as $551=19\times 29$, it is the same as solving $$M^5\equiv 12\mod 19, \quad M^5\equiv 12\mod 29.$$
Now by Little Fermat, we have:
$$M^{18}=M^{15}M^3\equiv 12^3M^3\equiv1\mod19,\quad M^{28}=M^{25}M^3\equiv 12^5M^3\equiv1\mod29$$
Let $N=12M$. We obtain the congruences:
$$N^3\equiv 1\mod19,\quad 12^2N^3\equiv-N^3\equiv 1\mod 29$$
Itis easy to check the first congruence has $3$ roots: $\; N\equiv 1,7,11\mod19$, while the second has only $1$; $\;N\equiv-1\mod29$.
By the Chinese Remainder Theorem, to solve for $N$, we start from a Bézout's identity: $2\cdot29-3\cdot 19=1$, whence:
$$N\equiv\begin{cases}
2\cdot1\cdot29+3\cdot 19\equiv 115\\
2\cdot7\cdot29+3\cdot 19\equiv463\\
2\cdot11\cdot29+3\cdot 19\equiv144
 \end{cases}\mod551$$
We go back to $M$, computing the inverse of $12$ modulo $551$ by the Extended Euclidean algorithm $12^{-1}\equiv 46\mod 551$, so that finally:
$$M\equiv 331, 360\enspace\text{or}\enspace12\mod551.$$
A: As $551=19\cdot29,$
As $12^2\equiv-1\pmod{29},12^{101}=12(12^2)^{50}\equiv12(-1)^{50}\pmod{29}$
$\implies12^{101}\equiv12\pmod{29}\  \ \ \ (1)$
For modulo $19,12\equiv-7\implies12^{101}\equiv(-7)^{101}=-7^{101}$
Now $7^2=49\equiv11,11^2=121\equiv7\implies7^4\equiv7\iff7^3\equiv1$ as $(7,19)=1$
$\implies7^{101}=7^2(7^3)^{33}\equiv11\cdot1^{33}\equiv-8$
$\implies12^{101}\equiv-(-8)\equiv8\pmod{19}\  \ \ \ (2)$
As $(19,29)=1,$ apply Chinese Remainder Theorem on $(1),(2)$
