A question about modulo with high number

Question

The question I got is

$$ 42^{27} \bmod 55 $$ And the answer I got is like this

$$ 42(42^{2})^{13} \bmod 55 \\42(1764)^{13} \bmod 55 \\42(4)^{13} \bmod 55 \\42(67108864) \bmod 55 \\42(9) \bmod 55 \\378 \bmod 55 \\ 48 \bmod 55 $$

So on the third/fifth step, why $1764$ turn into $4$ and why $67108864$ turns into $9$?

I have already read others similar question but still don't get the idea about what is happening

Answer 1

They used $\ 1764\equiv 4\pmod{55}\ $ and the Congruence Product & Power Rules.. Ditto for $\, 4^{\large 13}\!\equiv 9.\ $

Generally congruence is preserved by replacing aguments of sums and products by any congruent argument, e.g. see the Polynomial Congruence Rule in the above linked answer.

I just don't know how to deal with a big number

CRT = Chinese Remainder Theorem helps by reducing to smaller moduli. Applying CRT here along with modular order reduction of exponents we obtain by easy mental arithmetic

$\!\bmod 5\!:\ \ \ \ \ \ \ \ \ \ 2^{\large 4} \equiv 1\, \Rightarrow\ 42^{\large 27}\ \ \equiv\ \ \ 2^{\large\color{#c00}{27}}\ \ \,\equiv\,\ \ 2^{\large\color{#c00} 3}\ \equiv\ \color{#0a0}3,\ \ $ by $\ \ \color{#c00}{27\equiv 3}\pmod{4}$

$\!\bmod 11\!:\,\ (-2)^{\large 5} \equiv 1\, \Rightarrow\, 42^{\large 27 }\equiv (-2)^{\large{27}} \equiv (-2)^{\large 2} \equiv \color{#90f}4,\, \ \ $ by $\ \ 27\equiv 2\pmod{5}$

Thus applying easy CRT: $ \ \ \ 42^{\large 27} \equiv \color{#90f}4 + 11\left[\dfrac{\color{#0a0}3-\color{#90f}4}{11} \bmod 5\right]\equiv 4+11[-1]\equiv -7\equiv 48\pmod{\!55}$

By reducing the moduli to $5$ & $11$ we can now do the arithmetic in a couple minutes purely mentally.

Answer 2

Another way:

Using http://mathworld.wolfram.com/CarmichaelFunction.html,

$\lambda(55)=20$

As $(42,55)=1,27\equiv7\pmod{20}$

$42^{27}\equiv42^7\pmod{55}$

Now $42^2\equiv4\pmod{55}$

$\implies42^7=42(42^2)^3\equiv(-13)(2^2)^3\pmod{55}$

$\equiv(-13)9\equiv-117\equiv-117+3\cdot55$

Answer 3

In the ring $\mathbb Z/55\mathbb Z$ we have

$42^{27}=(-13)^{27}=-13^{27}$

$13^2=169=4\Rightarrow13^{27}=4^{13}\cdot13=9\cdot13=7$.

Thus $$42^{27}=-7=48$$