foo=bar

Link Testing

HTML entities

Display space

Unsupported Elements

The Euclidean algorithm can be thought of as constructing a sequence of non-negative integers that begins with the two given integers ${\\displaystyle r_{-2}=a}$ and ${\\displaystyle r_{-1}=b}$ and will eventually terminate with the integer zero: ${\\displaystyle \\{r_{-2}=a,\\ r_{-1}=b,\\ r_{0},\\ r_{1},\\ \\cdots ,\\ r_{n-1},\\ r_{n}=0\\}}$ with ${\\displaystyle r_{k+1}<r_{k}}$. The integer ${\\displaystyle r_{n-1}}$ will then be the GCD and we can state ${\\displaystyle {\\text{gcd}}(a,b)=r_{n-1}}$. The algorithm indicates how to construct the intermediate remainders ${\\displaystyle r_{k}}$ via division-with-remainder on the preceding pair ${\\displaystyle (r_{k-2},\\ r_{k-1})}$ by finding an integer quotient ${\\displaystyle q_{k}}$ so that:

${\\displaystyle r_{k-2}=q_{k}\\cdot r_{k-1}+r_{k}{\\text{, with }}\\ r_{k-1}>r_{k}\\geq 0.}$

Because the sequence of non-negative integers ${\\displaystyle \\{r_{k}\\}}$ is strictly decreasing, it eventually must terminate. In other words, since ${\\displaystyle r_{k}\\geq 0}$ for every ${\\displaystyle k}$, and each ${\\displaystyle r_{k}}$ is an integer that is strictly smaller than the preceding ${\\displaystyle r_{k-1}}$, 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 n-th step with ${\\displaystyle r_{n}}$ equal to zero.^[15]

To illustrate, suppose the GCD of 1071 and 462 is requested. The sequence is initially ${\\displaystyle \\{r_{-2}=1071,\\ r_{-1}=462\\}}$ and in order to find ${\\displaystyle r_{0}}$, we need to find integers ${\\displaystyle q_{0}}$ and ${\\displaystyle r_{0}<r_{-1}}$ such that:

${\\displaystyle 1071=q_{0}\\cdot 462+r_{0}}$.

This is the quotient ${\\displaystyle q_{0}=2}$ since ${\\displaystyle 1071=2\\cdot 462+147}$. This determines ${\\displaystyle r_{0}=147}$ and so the sequence is now ${\\displaystyle \\{1071,\\ 462,\\ r_{0}=147\\}}$. The next step is to continue the sequence to find ${\\displaystyle r_{1}}$ by finding integers ${\\displaystyle q_{1}}$ and ${\\displaystyle r_{1}<r_{0}}$ such that:

${\\displaystyle 462=q_{1}\\cdot 147+r_{1}}$.

This is the quotient ${\\displaystyle q_{1}=3}$ since ${\\displaystyle 462=3\\cdot 147+21}$. This determines ${\\displaystyle r_{1}=21}$ and so the sequence is now ${\\displaystyle \\{1071,\\ 462,\\ 147,\\ r_{1}=21\\}}$. The next step is to continue the sequence to find ${\\displaystyle r_{2}}$ by finding integers ${\\displaystyle q_{2}}$ and ${\\displaystyle r_{2}<r_{1}}$ such that:

${\\displaystyle 147=q_{2}\\cdot 21+r_{2}}$.

This is the quotient ${\\displaystyle q_{2}=7}$ since ${\\displaystyle 147=7\\cdot 21+0}$. This determines ${\\displaystyle r_{2}=0}$ and so the sequence is completed as ${\\displaystyle \\{1071,\\ 462,\\ 147,\\ 21,\\ r_{2}=0\\}}$ as no further non-negative integer smaller than ${\\displaystyle 0}$ can be found. The penultimate remainder ${\\displaystyle 21}$ is therefore the requested GCD:

${\\displaystyle {\\text{gcd}}(1071,\\ 462)=21.}$

We can generalize slightly by dropping any ordering requirement on the initial two values ${\\displaystyle a}$ and ${\\displaystyle b}$. If ${\\displaystyle a=b}$, the algorithm may continue and trivially find that ${\\displaystyle {\\text{gcd}}(a,\\ a)=a}$ as the sequence of remainders will be ${\\displaystyle \\{a,\\ a,\\ 0\\}}$. If ${\\displaystyle a<b}$, then we can also continue since ${\\displaystyle a\\equiv 0\\cdot b+a}$, suggesting the next remainder should be ${\\displaystyle a}$ itself, and the sequence is ${\\displaystyle \\{a,\\ b,\\ a,\\ \\cdots \\}}$. Normally, this would be invalid because it breaks the requirement ${\\displaystyle r_{0}<r_{-1}}$ but now we have ${\\displaystyle a<b}$ 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 ${\\displaystyle r_{0}<b}$ and everything continues as above. The only modifications that need to be made are that ${\\displaystyle r_{k}<r_{k-1}}$ only for ${\\displaystyle k\\geq 0}$, and that the sub-sequence of non-negative integers ${\\displaystyle \\{r_{k-1}\\}}$ for ${\\displaystyle k\\geq 0}$ is strictly decreasing, therefore excluding ${\\displaystyle a=r_{-2}}$ from both statements.