Editing Euclidean algorithm (section)

=== Procedure ===
{{Euclidean algorithm steps}}
The Euclidean algorithm can be thought of as constructing a sequence of non-negative integers that begins with the two given integers <math>r_{-2} = a</math> and <math>r_{-1} = b</math> and will eventually terminate with the integer zero: <math>\{ r_{-2} = a,\ r_{-1} = b,\ r_0,\ r_1,\ \cdots,\ r_{n-1},\ r_n = 0 \}</math> with <math>r_{k+1} < r_k</math>. The integer <math>r_{n-1}</math> will then be the GCD and we can state <math>\text{gcd}(a,b) = r_{n-1}</math>. The algorithm indicates how to construct the intermediate remainders <math>r_k</math> via [[Euclidean division|division-with-remainder]] on the preceding pair <math>(r_{k-2},\ r_{k-1})</math> by finding an integer quotient <math>q_k</math> so that:
: <math>r_{k-2} = q_k \cdot r_{k-1} + r_k \text{, with } \ r_{k-1} > r_k \geq 0.</math>

Because the sequence of non-negative integers <math>\{ r_k \}</math> is strictly decreasing, it eventually [[Well-ordering principle|must terminate]]. In other words, since <math>r_k \ge 0</math> for every <math>k</math>, and each <math>r_k</math> is an integer that is strictly smaller than the preceding <math>r_{k-1}</math>, there eventually cannot be a non-negative integer smaller than zero, and hence the algorithm must terminate. In fact, the algorithm will always terminate at the {{math|''n''}}th step with <math>r_n</math> equal to zero.<ref>{{Harvnb|Stark|1978|p=18}}</ref>

To illustrate, suppose the GCD of 1071 and 462 is requested. The sequence is initially <math>\{r_{-2} = 1071,\ r_{-1} = 462 \}</math> and in order to find <math>r_0</math>, we need to find integers <math>q_0</math> and <math>r_0 < r_{-1}</math> such that:
: <math>1071 = q_0 \cdot 462 + r_0</math>.

This is the quotient <math>q_0 = 2</math> since <math>1071 = 2 \cdot 462 + 147</math>. This determines <math>r_0 = 147</math> and so the sequence is now <math>\{1071,\ 462,\ r_0 = 147 \}</math>. The next step is to continue the sequence to find <math>r_1</math> by finding integers <math>q_1</math> and <math>r_1 < r_0</math> such that:
: <math>462 = q_1 \cdot 147 + r_1</math>.

This is the quotient <math>q_1 = 3</math> since <math>462 = 3 \cdot 147 + 21</math>. This determines <math>r_1 = 21</math> and so the sequence is now <math>\{1071,\ 462,\ 147,\ r_1 = 21 \}</math>. The next step is to continue the sequence to find <math>r_2</math> by finding integers <math>q_2</math> and <math>r_2 < r_1</math> such that:
: <math>147 = q_2 \cdot 21 + r_2</math>.

This is the quotient <math>q_2 = 7</math> since <math>147 = 7 \cdot 21 + 0</math>. This determines <math>r_2 = 0</math> and so the sequence is completed as <math>\{1071,\ 462,\ 147,\ 21,\ r_2 = 0 \}</math> as no further non-negative integer smaller than <math>0</math> can be found. The penultimate remainder <math>21</math> is therefore the requested GCD:
: <math>\text{gcd}(1071,\ 462) = 21.</math>

We can generalize slightly by dropping any ordering requirement on the initial two values <math>a</math> and <math>b</math>. If <math>a = b</math>, the algorithm may continue and trivially find that <math>\text{gcd}(a,\ a) = a</math> as the sequence of remainders will be <math>\{a,\ a,\ 0\}</math>. If <math>a < b</math>, then we can also continue since <math>a \equiv 0 \cdot b + a</math>, suggesting the next remainder should be <math>a</math> itself, and the sequence is <math>\{a,\ b,\ a,\ \cdots \}</math>. Normally, this would be invalid because it breaks the requirement <math>r_0 < r_{-1}</math> but now we have <math>a < b</math> by construction, so the requirement is automatically satisfied and the Euclidean algorithm can continue as normal. Therefore, dropping any ordering between the first two integers does not affect the conclusion that the sequence must eventually terminate because the next remainder will always satisfy <math>r_0 < b</math> and everything continues as above. The only modifications that need to be made are that <math>r_{k} < r_{k-1}</math> only for <math>k \ge 0</math>, and that the sub-sequence of non-negative integers <math>\{ r_{k-1} \}</math> for <math>k \ge 0</math> is strictly decreasing, therefore excluding <math>a = r_{-2}</math> from both statements.