Thread: 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.

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

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

Thanks.

That helped me understand it a lot better as well.