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".
[Math] Not able to understand the procedure used to find GCD of two numbers through Euclid’s algorithm.
euclidean-algorithmgcd-and-lcmnumber theory
Best Answer
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$.