How can you find large powers modulo n?
1,320
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$$
Related videos on Youtube
Author by
Ian
Updated on April 17, 2020Comments
-
Ian over 3 years
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 :)
-
Alex J Best over 10 yearsAre you sure the question isn't to find $7^{62}$?
-
Ian over 10 yearsno it says 7^64 :/
-
-
Ian over 10 yearsI still don't understand why they state "find 7^62 mod 120" after saying "7^0 ≡ 1 mod 120"
-
DonAntonio over 10 yearsThere 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.