8
$\begingroup$

I'm new to number theory, I just understood the proof of Euclidean Algorithm and how it cleverly uses the fact that $\mathrm{gcd}(a,b) = \mathrm{gcd}(b,r)$ repeatedly, where $a$ is the dividend, $b$ is the divisor and $r$ is the remainder.

Although one thing, I still don't understand is that, why do we always eventually end up with a zero anyway? What's the logic behind this?

$\endgroup$
  • 1
    $\begingroup$ @TheShortOne Can you comment (or edit) to tell us what you expect for your bounty, since this old question has several good answers already. $\endgroup$ – Ethan Bolker Oct 30 '18 at 17:25
  • $\begingroup$ @EthanBolker alright, what's bounty, and what do you mean "expect for your bounty"... Did we have a new update or something while I was gone. There are so many nice answers here already. I'll accept best of theee answers after a while, I'm kinda caught up in something. $\endgroup$ – William Nov 1 '18 at 16:27
  • $\begingroup$ If you check here you will see that @TheShortOne will give 200 reputation points for an answer that's in some way better than the ones here already. Since I think those answers are pretty good I wrote to ask him what improvements he would want to see for the 200 points. $\endgroup$ – Ethan Bolker Nov 1 '18 at 17:13
5
$\begingroup$

Assuming $a$ and $b$ are positive and $a>b$, by definition, $r$ is less than $b$. Then $b<a$ and $r<b$, so you have smaller numbers than you started with. If $a<b$, then just switch $a$ and $b$. If $a=b$, then $\gcd(a,\,b)=a=b$. Since $b$ and $r$ are still non-negative (also by definition), the only possibility is to go to zero. The numbers are getting smaller and remaining non-negative.

$\endgroup$
  • 1
    $\begingroup$ I think you need to clarify that $a, b$ are in the natural numbers and possibly offer that as further justification. $f(x) = (0.5)^x+1$ is monotonically decreasing and non-negative, but does not converge to 0. $\endgroup$ – Evan Weissburg Oct 13 '18 at 17:01
  • $\begingroup$ It is assumed that $a$ and $b$ are integers, since it doesn't make a lot of sense to take $\gcd$ of non-integers. What would the meaning be in that case? $\endgroup$ – HackerBoss Oct 13 '18 at 21:55
  • $\begingroup$ $\gcd$ of rationals makes sense, by first putting fractions with same denominator = LCM of the denominators. $\endgroup$ – G Cab Oct 30 '18 at 17:08
2
$\begingroup$

The remainder decreases strictly. If we do not end up with $0$, then $\mathbb N^*$ has no lower bounds, which is not true.

$\endgroup$
2
$\begingroup$

Rather than attempting to take in the beauty of the Euclidean Algorithm all at once, consider first another algorithm.

Take any coordinate pair $(a_0,b_0)$ on the grid $\mathbb N^{\gt 0} \times \mathbb N^{\gt 0}$.

We are going to keep applying a function (algorithm) until this ordered pair finds itself on the diagonal, the set

$\quad \quad \quad \Delta_{\mathbb N^{\gt 0}} = \{(x,x) : x \in \mathbb N^{\gt 0} \}$

This is the function,
$$ F(m,n) = \left\{\begin{array}{lr} (m-n,n) & \text{if } m \gt n\\ (m,n-m) & \text{if } n \gt m\\ \text{ not defined } & \text{if } m = n \end{array}\right\} $$

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= PSEUDO CODE:

$P_0 = (a_0,b_0)$
$n = 0$
$\text{Do While Pair } P_n \text{ in domain of } F$:
$\quad n = n + 1$
$\quad P_n = F(P_{n-1})$
$\text{End While}$
$\text{Print } P_n$

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Now as this algorithm runs, we have either the $1^{st}$ or $2^{nd}$ coordinates being replaced with a smaller number that is always greater than zero. When both numbers 'hit the diagonal' the process ends, and that might happen when they both wind up on $(1,1)$. If one coordinate hits $1$ it will be left alone and $F$ will keep decrementing the other coordinate by $1$ until it also 'gets there'.

So this 'one-step-at-time' subtraction algorithm will always end after $(m -1 ) + (n-1)$ steps (Euclidean division can always be done by repeated subtraction). Now the Euclidean algorithm is traversing this grid in the same way, although several steps can be combined when doing Euclidean division.

When the point gets to the diagonal, the two coordinates are equal to each other and equal to the gcd of the starting integers $a_0$ and $b_0$.

Observe that here we don't 'end up with 0'. Why bother with the last subtraction? The coordinates are equal and that last subtraction can be skipped. Also, we could also have the algorithm stop when either coordinate gets to $1$, since the starting numbers would then be relatively prime and both coordinates are going to wind up at $1$.

$\endgroup$
  • 1
    $\begingroup$ You might point out explicitly that this is just division by repeated subtraction. $\endgroup$ – Ethan Bolker Oct 30 '18 at 17:22
2
+200
$\begingroup$

There are a lot of fantastic answers to this question already, but here is another perspective on the problem.

We seek to show that $\forall a,b,\;a\geq b$, $r<\frac12a$.

Case 1: $b> \frac12a\;\to$ We know that in the expression $a=q\cdot b+r$, $q=1$. So, $$r=a-b<a-\frac12a=\frac12a$$

Case 2: $b\leq\frac12a\;\to$ Since $0\leq r<b\leq\frac12a$, $r<\frac12a$.

Either way, $r<\frac12a$.

This is very useful since it shows that the Euclidean Algorithm reduces rather quickly, and shows us that the Euclidean Algorithm has to converge to $0$.

$\endgroup$
1
$\begingroup$

That's only if you insist on taking it as far as it'll go. Programming a computer, it's easiest to just tell it to go all the way to $0$. Especially if you're programming it to work in Euclidean domains other than $\textbf Z$, in which you may have infinitely many units and it may or may not be obvious that they're units.

In $\textbf Z$, you can just stop when you encounter $1$ or $-1$. For example, compute $\gcd(8, 13)$. We have $13 = 8 \times 1 + 5$. Then $8 = 5 \times 1 + 3$. And then $5 = 3 \times 1 + 2$, $3 = 2 \times 1 + 1$. Do you really need to check that $2 = 1 \times 2 + 0$? I don't. Of course I already knew that $8$ and $13$ are coprime.

Now suppose that working in $\textbf Z[\sqrt 2]$ your calculations have taken you to the point where you have that $$241 + 175 \sqrt 2 = (1 + 3 \sqrt 2) \times 2 + (239 + 169 \sqrt 2).$$ Are you ready to conclude that your initial two numbers are coprime based on this? Or wouldn't you rather take it closer to where you can see the remainder $0$? And would you trust a computer to make this call at this point?

$\endgroup$

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.