Forum Index Register Members List Events Mark Forums Read Help

 JREF Forum Euclidean Algorithm

 Welcome to the JREF Forum, where we discuss skepticism, critical thinking, the paranormal and science in a friendly but lively way. You are currently viewing the forum as a guest, which means you are missing out on discussing matters that are of interest to you. Please consider registering so you can gain full use of the forum features and interact with other Members. Registration is simple, fast and free! Click here to register today.

 20th April 2012, 06:14 AM #1 LandR Graduate Poster     Join Date: Sep 2009 Posts: 1,028 Euclidean Algorithm Hi, I'm trying to understand the euclidean (extended) algorithm to solve equations of the form ax + by = gcd(a,b) I've found a site with a couple of examples but I'm not following their steps very well... Can someone explain how you go about it ? I get that you find the gcd of (a,b) using euclid. e.g. gcd(17, 218) (just a random example.., if this example doesn't work can someone show another example ?) and that I can do this using the table: (1) 218 = 17 x 12 + 14 (2) 17 = 14 x 1 + 3 (3) 14 = 3 x 4 + 2 (4) 3 = 2 x 1 + 1 (5) 2 = 2 x 1 + 0 So gcd(218, 17) = 1 So if I have the equation 218x + 17y = gcd(218, 17) 218x + 17y = 1 I then work backwards through the table above. starting with line (4) rearranged. 1 = 3 - 1 x 2 1 = 3 - 1 x (14 - (4 x 3)) >> here I sub in line (3) for 2. It's at this point I have no idea how to proceed. Last edited by LandR; 20th April 2012 at 06:24 AM.
 20th April 2012, 11:04 AM #2 maxpower1227 Graduate Poster     Join Date: Aug 2007 Posts: 1,043 Hmm.... I've never really seen these problems, but here is what I'm getting (I am switching notation to 218x - 17y = 1) 218x - 17y = 1 218 - 17*12 = 14 218*5 - 17*(12*5 + 4) = 2 218*5*9 - 17*(12*5*9 + 4*9 + 1) = 1 218*45 - 17*577 = 1 ETA: I'm way off. Better answer coming soon... __________________ Warning. If you don't want to see your treasured "evidence" completely pwned in public, don't show it to the posters at JREF. - Rolfe Last edited by maxpower1227; 20th April 2012 at 11:13 AM. Reason: ETA
 20th April 2012, 11:18 AM #3 maxpower1227 Graduate Poster     Join Date: Aug 2007 Posts: 1,043 1 = 3 - 2*1 1 = (17-14*1) - (14-3*4)*1 1 = (17-(218-17*12)*1) - ((218-17*12)-(17-14*1)*4)*1 1 = (17-(218-17*12)*1) - ((218-17*12)-(17-(218-17*12)*1)*4)*1 1 = (17*13 - 218) - ((218-17*12)-(17*13-218)*4)*1 1 = (17*13 - 218) - ((218-17*12)-(17*52-218*4)) 1 = (17*13 - 218) - (218*5 - 17*64) 1 = 17*77 - 218*6 __________________ Warning. If you don't want to see your treasured "evidence" completely pwned in public, don't show it to the posters at JREF. - Rolfe
 20th April 2012, 11:27 AM #4 maxpower1227 Graduate Poster     Join Date: Aug 2007 Posts: 1,043 The key seems to be to re-write your key equations as: (1) 218 - 17 x 12 = 14 (2) 17 - 14 x 1 = 3 (3) 14 - 3 x 4 = 2 (4) 3 - 2 x 1 = 1 (5) 2 - 2 x 1 = 0 and then continually making substitutions until all terms involve only multiples of 218 and 17 __________________ Warning. If you don't want to see your treasured "evidence" completely pwned in public, don't show it to the posters at JREF. - Rolfe
 21st April 2012, 09:23 AM #5 jojonete   Join Date: Sep 2007 Posts: 149 ETA: Argh! just noticed that maxpower1227 had got the answer two posts ago. Ok, consider this as a different explanation of how to take the same steps to get to the same solution. Originally Posted by maxpower1227 The key seems to be to re-write your key equations as: (1) 218 - 17 x 12 = 14 (2) 17 - 14 x 1 = 3 (3) 14 - 3 x 4 = 2 (4) 3 - 2 x 1 = 1 (5) 2 - 2 x 1 = 0 and then continually making substitutions until all terms involve only multiples of 218 and 17 Yes, that's it. I've just learnt this by checking wikipedia, and I'll elaborate more to (a) show LandR how it applies to his/her example and (b) make sure myself that it can be done. First, make it clear the problem we are trying to solve: 218x + 17y = 1 Second, the steps we'll follow: we'll solve all the following equations in order: [p1] 218x + 17y = 218 [p2] 218x + 17y = 17 [p3] 218x + 17y = 14 [p4] 218x + 17y = 3 [p5] 218x + 17y = 2 [p6] 218x + 17y = 1 Of course, the last equation is the one we're actually interested in. The two first ones are trivial: 218*1 + 17*0 = 218 [solution to p1] 218*0 + 17*1 = 17 [solution to p2] Then we pick equation (1) from maxpower1227, and we readily have: 218*1 + 17*(-12) = 14 [solution to p3] Now we pick equation (2) from maxpower1227: 17*1 + 14*(-1) = 3 Now, this should be 218x+17y=3, and not 17x+14y=3, but hey! in [solution to p3] we have 14 expressed as 218x+17y, so we can change the 14 to the form we need, so: 17*1 + (218*1 + 17*(-12)) * (-1) = 3 Joining all 218's and 17's we get: 218*(-1) + 17*13 = 3 [solution to p4] Now we just repeat. From (3): 14*1 + 3*(-4) = 2 Substituting [solution to p3] for 14 and [solution to p4] for 3: (218*1 + 17*(-12))*1 + (218*(-1) + 17*13)*(-4) = 2 218*5 + 17*(-64) = 2 [solution to p5] Finally, from (4): 3*1 + 2*(-1) = 1 Changing 3 and 2 to their [solution to p4] and [solution to p5] equivalents: (218*(-1) + 17*13)*1 + (218*5 + 17*(-64))*(-1) = 1 218*(-6) + 17*77 = 1 [solution to p6] So, the solution to our original problem, 218x + 17y = 1, is: x = -6 y = 77 He, he, now I'm sure I got it right Last edited by jojonete; 21st April 2012 at 09:30 AM.
 21st April 2012, 01:15 PM #6 LandR Graduate Poster     Join Date: Sep 2009 Posts: 1,028 Thank you!!!

JREF Forum

 Bookmarks Digg del.icio.us StumbleUpon Google Reddit