How do I calculate 5^7(mod 77)?
Im at my wits end- nothing seems to work!!
Also how is 5^157=1044(mod2773)?! Its there in one of the examples in my book and im wondering where that came from?
Hello,
For the first one, I can't really see any simple method.
5²=25, 5^4=25^2=625
77x2=154 and since 600=4x150, 77x8=154x4=600+16=-9 mod 625
and 154=155-1=5x31-1 -> 5x31=1 mod 77.
So finally 5^7=(5^4)^2 * 31 mod 77 = 81*31 mod 77 = 4x31 mod 77 = 124 mod 77 = -30 mod 77.
As for the second one, it looks awful (even the first one was awful)... in which chapter was it ? what's the context ? it looks like some cipher stuff.
the first one is a bit tedious, but i don't know about awful.
5^3 = 125 = 48 mod 77
5^4 = (48)(5) = 240 = 9 mod 77
5^5 = 45 mod 77
5^6 = 225 = 71 = -6 mod 77
5^7 = -30 = 47 mod 77
for the second one, 5^5 = 3125 = 352 mod 2773
5^10 = (352)(352) = 123,904 = 1892 mod 2773
5^20 = (1892)(1892) = 3,579,664 = 2494 mod 2773
5^40 = (2494)(2494) = 6,220,036 = 197 mod 2773
5^80 = (197)(197) = 38,809 = 2,760 = -13 mod 2773
5^120 = (197)(-13) = -2561 = 212 mod 2773
5^140 = (212)(2494) = (212)(-279) = -59,148 = -915 mod 2773
5^150 = (-915)(1892) = -1,731,180 = -828 mod 2773
5^155 = (-825)(352) = -291,456 = -291 mod 2773
5^157 = (-291)(25) = -7275 = -1729 = 1044 mod 2773
i'm sure there's an easier way to compute this, but as you see, it can be done "long-hand"
The solution in both case requires the 'Chinese Remainder Theorem' which extablishes that if then the pair of equations...
(1)
... has one and only one solution ...
a) because 77= 7 x 11 is...
(2)
... so that is solution of the pair of equations...
(3)
b) this case is a little more 'computational expensive' than the previous one. Because 2773= 59 x 47 is...
(4)
... so that is solution of the pair of equations...
(5)
The procedure for solving the pair of equations like (1) will be described in a further post...
Kind regards
knowing the chinese remainder theorem helps.
suppose you found out 5^7(mod 7) and 5^7(mod11) the according to chinese remainder theorem you can find out what is 5^7(mod 77). Even if you dont know chinese rem-theorem still the following will make it clear to you.
so we have and,
call 5^7=x so that it doesn't look tedious.
now the first congruence gives
substitute this in the second congruence to get:
now
substitute this in
from the above we have:
A procedure for solving the pair of equations...
(1)
... obtaining with and distinct primes consists in computing first ...
(2)
... and then...
(3)
Now we try to solve the first pair of equations of my previous post...
... and we obtain the result obtained by abhishekkgp...
The second pair of equations can be solved in the same way...
Kind regards