State/Greatest common divisors can be found with the Euclidean algorithm

From SlugmathWiki

Proposition
Proof
Metadata

Proposition: (Greatest common divisors can be found with the Euclidean algorithm) Let $a$ and $b$ be elements of a Euclidean domain (such as $\ZZ$ or $\RR[X]$, for example) and suppose that $b \neq 0$. Then, the greatest common divisor of $a$ and $b$ is equal to the last nonzero element of the remainder sequence obtained via the Euclidean algorithm.

Logical Connections

This statement logically relies on the following definitions and statements: Def/Integer, Def/Greatest common divisor, Def/Euclidean algorithm, State/Two out of three principle for divisibility

The following statements and definitions rely on the material of this page: State/Linear Diophantine equations can be solved with the Euclidean algorithm

To visualize the logical connections between this statements and other items of mathematical knowledge, you can visit the following cluster(s), and click the "Visualize" tab: Clust/Basic number theory

Let $a$ and $b$ be integers (or elements of a Euclidean domain), and suppose that $b \neq 0$. Let $r_{-2} = a$, and $r_{-1} = b$, and let $(q_k)$, $(r_k)$ be sequences of quotients and remainders obtained via the Euclidean algorithm. Let $t$ be the smallest natural number such that $r_{t+1} = 0$, i.e., $r_t$ is the last nonzero remainder in the sequence $(r_k)$.

Then, for all $k \geq 0$, we have:

$$r_{k-2} = q_{k} r_{k-1} + r_k.$$

Suppose that $d$ is a common divisor of $a$ and $b$. We prove that $d$ divides $r_k$ for all $k \geq -2$ by induction on $k$.

$k=-2,-1$.	For $k = -2$ and $k = -1$, the claim follows from the fact that $d$ is a common divisor of $a$ and $b$ and $r_{-2} = a$ and $r_{-1} = b$.
$k \geq 0$.	Now, suppose that $k \geq 0$, and the claim has been proven for all smaller values of $k$. In particular, $d$ divides $r_{k-1}$ and $r_{k-2}$. Since $r_k = r_{k-2} - q_k r_{k-1}$, the two out of three principle implies that $d$ divides $r_k$.
Hence $d$ divides $r_k$ for all $-2 \leq k \leq t$, and in particular, $d$ divides $r_t$.

On the other hand, we claim that $r_t$ divides $r_k$ for all $k$ between $-2$ and $t+1$. In other words, $r_t$ divides $r_{t-j}$ for all $-1 \leq j \leq t+2$. We prove this by induction on $j$ as follows:

$j=-1,0$.	When $j = -1$, $r_{t-j} = r_{t+1} = 0$, and $r_t$ certainly divides $0$. For $j = 0$, $r_{t-j} = r_t$, and $r_t$ divides itself.
$j \geq 1$.	Now, suppose that $1 \leq j \leq t+2$, and our claim (that $r_t$ divides $r_{t-j}$) has been proven for all smaller values of $j$. Then, we have: $$r_{t-j} = r_{t-(j-2)} + q_{t-(j-2)} r_{t-(j-1)}.$$ By the inductive hypothesis, $r_t$ divides $r_{t-(j-2)}$ and $r_{t-(j-1)}$. By the two out of three principle again, we find that $r_t$ divides $r_{t-j}$.
Therefore, $r_t$ divides $r_{t-j}$ for all $-1 \leq j \leq t+2$. In particular, $r_j$ divides $r_{-1}$ and $r_{-2}$.

To summarize, we have found the following to be true:

Every common divisor of $a$ and $b$ also divides $r_t$.
$r_t$ divides both $a$ and $b$.

This characterizes $r_t$ as a (the) greatest common divisor of $a$ and $b$.

State/Greatest common divisors can be found with the Euclidean algorithm

From SlugmathWiki

Logical Connections

Views

Personal tools

Navigation

Mathematics

Pegagogy

Search

Toolbox