Not able to understand the procedure used to find GCD of two numbers through Euclid's algorithm.

Question

Ok so I was just touring through the basic concepts of number theory and then this doubt suddenly hit me. We use Euclid's algorithm to find the GCD of two numbers, $a$ and $b$. First step: $a=b\times q_1+r_1$ where $q$ is some positive integer. Second step: $b=r_1\times q_2+r_2$ And so on all the way till we get remainder as zero and then the divisor in the last step is our GCD. Now what I am having trouble understanding is that why do we take $b$ as the dividend in the second step and remainder of the first step as the divisor in the second step? Why Not maybe something else like $bq_1$ as divisor? What I am asking for is an explanation to why we take the divisor in the first step as the dividend in the second? Sorry for repeating the same question again but I just wanted to make my question clear. P.S I have used the underscore to represent a subscript. So $q_1$ is "q subscript 1".

Answer 1

The Euclidean algorithm relies on the fact that if $a$ and $b$ are integers with $b>0$, then for any integer $k$, $\gcd(a,b)=\gcd(b, a-kb)$. In particular, using the division algorithm to write $a=bq+r$, with $0\le r<b$, we have $r=a-bq$, and so $\gcd(a,b)=\gcd(b,r)$. This explains why you go from dividend; divisor to divisor; remainder. You then iterate this process until you get to $0$.

For example: $\gcd(54, 21)=\gcd(21,12)=\gcd(12,9)=\gcd(9,3)=\gcd(3,0)=3$.

Answer 2

why we take the divisor in the first step as the dividend in the second?

Well. There are many proofs of the algorithm on the Web, so I suppose that you does not want a proof but an intuition. The best that you can do for this is to apply the algorithm and well understand how it works.

Use $a=24$ and $b=18$. The first step is:

$ 24 = 18 \times 1 + 6$

This means that $18$ is not a divisor of $24$ and the remainder of the division is $6$.

The second step is:

$18=6\times 3 +0$.

Why we have taken $18$? because we search a number that divides $b$ , and possibly divide also $a$. In this case we have taken this number $=3$. We have ,in fact,

$24=18 \times 1 + 6=(6\times 3) \times 1 +6= 6 \times 4$.

And this result shows also because we have chosen as divisor in the second step the remainder of the first step: simply we want to search if $18$ is a multiple of this remainder.

The algoritm terminate when we find a remanider $=0$, and, in this case it has only two steps.

Now use $a=24$ and $b=9$ and you can understand also the successive steps.

Answer 3

Maybe the simplest way to look at this is that $\gcd(a,b)=\gcd(a-b,b)$, and then iterate that.

If $e\mid a$ and $e\mid b$ then $e\mid (a-b)$.

If $e\mid (a-b)$ and $e\mid b$ then $e\mid a$.

If you can prove the two statement above (which is not hard) you can conclude:

Every divisor that $a$ and $b$ have in common is a divisor that $a-b$ and $b$ have in common; and

every divisor that $a-b$ and $b$ have in common is a divisor that $a$ and $b$ have in common.

This subtraction therefore does not alter the set of common divisors of the pair; therefore it does not alter the greatest one.

For example:

The divisors of $84$ are: $1,2,3,4,6,7,12,14,21,28,42,84$.

The divisors of $120$ are $1,2,3,4,5,6,8,10,12,15,20,24,30,40,60,120$.

The ones they have in common are $1,2,3,4,6,12$.

Now subtract: $120-84=36$.

The divisors of $36$ are $1,2,3,4,6,9,12,18,36$.

The divisors that $84$ and $36$ have in common is $1,2,3,4,6,12$.

The list of divisors the two numbers have in common did not change when we subtracted.