# Math Help - Modular Arithmetic

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

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

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

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

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

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

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

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

$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!: $1=166\cdot 6804+(-841)\cdot 1343$

Tonio

3. Thanks.

That helped me understand it a lot better as well.