The Euclidean algorithm, for finding the gcd of two number, let $a,b;$ changes in each successive step the dividend to be the previous step's divisor, and divisor to be the previous step's remainder.
Say have initially, $a=442,$ as the dividend, and $b=45,$ as the divisor $b.$
My doubt is that, know that the remainder only plays a role in the algorithm, in the successive two steps, with it forming the divisor in the next step, and dividend in the further next step.
Also, relationship among the remainders in three successive steps, are used to prove the correctness of the algorithm. For, that we start backward, starting with the penultimate step.
But, the quotient seems is ignored, as just states the number of times the divisor divides into the dividend, in a step.
Request reason, why quotient cannot be used, to prove the correctness of the algorithm, as per my example below:
Say, have $a= bq+r\implies 442 = 9\cdot 45 + 37.$
Next, if $d$ is the $\gcd (442,45),$ then should have $d=(45,442 -45\cdot 9)=(37, 8)= (8,5)= (5,3)= (3,2)= (2,1).$
Let, $a=bq + r, 0\leq r \lt b, q\geq 1.$
Note: $q \geq 1$ as $r \lt b,$ say for $a=442, b=45, q=9, r=37;$ so in the next step have $a_1= 45, b_1= 37.$
$$ \begin{array}{|c|c|} \hline \text{Step #} & \text{dividend} & \text{divisor} & \text{quotient} & \text{remainder} \\ \hline 0 & 422 & 45 & 9 & 37 \\ 1 & 45 & 37 & 1 & 8 \\ 2 & 37 & 8 & 4 & 5 \\ 3 & 8 & 5 & 1 & 3 \\ 4 & 5 & 3 & 1 & 2 \\ 5 & 3 & 2 & 1 & 1 \\ 6 & 2 & 1 & 2 & 0 \\ \hline \end{array} $$
For the first step, have: $r_0= a_0-q_0\cdot b_0, 0\leq r_0 \lt b_0, q_0\geq 1.$
Next (second) step has $b_1 = r_0\cdot q_1+ r_1, 0\leq r_1\lt r_0, q_1\geq 1.$
Let, the algorithm exit in the $i-1$th step, when have $r_{i-1}=0.$
In the last step have, let: $a_{i-1}= b_{i-1}\cdot q_i + 0.$
In the penultimate (just before the last) step, have:
$a_{i-2}= b_{i-2}\cdot q_{i-2} + r_{i-2}\implies b_{i-2}= r_{i-2}\cdot q_{i-1}.$
In the previous (to penultimate) step, have:
$a_{i-2} = b_{i-2}\cdot q_{i-2}+ r_{i-2}.$
Or, $b_{i-3} = r_{i-3}\cdot q_{i-2} + r_{i-2}.$
Or, $r_{i-4} = r_{i-3}\cdot q_{i-2} + r_{i-2}.$
Or, $\frac{(r_{i-4} - r_{i-2})}{r_{i-3}} = q_{i-2}.$
So, can we prove the correctness of the algorithm using the help of quotients?