An easy way to calculate $12^{101} \bmod 551$?

Question

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!

Answer 1

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$.

Answer 2

$551=19\cdot 29$. Finding $12^{101}\bmod 19,29$ is sufficient, and you can then apply Chinese Remainder Theorem in some form (there are many methods in the Wikipedia page). By little Fermat,

$$12^{101}\equiv 12^{101\pmod{\! 18}}\equiv 12^{11}\pmod{\! 19}$$

$$12^{101}\equiv 12^{101\pmod{\! 28}}\equiv 12^{17}\pmod{\! 29}$$

At this point, you can calculate these already small values, by e.g. repeated squaring with reducing.

More advanced methods such as Euler's criterion with Quadratic reciprocity can speed up the process. Since $19\equiv \pm 5\pmod{\! 12},\, 29\equiv \pm 5\pmod{\! 12}$:

$$12^9 \equiv 12^{(19-1)/2}\equiv\left(\frac{12}{19}\right)\equiv \left(\frac{2^2}{19}\right)\left(\frac{3}{19}\right)\equiv -1\pmod{\! 19}$$

$$12^{14} \equiv 12^{(29-1)/2}\equiv\left(\frac{12}{29}\right)\equiv \left(\frac{2^2}{29}\right)\left(\frac{3}{29}\right)\equiv -1\pmod{\! 29}$$

$$12^{11}\equiv -12^2\pmod{\! 19},\ \ \ 12^{17}\equiv -12^{3}\pmod{\! 29}$$

---

There is not much else you could do other than repeated squaring, if you choose not to use the more advanced methods.

$$12^2\equiv 11,\, 12^4\equiv 11^2\equiv 7,\, 12^8\equiv 11\,\pmod{\! 19}$$

$$12^{11}\equiv 12^{8+2+1}\equiv 11\cdot 11\cdot 12\equiv 8\pmod{\! 19}$$

$$12^2\equiv -1\,\Rightarrow\, 12^{17}\equiv (12^2)^8\cdot 12\equiv (-1)^8\cdot 12\equiv 12\,\pmod{\! 29}$$

Now apply Chinese Remainder theorem, as said before. Wikipedia has many methods. E.g.:

$$x\equiv 8\pmod{\! 19}\iff x=19k+8$$

$$19k+8\equiv 12\pmod{\! 29}\iff -10k\equiv 4$$

$$\stackrel{:(-2)}\iff 5k\equiv -2\equiv -60\stackrel{:5}\iff k\equiv -12\equiv 17\pmod{\! 29}$$

$$x=19(29m+17)+8=551m+331$$

$$12^{101}\equiv 331\,\pmod{\! 551}$$

Answer 3

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.$$

Answer 4

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)$