# 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?

-
How about trying the Chinese Remainder Theorem? –  j.p. Aug 5 '10 at 14:34
@jug: Can you give an example how to use that in this case? –  Gumbo Aug 5 '10 at 15:08

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

-
Thanks for your answer! But how do you derive 27 from 5 mod 11 and -1 mod 7? –  Gumbo Aug 5 '10 at 16:12
Well, you can just check that 27 works (and 27 is how you arrived at those remainders in the first place). :-) But in general, look up the Chinese remainder theorem; it gives some methods. One method: because the inverse of 7 mod 11 is 8 and the inverse of 11 mod 7 is 2, you can use 5(7)(8) + (-1)(11)(2) mod 77, which is 27. Or (easier by hand) you can just try numbers of the form 7k-1 until you get one that's 5 mod 11: so here you'd try 6, 13, 20, 27. (You'll try at most 11 numbers, since there has to be a solution, by the Chi.Rem.Thm) –  ShreevatsaR Aug 5 '10 at 16:38
Thanks for your help! I really appreciate that! –  Gumbo Aug 5 '10 at 16:47

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

-
Thanks, I've learnt it now. :-) Just to make sure I understand: the Carmichael function of n is the lcm of the orders of all a relatively prime to n, and is always a divisor of the Euler totient function of n, correct? I agree it's confusing to talk of what's "simplest" when working with specific numbers rather than some general set of cases. –  ShreevatsaR Aug 5 '10 at 18:32
Yes. In practice, one computes it by taking the lcm of the Carmichael functions of the prime power factors of n, which are the same as the Euler totient functions except for powers of 2, where for powers of 2 greater than or equal to 8 it's half what you'd expect. –  Qiaochu Yuan Aug 5 '10 at 18:52
a quibble: "half of what you'd expect" is not a very well-defined quantity. I had never thought about the Carmichael function until today, but (as a practicing number theorist) I found that its values at powers of $2$ are exactly what I expected them to be.... :) –  Pete L. Clark May 22 '11 at 6:06
@Pete: sure, but as a practicing number theorist you're well aware that the corresponding unit groups aren't cyclic! –  Qiaochu Yuan May 22 '11 at 8:03

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.

-

By little Fermat: $\; 6,10\:|\:120\ \Rightarrow\ 3^{120} \equiv 1 \pmod{7, 11}\ \Rightarrow\ 3^{123} \equiv 3^3 \pmod{77}$

See also these Fermat-Euler-Carmichael generalizations of little Fermat-Euler from my sci.math post on Apr 10 2009.

THEOREM 1 $\$ For naturals $\rm\: a,e,n\:$ with $\rm\: e,n>1$

$\rm\qquad\qquad\ n\ |\ a^e-a\$ for all $\rm\:a\ \iff\ n\:$ is squarefree and prime $\rm\: p\:|\:n\: \Rightarrow\: p-1\ |\ e-1$

REMARK $\$ The special case $\rm\:e \:= n\:$ is Korselt's criterion for Carmichael numbers.

THEOREM 2 $\$ For naturals $\rm\: a,e,n \:$ with $\rm\: e,n>1$

$\rm\qquad\qquad\ n\ |\ a^e-1\$ for all $\rm\:a\:$ coprime to $\rm\:n\ \iff\ p\:$ prime, $\rm\ p^k\: |\: n\ \Rightarrow\ \lambda(p^k)\:|\:e$

with $\rm\quad\ \lambda(p^k)\ =\ \phi(p^k)\$ for odd primes $\rm\:p\:,\:$ or $\rm\:p=2,\ k \le 2$

and $\quad\ \ \rm \lambda(2^k)\ =\ 2^{k-2}\$ for $\rm\: k>2$

The latter exception is due to $\rm\:\mathbb Z/2^k\:$ having multiplicative group $\rm\ C(2) \times C(2^{k-2})\$ for $\rm\:k>2\:.$

Note that the least such exponent $\rm\:e\:$ is given by $\rm\: \lambda(n)\: =\: lcm\ \{\lambda(\;{p_i}^{k_i})\}\;$ where $\rm\ n = \prod {p_i}^{k_i}\:.$

$\rm\:\lambda(n)\:$ is called the (universal) exponent of the group $\rm\:\mathbb Z/n^*,\:$ a.k.a. the Carmichael function.

See my post here for proofs and further discussion.

-