# Modular Arithmetic

• Apr 27th 2010, 11:48 PM
Mundaka
Modular Arithmetic
Hi,

Just need help with a couple of Q's.

Using Euclids algorithm, find:
3568a = 1 mod 1127

and

Use Euclids algorithm to find x and y so 6804x +1343y = 1

Ty for any help.
• Apr 28th 2010, 03:24 AM
tonio
Quote:

Originally Posted by Mundaka
Hi,

Just need help with a couple of Q's.

Using Euclids algorithm, find:
3568a = 1 mod 1127

and

Use Euclids algorithm to find x and y so 6804x +1343y = 1

Ty for any help.

Read about Bezout's Identity: I'll do (2) and that must suffice to do (1):

$\displaystyle 6804 = 5\cdot 1343+89$ --- first line

$\displaystyle 1343=15\cdot 89+8$ --- second line

$\displaystyle 89=11\cdot 8+1$ --- third line

$\displaystyle 8=8\cdot 1$ --- fourth and final line

Now begin from one line before the end upwards, writing each time the remainder as a combination of the other two elements:

$\displaystyle 1=89-11\cdot 8$ --- from 3rd line

$\displaystyle 1=89-11\cdot 8=89-11(1343-15\cdot 89)=166\cdot 89-11\cdot 1343$ --- from 2nd line

$\displaystyle 1=166\cdot 89-11\cdot 1343=166(6804-5\cdot 1343)-11\cdot 1343=166\cdot 6804 -841\cdot 1343$ --- from 1st line

And voila!: $\displaystyle 1=166\cdot 6804+(-841)\cdot 1343$

Tonio
• Apr 28th 2010, 03:54 AM
Mundaka
Thanks.

That helped me understand it a lot better as well.