<s>[INST] Modular exponentiation using Euler’s theorem How can I calculate $27^{41}\ \mathrm{mod}\ 77$ as simple as possible?
I already know that $27^{60}\ \mathrm{mod}\ 77 = 1$ because of Euler’s theorem:
$$ a^{\phi(n)}\ \mathrm{mod}\ n = 1 $$
and
$$ \phi(77) = \phi(7 \cdot 11) = (7-1) \cdot (11-1) = 60 $$
I also know from using modular exponentiation that $27^{10} \mathrm{mod}\ 77 = 1$ and thus
$$ 27^{41}\ \mathrm{mod}\ 77 = 27^{10} \cdot 27^{10} \cdot 27^{10} \cdot 27^{10} \cdot 27^{1}\ \mathrm{mod}\ 77 = 1 \cdot 1 \cdot 1 \cdot 1 \cdot 27 = 27 $$
But can I derive the result of $27^{41}\ \mathrm{mod}\ 77$ using $27^{60}\ \mathrm{mod}\ 77 = 1$ somehow?
 [/INST] You can use exponentiation by squaring (all operations are modulo 77):
$27^{41} = 27^{32+8+1} = 27 \cdot 27^8 \cdot (27^8)^4 = (*)$
$\big[ 27^8 = ((27^2)^2)^2 = (36^2)^2 = 64^2 = 15 \big]$
$(*) = 27 \cdot 15 \cdot 15^4 = 27 \cdot 15 \cdot (15^2)^2 = 27 \cdot 15 \cdot 71^2 = 27 \cdot 15 \cdot 36 = 27$
This uses only 7 multiplications instead of 41.
</s>