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

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.

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.