Modular arithmetic

**nicola5** · May 2nd 2011, 12:49 PM

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?

**Moo** · May 2nd 2011, 02:45 PM

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.

**Deveno** · May 2nd 2011, 03:24 PM

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"

**nicola5** · May 2nd 2011, 04:15 PM

Hi! Yes its horribly tedious

You are right- this is part of cryptography, the RSA cryptosystem to be exact.

**nicola5** · May 2nd 2011, 04:21 PM

Deveno- Thanks sooooo much!!

**Moo** · May 2nd 2011, 11:12 PM

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.

**chisigma** · May 4th 2011, 06:22 AM

Originally Posted by nicola5

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?

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

$\chi$ $\sigma$

**abhishekkgp** · May 5th 2011, 10:41 AM

Originally Posted by nicola5

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?

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.

$5^6 \equiv 1 \, (\, mod \, 7) \Rightarrow 5^7 \equiv 5 \, (\, mod \,7)$
$5^7 \equiv (5^2)^3 \cdot 5 \equiv 3^3 \cdot 5 \equiv 3 \, (\, mod \, 11)$

so we have $5^7 \equiv 5 \,(\, mod \, 7)$ and,
$5^7 \equiv 3 \, (\, mod\, 11)$

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

now the first congruence gives $x=7k+5 \, for \, some \, k \in \mathbb{Z}$
substitute this in the second congruence to get:
$7k+5 \equiv 3\,(\,mod\,11) \Rightarrow 7k \equiv 9 \,(\,mod\,11) \iff 21k \equiv 27\Rightarrow k \equiv 6\,(\,mod\,11)$
now $k \equiv 6\,(\,mod\,11) \Rightarrow k=11r + 6 \, for \, some \, r \in \mathbb{Z}$

substitute this in $x=7k+5 \, to\, get\, x= 77r+47$

from the above we have:
$5^7 \equiv x\equiv 47 \,(\,mod\,77)$

**chisigma** · May 5th 2011, 10:31 PM

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

$\chi$ $\sigma$

**chisigma** · May 6th 2011, 02:14 AM

In my post #7 I did wrong computation of

so that now I try to repair...

Is 2773=59 x 47 and ...

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

(1)

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

Kind regards

$\chi$ $\sigma$

Thread: Modular arithmetic

LinkBack

Thread Tools

Display