Math Is Fun Forum

Natkirky

Member

Registered: 2006-10-17

Posts: 21

Euclidean Algorithm and gcd

Hi i was wondering if anyone could help me with this question.

Find integers m and n such that 8m + 26n = 2.

I can't make sense of my notes and don't even know how to start.

Thank you

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Euclidean Algorithm and gcd

Hi

http://en.wikipedia.org/wiki/Extended_E … _algorithm

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Natkirky

Member

Registered: 2006-10-17

Posts: 21

Re: Euclidean Algorithm and gcd

Hi Bob,

That's great thank you?

Natalie

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Euclidean Algorithm and gcd

Hi Natalie;

8m + 26n = 2.

Once you find one pair of solutions then you can get more using this:

This is a rough and ready method that sometimes works.

Get one solution by finding the gcd of 26 and 8

(26,8) = 2 Take the 2 from the 26 and divide by 8 = 3 So m = - 3 and n = 1

Now use the above formula to get more.

Here is a cool page that does it for you.

http://www.hostsrv.com/webmaa/app1/MSP/ … tended_gcd

Here is a nice way to do it by hand.

http://www.opencodeproject.com/article. … +algorithm

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.