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