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.

Printable View

- Apr 27th 2010, 11:48 PMMundakaModular 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 AMtonio

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 AMMundaka
Thanks.

That helped me understand it a lot better as well.