# Congruence Modulo with large exponents

How will the congruence modulo works for large exponents? What theorem/s may be used? For example to show that $7^{82}$ is congruent to $9 \pmod {40}$.

Besides the methods mentioned by Andre, it's worth mentioning another more powerful technique that often proves crucial. Namely, instead of Euler's theorem, based on his $$\phi$$ (totient) function, one should use an improvement due to Carmichael, based on his $$\lambda$$ function (universal exponent).

The big gain in power arises from employing $$\rm\: \ell = \color{#C00}{lcm}\:$$ vs. product to combine exponents:

$$\begin{eqnarray}\rm a^j&\equiv&\rm 1\pmod m\\ \rm a^k&\equiv&\rm 1\pmod n\end{eqnarray}\Bigg\}\ \Rightarrow\rm\ a^{\color{#C00}{lcm}(j,k)}\equiv 1\pmod{lcm(m,n)}$$

since by mod order reduction $$\rm\bmod m\!:\ a^j\equiv 1,\ j\mid \ell\,\Rightarrow\, a^{\ell}\equiv 1\,$$ (or directly: $$\rm\,\ell = ji\,\Rightarrow\, a^{\ell}\equiv (a^j)^i\equiv 1^i\equiv 1).$$ Similarly $$\rm\bmod n\!:\ a^{\ell}\equiv 1,\,$$ so $$\rm\,a^{\ell}\equiv 1\,$$ lifts to modulus $$\rm\,{\rm lcm}(m,n)\,$$ by CCRT.

For example, if $$\rm\:n\:$$ is coprime to $$2,3,5$$ then Euler's theorem implies that $$\rm\:n^{64}\equiv 1\pmod{240},\:$$ versus Carmichael's theorem, which yields the much stronger result that $$\rm\:n^4\equiv 1\pmod{240}.\,$$ This allows one to immediately solve the problem there, viz. $$\rm\,240\:|\:p^4\!-\!1\,$$ for all primes $$\rm\,p > 5.$$ Compare below the computation of the Euler vs. Carmichael function:

$$\qquad\qquad\rm\phi(240) = \phi(2^4\cdot 3\cdot 5) = \ \phi(2^4)\ \phi(3)\ \phi(5) = 8\cdot2\cdot 4 = 64$$

$$\qquad\qquad\rm\lambda(240) = \lambda(2^4\cdot 3\cdot 5) = \color{#C00}{lcm}(2^{2},\phi(3),\phi(5)) = \color{#C00}{lcm}(4,2,4) = 4$$

Thus Carmichael generally yields a much lower bound on the order of elements, which greatly simplifies problems like yours and that above. For more examples see my posts here.

Maybe just start calculating. Note that $7^2=49\equiv 9\pmod{40}$. So $7^4\equiv 81\equiv 1\pmod{40}$. We got lucky.

It follows that $7^{80}=(7^{16})^5\equiv 1\pmod{40}$. Thus $7^{82}=7^{80}7^2\equiv 49\equiv 9\pmod{40}$.

In general, repeated squaring, and reduction with respect to our modulus (in this case $40$) gets us to high powers fairly quickly.

A more elaborate way is to use Euler's Theorem. If $a$ is relatively prime to $m$, then $a^{\varphi(m)}\equiv 1\pmod{m}.$

Here $\varphi$ is the Euler $\phi$-function. We have $\varphi(40)=16$, so taking $a=7$ we have $a^{16}\equiv 1 \pmod{40}$. It follows that $a^{80}=(a^{16})^5\equiv 1\pmod{40}$. So $a^{82}\equiv a^2=49\pmod{40}$. But $49\equiv 9\pmod{40}$.

Still another way is to factor $40$ as $2^3\cdot 5$. We then work separately modulo $8$ and modulo $5$.

First modulo $8$: We have $7\equiv -1\pmod{8}$, so $7^{82}\equiv (-1)^{82}\equiv 1\pmod{8}$.

Next modulo $5$: We have $7\equiv 2\pmod{5}$, so $7^2\equiv 4\equiv -1\pmod{5}$, and therefore $7^4\equiv 1\pmod{5}$. (We could also get this directly by using Fermat's Theorem.) It follows that $7^{80}\equiv 1\pmod{5}$, and therefore $7^{82}\equiv 4\pmod 5$.

Now we are looking for the numbers that are congruent to $1$ modulo $8$ and to $4$ modulo $5$. For bigger numbers, we can use the Chinese Remainder Theorem. But finding a number congruent to $1$ modulo $8$ and to $4$ modulo $5$ can also be done without much machinery.

In general, the technique to use depends very much on the modulus $m$. If it is huge, and we do not know its prime factorization, then the Binary Method of exponentiation is quite efficient.

Thought I'd drop a few helps:

• even exponents you can replace the base with it's additive inverse or multiplicative inverse if needed.
• odd exponents, you can do the same and then change your answer to the additive inverse when complete.
• exponents can be written in any base system and then dealt with like this raise to the power of the base system and multiply the actual base raised to the digit. Repeat this process with each digit.
• factorable exponents can use $$a^{bc}=(a^b)^c$$
• factorable moduli can be split into it's prime powers and combined with Chinese remainder theorem.
• exponents can be reduced mod Euler phi function.
• exponent can be replaced by additive inverse exponent and then the answer is the multiplicative inverse mod the modulus
• you can repeatedly raise to same exponent and multiply the results for the exponents that add to the original ...

Etc.