# Why does Euclid's algorithm taken one step past the GCD seem to yield the LCM?

In class we are going over Euclid's Algorithm. For example, we learned that for integers $m$, $n$:$$\gcd(m,n) = sm + tn$$ Where $s$ and $t$ are integers that can be plugged in to satisfy the equation.

We also learned to step through the recursive algorithm like so: $$\gcd(m, n) = \gcd(m, n \bmod m)$$ to get pairs of coefficients $s$ and $t$ until we reached a remainder of zero ($n \bmod m = 0$), meaning the $s$ and $t$ at that point in the recursion are the ones that yield:$$sm + tn = \gcd(m,n)$$

What we observed but couldn't explain (professor included) was that if you take the algorithm one step further, getting $s'$ and $t'$ such that $s'm + t'n = 0$, it seems to be always true that $s'm = \operatorname{lcm}(m,n)$.

To clarify, I understand that the algorithm can't divide by zero, but if you continue the pattern:
$$s'' = s - s'*q$$ $$t'' = t - t'*q$$ you get an $s''$ and $t''$ such that: $$s''*m + t''*n = 0$$ Then taking this $s''$, multiplying it by the original $m$, you see that this is the $lcm(m, n)$. This seems to be true consistently, but I haven't been able to find a counterproof, contradiction, counterexample, etc, so I was wondering if anyone knew how to disprove it, or if there was a proof to verify this was always the case.

• What do you mean by "taking the algorithm one step further"? The algorithm can't be taken one step further, without dividing by zero. – Gerry Myerson Apr 21 '14 at 13:04
• This is evidently not true: $1000\cdot2-500\cdot 4=0$, but $2000$ is of course not the lowest common multiple of $2$ and $4$. It's trivial to see that $s'm$ is a common multiple of $m$ and $n$, though. – egreg Apr 21 '14 at 13:42
• @egreg yes, it is trivial to see, but not trivial to prove. I am trying to determine what the proof is, to see if it is true in all cases. – Steverino Apr 21 '14 at 13:48
• If $s'm=-t'n$, then obviously $s'm$ is a common multiple of $m$ and $n$. But quite certainly not the least common multiple, unless you choose the minimal positive $s'$ (which is $n/\gcd(m,n)$), assuming $m\ne0$ and $n\ne0$. – egreg Apr 21 '14 at 13:52
• @GerryMyerson I understand that the algorithm can't divide by zero, but if you continue the pattern s'' = s - s'q, t'' = t - t'*q, you get an s and t such that sm + t*n = zero. Then taking this s, multiplying it by m, you see that this is the LCM of m and n. This seems to be true consistently, I haven't been able to find a counterproof, contradiction, counterexample, etc, so I was wondering if anyone knew how to disprove it, or if there was a proof to verify this was always the case. – Steverino Apr 21 '14 at 13:53

Let $a,b$ be two positive integers. Euclid's algorithm produces unique sequences $(r_n),(s_n),(t_n)$ such that :

• $r_0=a$, $r_1=b$ and $r_{n+1} = r_{n-1} - q_n r_n$ (with usual conditions on $(r_{n+1},q_n)$).

• $s_0=1$, $s_1=0$, $t_0=1$, $t_1=1$ and $s_{n+1} = s_{n-1} - q_n s_n$, $t_{n+1} = t_{n-1} - q_n t_n$. This implies $r_n = s_n a_n + t_n b_n$.

Let $r_N$ be the last remainder. Then $r_N = s_N a + t_N b$ is Bezout's relation for $\gcd(a,b)$, and $0 = r_{N+1} = s_{N+1} a + t_{N+1} b$.

You are asking why $|r_{N+1} a| = |t_{N+1} b|$ is equal to ${\rm lcm}(a,b)$. Note that the sequence $w_n := s_{n} r_{n+1} - s_{n+1} r_{n}$ is constant and so $w_N=w_0$. But $$w_N = s_{N+1} r_N = s_{N+1}.\gcd(a,b)$$ and $$w_0 = b.$$ Combining with the fact that $\gcd(a,b).{\rm lcm}(a,b)=ab$, this implies $s_{N+1} a = {\rm lcm}(a,b)$.

• You definitely understood and clarified my question well! But I could not understand the steps taken to come to the answer. Where you wrote |rN+1a| did you mean |sN+1a|? Also, why is (s(n)r(n+1))−s(n+1)r(n)) constant? – Steverino Apr 21 '14 at 14:49
• Your are right there is a typo. About $w_n$, just compute $w_{n+1}$ with the induction formula (and in fact it is $(-1)^n w_n$ which is constant). – user10676 Apr 21 '14 at 17:21
• I suspect your answer is right since you understood what I was asking, but I don't understand the last two lines, in other words I don't understand why $$w_0 = b.$$ or why $$s_{N+1} a = {\rm lcm}(a,b)$$ is implied. – Steverino Apr 21 '14 at 19:05
• $w_n$ is defined to be $s_nr_{n+1}-s_{n+1}r_n$, so $w_0=s_0r_1-s_1r_0$. But $r_0=a$, $r_1=b$, $s_0=1$, $s_1=0$, so $w_0=b$. – Gerry Myerson Apr 22 '14 at 1:23