# Thread: Modular arithmetic

1. ## Modular 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?

2. 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.

3. 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"

4. Hi! Yes its horribly tedious
You are right- this is part of cryptography, the RSA cryptosystem to be exact.

5. Deveno- Thanks sooooo much!!

6. 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.

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

8. 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)$

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

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