Question

Why, given Euclid's algorithm yielding the GCD of two numbers m and n in the form (a*m + b*n), taken a step further to a' and b', does (a'*m) equal the LCM of m and n? Is there a proof for this?

Answer 1

What is the definition of LCM that uses the GCD as a factor?

Answer 2

there are 2 integers a,b such that the GCD of two integers m,n can be written as:

am + bn = GCD

what does it mean to 'take it a step further'?

Answer 3

Given that a and b can be determined using the division algorithm in the format a'' = a - a'*q (similarly for b), even though you can't divide by zero, you can still continue the a and b portions of the algorithm to get an a and b such that a*m + b*n = 0, and where a*m = LCM(m,n)

Answer 4

I don't know why this works but it's consistent. I just want to know if there's a proof for it or counterproof against it so I can know if it's reliable or provably false.

Answer 5

For example, given m = 15, n = 10: for a = 2 and b = -3 we get:
15(2) + 10(-3) = 30 - 30 = 0
Also, 15 * 2 happens to be the LCM of 15 and 10. But how can we prove generically that this would work for ALL m and n?

Answer 6

the GCD of 15 and 10 is not 0 ... but im prolly reading that wrong.

Answer 7

right the gcd is 30... but lemme try to illustrate this better
15 10
15 1 0
10 0 1
5 1 -1
are you familiar with finding a and b using this method? In this case, you can see when the GCD is 5, a=1 and b=-1 ... if you continue the table one more row, however, you get 0 (because 10 MOD 5 = 0) and a=-2, b=3. As such, |a*m| = 30, the LCM(m,n)
What makes this witchcraft happen? It seems to work for all m and n, but I can't work out a proof for it

Answer 8

lcm is 30, gcd is 5 ... im use to a different method

15 = 1*(10) + 5
10 = 2* (5) + 0 <-- got a zero so move 1 up

gcd = 5 such that

15a + 10b = 5, running a reverse euclid alg ...

0
0 1
0-1(1) = -1

out of factors, started with 0 so the smaller value gets the -1

15a + 10(-1) = 5, a has to be 1

15(1) + 10(-1) = 5

Answer 9

try your method for a prime, or relatively prime values and see if it works out for you.

Answer 10

Yes, it is working for all values, even if I make m=n it woks, if m or n = 1, or both do, etc.

Answer 11

can you post a link to the method you are using? it would help me better see the process and tell if things are working in some pattern that can be proofed

Answer 12

I haven't found the method published anywhere, it was my professor's blackboard method. I unfortunately am having a difficult time explaining it better than this. Basically you build a table using m and n, then recursively fill out each row of the table using DIV, MOD, and new a and b values recursively until MOD = 0; that's how you know you've reached the GCD. That's Euclid's algorithm in a nutshell. But then AFTER you find GCD, if you continue filling out the table to the next row you get numbers that start giving you LCM of m and n and we can't figure out why. Sorry, I am not able to explain it better in chat format. :(

Answer 13

so if im reading this right ...

15 10
15 15/15 = 1 10/15 = 0, assuming since its less than 1?

10 15/10 = 0 10/10 = 1
^^^^
this is where my comprehension is breaking down


explain how we fill in the first row, then lets see if i can use that to fill in the second row, and proceed to the third row.

Answer 14

looks like something interesting is cookin up .. .what's happening??

Answer 15

euclid is casuing trouble again :)

Answer 16

lol ... (a*m + b*n) = gcd is Bezout lemma ... i recently did that on abstract algebra. freaking ugly.

Answer 17

but what @steven_k is trying to tell ... I am not understanding, probably my english :|

Answer 18

if i could figure out the tabling i might be able to perceive it regardless of my english :)

Answer 19

Sorry, the method is quite complicated... The first rows are filled in as they are because 15(1) + 10(0) = 15, and 15(0) + 10(1) = 10.
Then in the second row, the first number is 5 because 15mod10=5, the second number is 1 and the third number is -1 because for each number in row (n), it is (n-2) - q(n-1), where q = the DIV of the previous two row headers, in this case 15 and 10; so DIV = 1

Answer 20

did you mean that how Euclid's algo works?

Answer 21

*do

Answer 22

yes, but the point being, using this method you can continue one row past the end where you find GCD and get values for a and b such that (a*m)+(b*n) = 0 and |a*m| = lcd(m,n)

Answer 23

(a*m)+(b*n) = 0 is equivalent to
(a*m)= (b*n) ... just ignore the negative, ... this is trivially true, just set m=b and n=a