# Modular exponentiation making use of Euler's theory

How can I compute $27^{41}\ \mathrm{mod}\ 77$ as straightforward as feasible?

I currently recognize that $27^{60}\ \mathrm{mod}\ 77 = 1$ as a result of Euler’s theorem :

$$ a^{\phi(n)}\ \mathrm{mod}\ n = 1 $$. and also. $$ \phi(77) = \phi(7 \cdot 11) = (7-1) \cdot (11-1) = 60 $$

I additionally recognize from making use of modular exponentiation that $27^{10} \mathrm{mod}\ 77 = 1$ and also hence

$$ 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 acquire the outcome of $27^{41}\ \mathrm{mod}\ 77$ making use of $27^{60}\ \mathrm{mod}\ 77 = 1$ in some way?

You can make use of exponentiation by squaring (all procedures 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 makes use of just 7 reproductions as opposed to 41.

As recommended in the comment over, you can make use of the Chinese Remainder Theorem, by utilizing Euler's theory/ Fermat's theory on each of the tops independently. You recognize that $27^{10} \equiv 1 \mod 11$, and also you can additionally see that modulo 7, $27 \equiv -1 \mod 7$, so $27^{10} \equiv (-1)^{10} \equiv 1\mod 7$ too. So $27^{10} \equiv 1 \mod 77$, and also $27^{41} = 27^{40+1} \equiv 27 \mod 77$. (We've properly located the order of 27 as 10, yet an extra mechanical procedure might be to make use of that $27^{41} \equiv 27 \equiv 5 \mod 11$ and also $27^{6} \equiv 1 \mod 7$ to see that $27^{41} = 27^{42-1} \equiv 27^{-1} \equiv -1 \mod 7$, and also placed 5 mod 11 and also - 1 mod 7 with each other to get 27.)

This is if you're doing it by hand, for this instance. As a whole, algorithmically, you would certainly simply make use of duplicated making even to exponentiate numbers. You do not obtain a lot by utilizing Euler's theory, given that locating the order of a number mod $n$ is as tough as factoring $n$.

If you are significant concerning "as straightforward as feasible" after that observe that $27^{41} = 3^{123}$ and also usage Carmichael's theorem (a fortifying of Euler's theory which in fact offers a limited bound) to reason that $3^{30} \equiv 1 \bmod 77$ and also therefore $3^{123} \equiv 3^3 \equiv 27 \bmod 77$. Yet I do not assume this is the appropriate inquiry to ask ; you need to actually be asking "as basic as feasible," and afterwards the solution you have actually approved is most ideal.

(Of training course it is adequate to make use of Euler's theory for the above calculation, yet couple of individuals appear to find out Carmichael's theory and also I constantly such as to aim it out when I can.)

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

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

**THEORY 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 also prime $\rm\: p\:|\:n\: \Rightarrow\: p-1\ |\ e-1 $

**REMARK ** $\ $ The grandfather clause $\rm\:e \:= n\:$ is Korselt's criterion for Carmichael numbers.

**THEORY 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 weird tops $\rm\:p\:,\:$ or $\rm\:p=2,\ k \le 2 $

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

The last exemption results from $\rm\:\mathbb Z/2^k\:$ having multiplicative team $\rm\ C(2) \times C(2^{k-2})\ $ for $\rm\:k>2\:.$

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

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

See my post here for evidence and also more conversation.

Related questions