# Why does the Euclidean algorithm for finding GCD work?

I am having trouble understanding why the Euclidean algorithm for finding the GCD of two numbers always works?

I found some resources here (http://www.cut-the-knot.org/blue/Euclid.shtml), and here(http://sites.math.rutgers.edu/~greenfie/gs2004/euclid.html).

But I am a little confused about how they approach it here. I understand that if we have two numbers, a and b, then the greatest common divisor of a and b has to be less than a, and if a divides b, then a will have to be the GCD.

But I am confused about what happens when:

b=a*q+r So now, we are saying that we take a/r, correct? Why should we do this at all?

• Your equation should be $b=aq+r$ not ${b\over a} =aq+r$. Does it make more sense now? – saulspatz Oct 3 '19 at 19:44
• A small point is in your statement of "... the greatest common divisor of a and b has to be less than a, ...", it should be that the gcd is less than or equal to a instead (with this assuming $a$ is a positive integer). – John Omielan Oct 3 '19 at 20:16
• @saulspatz Done! But that was not my confusion! – user681443 Oct 6 '19 at 0:04

I will try to explain

why the Euclidean algorithm for finding the GCD of two numbers always works

by using a standard argument in number theory: showing that a problem is equivalent to the same problem for smaller numbers.

Start with two numbers $$a > b \ge 0$$. You want to know two things:

1. their greatest common divisor $$g$$,

2. and how to represent $$g$$ as a combination of $$a$$ and $$b$$

It's clear that you know both of these things in the easy special case when $$b = 0$$.

Suppose $$b > 0$$. The divide $$a$$ by $$b$$ to get a quotient $$q$$ and a remainder $$r$$ strictly smaller than $$b$$: $$a = bq + r. \quad \text{(*)}$$

Now any number that divides both $$a$$ and $$b$$ also divides $$r$$, so divides both $$b$$ and $$r$$. Also any number that divides both $$b$$ and $$r$$ also divides $$a$$, so divides both $$a$$ and $$b$$. That means that the greatest common divisor of $$a$$ and $$b$$ is the same as the greatest common divisor of $$b$$ and $$r$$, so (1) has the same answer $$g$$ for both those pairs.

Moreover, if you can write $$g$$ as a combination of $$b$$ and $$r$$ then you can write it as a combination of $$a$$ and $$b$$ (substitute in (*)). That means if you can solve (2) for the pair $$(b,r)$$ then you can solve it for the pair $$(a,b)$$.

Taken together, this argument shows that you can replace your problem for $$(a,b)$$ by the same problem for the smaller pair $$(b,r)$$. Since the problem can't keep getting smaller forever, eventually you will reach $$(z, 0)$$ and you're done.

• This was really helpful! Thank you so much! – user681443 Oct 6 '19 at 0:03

Remember that $$\gcd(x, y) \vert (ax+by)$$ for any linear combination of x and y, and that the smallest possible positive linear combination will always be the $$\gcd$$.

The Euclidean algorithm is designed to create smaller and smaller positive linear combinations of $$x$$ and $$y$$. Since any set of positive integers has to have a smallest element, this algorithm eventually has to end. When it does (i.e., when the next step reaches $$0$$), you've found your $$\gcd$$.

Key to your question is the Well-Ordering Principle. It guarantees the existence of a least element for non-empty subsets of the natural numbers.

The GCD algorithm comes from two principles, the division algorithm and that given any two integers with a common factor, their sum and difference are both divisible by that common factor.

Suppose you have two natural numbers x and y each divisible by q. Then x=aq and y=bq for some natural numbers a and b. x+y = q(a+b), so is divisible by q. (x-y)=q(a-b) and again is divisible by q.

The Division Algorithm guarantees given a and b, with ab. So s must be less than b and greater than zero.

Now suppose you want to find the GCD of a and b.

By the division algorithm we know for some r and s, a=rb+s. Suppose g divides a and b. Since it divides b, it divides rb. Since it also divides a, it also divides a-rb as proven earlier. s is (a-rb) so we have proven g divides s. Why also have that s is smaller than b.

By iteration we have that b=ps+q. The division algorithm gives us p and q, with q and b having a common factor.

At each step, the remainder gets smaller and smaller.

When the remainder is zero, the previous remainder is the common factor of the original two numbers.