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? – Bill Dubuque Apr 23 '15 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. – Niket Parikh Apr 23 '15 at 16:10
• @BillDubuque : Do you know of published expositions of the algorithm that say what my answer below says? – Michael Hardy Jul 6 '15 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 – Bill Dubuque Jul 6 '15 at 19:45
• @Michael It is also mentioned here in many of my posts, e.g. this one which gives a conceptual presentation. – Bill Dubuque Jul 6 '15 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. – Niket Parikh Apr 23 '15 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$. – Andreas Blass Apr 23 '15 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$. – paw88789 Apr 23 '15 at 16:33

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. – Niket Parikh Apr 23 '15 at 16:56

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.