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?

Solution 1:

If you are serious about "as simple as possible" then observe that $27^{41} = 3^{123}$ and use Carmichael's theorem (a strengthening of Euler's theorem which actually gives a tight bound) to deduce that $3^{30} \equiv 1 \bmod 77$ and hence $3^{123} \equiv 3^3 \equiv 27 \bmod 77$. But I do not think this is the right question to ask; you should really be asking "as general as possible," and then the answer you have accepted is most appropriate.

(Of course it suffices to use Euler's theorem for the above computation, but few people seem to learn Carmichael's theorem and I always like to point it out when I can.)

Solution 2:

As suggested in the comment above, you can use the Chinese Remainder Theorem, by using Euler's theorem / Fermat's theorem on each of the primes separately. You know that $27^{10} \equiv 1 \mod 11$, and you can also see that modulo 7, $27 \equiv -1 \mod 7$, so $27^{10} \equiv (-1)^{10} \equiv 1\mod 7$ as well. So $27^{10} \equiv 1 \mod 77$, and $27^{41} = 27^{40+1} \equiv 27 \mod 77$. (We've effectively found the order of 27 as 10, but a more mechanical procedure may be to use that $27^{41} \equiv 27 \equiv 5 \mod 11$ and $27^{6} \equiv 1 \mod 7$ to see that $27^{41} = 27^{42-1} \equiv 27^{-1} \equiv -1 \mod 7$, and put 5 mod 11 and -1 mod 7 together to get 27.)

This is if you're doing it by hand, for this case. In general, algorithmically, you would just use repeated squaring to exponentiate numbers. You don't gain much by using Euler's theorem, since finding the order of a number mod $n$ is as hard as factoring $n$.

Solution 3:

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.