# How can you find large powers modulo n?

I am following an example in my book as follows:

Find 7^64 mod 120.
Note: (7,120) = 1 and φ(120) = 32, so 7^64 ≡ 7^0 ≡ 1 mod 120.


This part I understand. It's this part which is confusing me.

Find 7^62 mod 120.                             <--- why do this?
Write 7^62 ≡ 7^64 .7^-2 ≡ 49^-1 mod 120.       <--- how do you work out that 7^62 ≡ 49^-1 mod 120

In order to find 49^-1 mod 120 we run the Euclidean algorithm:
120 = 2.49 + 22
49  = 2.22 + 5
22  = 4.5  + 2
5   = 2.2  + 1

Thus 1 = 5-2.2=5-2.(22-4.5) = 9.5 - 2.22
= 9.(49-2.22)-2.22 = 9.49 - 20.22
= 9.49 - 20.(120 - 2.49) = 49.49 - 20.120
≡ 49.49 mod 120

Thus 49^-1 ≡ 49 mod 120. Thus 7^62 ≡ 49 mod 120.     <--- how is 49^-1 ≡ 49 mod 120


Will be eternally grateful if anyone can help! Thanks in advance :)

-
Are you sure the question isn't to find $7^{62}$? –  Alex J Best Apr 16 '13 at 21:47
no it says 7^64 :/ –  Ian Apr 16 '13 at 21:54

We have that

$$7^{62}=7^{64}\cdot7^{-2}=1\cdot7^{-2}=49^{-1}$$

and what they do after that is the reverse Euclides Algorithm, as you can check: just a way to find out integers $\,x,y\,$ s.t. $\,49x+120y=1=g.c.d.(49,129)\,$.

But in this case you can go around this (the following is done modulo $\,120\,$):

$$7^4=1\implies 7^{-1}=7^3=343=-17=103\implies$$

$$49^{-1}=\left(7^{-1}\right)^2=(-17)^2=289=49\ldots$$

-
I still don't understand why they state "find 7^62 mod 120" after saying "7^0 ≡ 1 mod 120" –  Ian Apr 17 '13 at 0:16
There are two "find" 's: the first one is $\,7^{64}\,$ and the 2nd for $\,7^{62}\,$ , and I think they're separate. The first part ended with $\,7^{64}=7^0=1\,$ which, btw, isn't a very wise thing to write imfho. It is based on the fact that $\,a^{\phi(120)}=1\;\;\forall\;a\in\left(\Bbb Z/120\Bbb Z\right)^*$ , but that $\,7^0\,$ can be pretty confusing for newbies. –  DonAntonio Apr 17 '13 at 2:19