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 28th 2010, 12:48 AMMundakaModular 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, 04:24 AMtonio

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

---**first line**

---**second line**

---**third line**

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

--- from 3rd line

--- from 2nd line

--- from 1st line

And voila!:

Tonio - Apr 28th 2010, 04:54 AMMundaka
Thanks.

That helped me understand it a lot better as well.