Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 :)

share|improve this question
    
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

1 Answer 1

up vote 0 down vote accepted

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.