1
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ Every exposition of the Euclidean algorithm should explain this. What exposition are you reading? $\endgroup$ – Bill Dubuque Apr 23 '15 at 15:59
  • $\begingroup$ 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. $\endgroup$ – Niket Parikh Apr 23 '15 at 16:10
  • $\begingroup$ @BillDubuque : Do you know of published expositions of the algorithm that say what my answer below says? $\endgroup$ – Michael Hardy Jul 6 '15 at 19:19
  • 1
    $\begingroup$ @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 $\endgroup$ – Bill Dubuque Jul 6 '15 at 19:45
  • 1
    $\begingroup$ @Michael It is also mentioned here in many of my posts, e.g. this one which gives a conceptual presentation. $\endgroup$ – Bill Dubuque Jul 6 '15 at 19:47
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Niket Parikh Apr 23 '15 at 16:17
  • $\begingroup$ @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$. $\endgroup$ – Andreas Blass Apr 23 '15 at 16:26
  • $\begingroup$ 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$. $\endgroup$ – paw88789 Apr 23 '15 at 16:33
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Does make great sense! Now my blurred up concepts are getting clearer. $\endgroup$ – Niket Parikh Apr 23 '15 at 16:56
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.