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?

Printable View

- May 2nd 2011, 12:49 PMnicola5Modular arithmetic
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? - May 2nd 2011, 02:45 PMMoo
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. - May 2nd 2011, 03:24 PMDeveno
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" - May 2nd 2011, 04:15 PMnicola5
Hi! Yes its horribly tedious:(

You are right- this is part of cryptography, the RSA cryptosystem to be exact. - May 2nd 2011, 04:21 PMnicola5
Deveno- Thanks sooooo much!!

- May 2nd 2011, 11:12 PMMoo
Can you give the original questions then ? Because if it's a problem you've been given, there's no point in doing such calculations.

- May 4th 2011, 06:22 AMchisigma
The solution in both case requires the 'Chinese Remainder Theorem' which extablishes that if http://quicklatex.com/cache3/ql_ff0d...298f419_l3.png then the pair of equations...

http://quicklatex.com/cache3/ql_43f0...71d02b2_l3.png

http://quicklatex.com/cache3/ql_2015...66471f5_l3.png (1)

... has one and only one solution http://quicklatex.com/cache3/ql_0895...959a891_l3.png...

a) because 77= 7 x 11 is...

http://quicklatex.com/cache3/ql_edd0...5ebf866_l3.png

http://quicklatex.com/cache3/ql_b32b...31b8e04_l3.png (2)

... so that http://quicklatex.com/cache3/ql_eeb3...cc2e989_l3.png is solution of the pair of equations...

http://quicklatex.com/cache3/ql_dd48...00760b1_l3.png

http://quicklatex.com/cache3/ql_4fb4...8cf0297_l3.png (3)

b) this case is a little more 'computational expensive' than the previous one. Because 2773= 59 x 47 is...

http://quicklatex.com/cache3/ql_c02c...1ff0808_l3.png

http://quicklatex.com/cache3/ql_de4b...6334b22_l3.png (4)

... so that http://quicklatex.com/cache3/ql_11f9...99347f4_l3.png is solution of the pair of equations...

http://quicklatex.com/cache3/ql_fbbb...8306f97_l3.png

http://quicklatex.com/cache3/ql_9398...0b4a7a4_l3.png (5)

The procedure for solving the pair of equations like (1) will be described in a further post...

Kind regards

$\displaystyle \chi$ $\displaystyle \sigma$ - May 5th 2011, 10:41 AMabhishekkgp
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.

http://latex.codecogs.com/png.latex?..., (\, mod \,7)

http://latex.codecogs.com/png.latex?...(\, mod \, 11)

so we have http://latex.codecogs.com/png.latex?...,(\, mod \, 7) and,

http://latex.codecogs.com/png.latex?... (\, mod\, 11)

call 5^7=x so that it doesn't look tedious.

now the first congruence gives http://latex.codecogs.com/png.latex?...\in \mathbb{Z}

substitute this in the second congruence to get:

http://latex.codecogs.com/png.latex?...6\,(\,mod\,11)

now http://latex.codecogs.com/png.latex?...\in \mathbb{Z}

substitute this in http://latex.codecogs.com/png.latex?...et\, x= 77r+47

from the above we have:

http://latex.codecogs.com/png.latex?... \,(\,mod\,77) - May 5th 2011, 10:31 PMchisigma
A procedure for solving the pair of equations...

http://quicklatex.com/cache3/ql_43f0...71d02b2_l3.png

http://quicklatex.com/cache3/ql_2015...66471f5_l3.png (1)

... obtaining http://quicklatex.com/cache3/ql_44d2...8d68b3f_l3.png with http://quicklatex.com/cache3/ql_908e...8c76e25_l3.png and http://quicklatex.com/cache3/ql_23b2...169a3f2_l3.png distinct primes consists in computing first ...

http://quicklatex.com/cache3/ql_3b1b...793bb55_l3.png

http://quicklatex.com/cache3/ql_f82a...0405f93_l3.png (2)

... and then...

http://quicklatex.com/cache3/ql_8126...31fb921_l3.png (3)

Now we try to solve the first pair of equations of my previous post...

http://quicklatex.com/cache3/ql_dd48...00760b1_l3.png

http://quicklatex.com/cache3/ql_4fb4...8cf0297_l3.png

http://quicklatex.com/cache3/ql_e0e3...0556157_l3.png

http://quicklatex.com/cache3/ql_3c9b...2f288bd_l3.png

http://quicklatex.com/cache3/ql_86ca...7783c42_l3.png

... and we obtain the result obtained by abhishekkgp...

The second pair of equations can be solved in the same way...

Kind regards

$\displaystyle \chi$ $\displaystyle \sigma$ - May 6th 2011, 02:14 AMchisigma
In my post #7 I did wrong computation of http://quicklatex.com/cache3/ql_8b60...9c694de_l3.png so that now I try to repair...

Is 2773=59 x 47 and ...

http://quicklatex.com/cache3/ql_491e...f90f2fa_l3.png

http://quicklatex.com/cache3/ql_294a...0e91c6b_l3.png

... so that the equation pair to be solved is...

http://quicklatex.com/cache3/ql_6042...2aefb40_l3.png

http://quicklatex.com/cache3/ql_68f8...cc802bf_l3.png (1)

Applying the procedure described in #9 we obtain...

http://quicklatex.com/cache3/ql_cd37...0835aa3_l3.png

http://quicklatex.com/cache3/ql_8d1e...de5080e_l3.png

http://quicklatex.com/cache3/ql_ee28...67b783f_l3.png

Kind regards

$\displaystyle \chi$ $\displaystyle \sigma$