3
$\begingroup$

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.

$\endgroup$
  • 8
    $\begingroup$ What do you mean by "taking the algorithm one step further"? The algorithm can't be taken one step further, without dividing by zero. $\endgroup$ – Gerry Myerson Apr 21 '14 at 13:04
  • $\begingroup$ 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. $\endgroup$ – egreg Apr 21 '14 at 13:42
  • $\begingroup$ @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. $\endgroup$ – Steverino Apr 21 '14 at 13:48
  • 2
    $\begingroup$ 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$. $\endgroup$ – egreg Apr 21 '14 at 13:52
  • $\begingroup$ @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. $\endgroup$ – Steverino Apr 21 '14 at 13:53
7
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Steverino Apr 21 '14 at 14:49
  • $\begingroup$ 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). $\endgroup$ – user10676 Apr 21 '14 at 17:21
  • $\begingroup$ 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. $\endgroup$ – Steverino Apr 21 '14 at 19:05
  • 1
    $\begingroup$ $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$. $\endgroup$ – Gerry Myerson Apr 22 '14 at 1:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.