TITLE: Why does Euclid's algorithm taken one step past the GCD seem to yield the LCM?
QUESTION [3 upvotes]: 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.

REPLY [7 votes]: 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)$.
{"set_name": "stack_exchange", "score": 3, "question_id": 762933}