God Created the INTEGER - Stephen Hawkings

\

Awesome Book

https://books.google.co.in/books?id=eU_RzM7OoI4C&pg=PA604&lpg=PA604&dq=congruence+exponent+with+exponent&source=bl&ots=tLYATv69qC&sig=i1S3YkudeWkZOHh2TkJhhBfkUU0&hl=en&sa=X&ved=0ahUKEwiJhNbbqujLAhUJOJQKHVG_CEwQ6AEIQjAH#v=onepage&q=congruence%20exponent%20with%20exponent&f=false

To Find Modulo of Large Exponent.

Calculate 782 mod 40

[It is carried out using Chinese Remainder Theorm.]
Chinese Remainder Theorem

Maybe just start calculating. Note that 72=49≡9(mod40)$7^2=49\equiv 9(\mathrm{mod}40)$. So 74≡81≡1(mod40)$7^4\equiv 81\equiv 1(\mathrm{mod}40)$. We got lucky.

It follows that 780=(716)5≡1(mod40)$7^{80}=(7^{16}{)}^5\equiv 1(\mathrm{mod}40)$. Thus 782=78072≡49≡9(mod40)$7^{82}=(7^{\mathrm{80)\; (}}{7}^{\mathrm{2)}}\equiv 49\equiv 9(\mathrm{mod}40)$.

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

A more elaborate way is to use Euler's Theorem. If a$a$ is relatively prime to m$m$, then aφ(m)≡1(modm).$a^{\phi (m)}\equiv 1(\mathrm{mod}m).$

Here φ$\phi$ is the Euler ϕ$\varphi$-function. We have φ(40)=16$\phi (40)=16$, so taking a=7$a=7$ we have a16≡1(mod40)$a^{16}\equiv 1(\mathrm{mod}40)$. It follows that a80=(a16)5≡1(mod40)$a^{80}=(a^{16}{)}^5\equiv 1(\mathrm{mod}40)$. So a82≡a2=49(mod40)$a^{82}\equiv a^2=49(\mathrm{mod}40)$. But 49≡9(mod40)$49\equiv 9(\mathrm{mod}40)$.

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

First modulo 8$8$: We have 7≡−1(mod8)$7\equiv -1(\mathrm{mod}8)$, so 782≡(−1)82≡1(mod8)$7^{82}\equiv (-1{)}^{82}\equiv 1(\mathrm{mod}8)$.

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

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

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

Reference Link:
http://math.stackexchange.com/questions/165670/congruence-modulo-with-large-exponents