image
Physics Forums Logo
image
image
* Register * Upgrade Blogs Library Staff Rules Mark Forums Read
image
image   image
image

Go Back   Physics Forums > Science Education > Homework & Coursework Questions > Calculus & Beyond


Reply

image Extended euclidian algorithm problem (HELP!!!) Share It Thread Tools Search this Thread image
Old Oct12-05, 11:27 AM                  #1
Mathman23

Mathman23 is Offline:
Posts: 256
Extended euclidian algorithm problem (HELP!!!)

Hi

I have this here example problem:

9x - 65y = 1

I'm suppose to use the extended euclidian algorithm, but it has given me such much trouble.

I get the regular euclidian algorithm, but not the extended one.

Therefore if there is some good soul out there who would be so kind to explain the extended algorithm using this example I would be much greatful :-)

Sincerley and God Bless

Fred
  Reply With Quote
Old Oct12-05, 11:34 AM       Last edited by HallsofIvy; Oct12-05 at 11:37 AM..            #2
HallsofIvy

PF Mentor

HallsofIvy is Offline:
Posts: 25,722
One difficulty I have is that I don't see a problem here! An equation is not a problem. What do you want to do with the equation? Since you mention the (extended) Euclidean algorithm, are you trying to find integer values of x and y that satisfy the equation?

I notice that 9 divides into 65 3 times with a remainder of 2 and that 2 divides into 9 4 times with a remainder of 1.

In other words 9- 4(2)= 1 and 2= 65- 7(9). Does that help?
  Reply With Quote
Old Oct12-05, 11:59 AM                  #3
Mathman23

Mathman23 is Offline:
Posts: 256
Hi and thank you for your answer,

As I wrote in my earlier post I know how to use the standard euclidian algorithm and thereby finding the gcd(a,b).

Having this in my mind is there an recipe that I can follow then I need to find an x,y this satisfies:

ax + by = gcd(a,b)

I know its the extended euclidian algorithm which I need to use. Would You please explain to me step by step, how by using ex.euclid that I'm able to find x,y ?

Best Regards and God Bless

Fred
  Reply With Quote
Old Oct12-05, 12:03 PM                  #4
ComputerGeek

ComputerGeek is Offline:
Posts: 534
yes, you solve for the remainders and substitute the solution, collect the terms and solve for the next remainder, then substitute and collect terms, etc.
  Reply With Quote
Old Oct12-05, 12:09 PM                  #5
Mathman23

Mathman23 is Offline:
Posts: 256
Can you please elaborate :-)

Lets say we have 7x - 50y = 1 = gcd(7,50)

How do I go about solving this equation using ex. euclid ?

/Fred

Originally Posted by ComputerGeek
yes, you solve for the remainders and substitute the solution, collect the terms and solve for the next remainder, then substitute and collect terms, etc.
  Reply With Quote
image image
Reply
Thread Tools


Similar Threads for: Extended euclidian algorithm problem (HELP!!!)
Thread Thread Starter Forum Replies Last Post
Euclidian Geometry k3N70n Calculus & Beyond 1 Jan27-07 11:06 PM
Algorithm problem (please help) jackdamack10 Programming & Comp Sci 11 Oct28-05 10:00 AM
Design algorithm problem black_red_cragon Number Theory 1 Aug28-05 04:26 PM
Euclidian space definition quasar987 Linear & Abstract Algebra 6 Dec13-04 04:38 AM

Powered by vBulletin Copyright ©2000 - 2010, Jelsoft Enterprises Ltd. © 2009 Physics Forums
Sciam | physorgPhysorg.com Science News Partner
image
image   image