Why do we eventually end up with $0$ in Euclidean Algorithm?

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

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?

Answer 5

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