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

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

• Every exposition of the Euclidean algorithm should explain this. What exposition are you reading? Apr 23, 2015 at 15:59
• Yeah many of them do explain but still I find them a bit complicated and out of my reach. So I thought if so,done here could simplify it. I was reading about this on Wikipedia. Apr 23, 2015 at 16:10
• @BillDubuque : Do you know of published expositions of the algorithm that say what my answer below says? Jul 6, 2015 at 19:19
• @Michael That's the subtractive form of the Euclidean algorithm which goes back to Euclid. Search Google Books for "subtractive Euclidean algorithm" for expositions, e.g. Stillwell, Elements of Number Theory p.22ff Jul 6, 2015 at 19:45
• @Michael It is also mentioned here in many of my posts, e.g. this one which gives a conceptual presentation. Jul 6, 2015 at 19:47

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

• Any proof or explanation for the fact that gcd(a,b)=gcd(b,a-kb)? I mean this fact does not really seem very intuitive and some explanation would help. Apr 23, 2015 at 16:17
• @NiketParikh To see that those two gcd's are the same, it might be easier to prove the stronger fact that all of the common divisors of $a$ and $b$ are also all of the common divisors of $b$ and $a-kb$. Apr 23, 2015 at 16:26
• And conversely all the common divisors of $b$ and $a-kb$ are common divisors of $a$ and $b$. Here's one direction. If $d$ is a common divisor of $a$ and $b$, then $a=md$ and $b=nd$ for some integers $m,n$. Then $a-kb=md-knd=(m-kn)d$. So $d$ is a divisor of $a-kb$, and of course it was already a divisor of $b$. Apr 23, 2015 at 16:33

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.

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.

• Does make great sense! Now my blurred up concepts are getting clearer. Apr 23, 2015 at 16:56