Please Login to access more options.

Problem 42 (The GCD Theorem Proof)

Prove the GCD Theorem.

Theorem (The GCD Theorem)

Let $a$ and $b$ be nonzero integers. The greatest common divisor of $a$ and $b$ is an integer linear combination of $a$ and $b$, or symbolically we have $\gcd(a,b)\in\text{span}(a,b)$. In addition, the smallest positive integer linear combination of $a$ and $b$ is $\gcd(a,b)$.

Solution

Let $a, b \in \mathbb{Z}$ where $a, b \neq 0$. Let $S = \mathbb{N} \cap \langle a, b \rangle$. Note that either $a$ or $-a$ is in $S$, so $S\neq \emptyset$. By the Well Ordering Principle we know that the set $S$ must contain a least element since $S \subseteq \mathbb{N}$, therefore let $d = \min( S )$. It follows that $d \in \langle a, b \rangle$, and therefore may be written as an integer linear combination of $a$ and $b$, which symbolically is

$$ \begin{equation} d = s \cdot a + t \cdot b. \end{equation} $$

We now must show that $d|a$ and that $d|b$. We start by showing that when we divide $a$ by $d$, we obtain zero remainder. Using the division algorithm, we have $$ a = q \cdot d + r $$ for some $q, r, \in \mathbb{Z}$ where $0 \leq r < d$. Working now with the equation from the division algorithm for $a$ we see that $r$ may be written in terms of $a$ and $d$, and we compute $$ \begin{align} r &= a - q \cdot d \\ &= a - q\; ( s \cdot a + t \cdot b ) \\ &= a - q \cdot s \cdot a - q \cdot t \cdot b \\ &= ( 1 - q \cdot s ) \; a - q \cdot t \cdot b \\ &= ( 1 - q \cdot s ) \; a + ( -q \cdot t )\; b. \end{align} $$

Here we see that $r$ is an integer linear combination of $a$ and $b$ and therefore $r \in \langle a, b \rangle$. However, since $d = \min( S )$ we know that $d$ is the smallest positive element in the span of $a$ and $b$, and since $0 \leq r < d$ it follows that $r =0$. Thus we see that $d|a$, and a similar proof shows that $d|b$ as desired.

We now prove that $d$ is the greatest common divisor. Let $d' \in \mathbb{N}$ such that $0 < d'$, and where $d'| a$ and $d'|b$. This means that there exists some $q_3, q_4 \in \mathbb{Z}$ such that $$ q_3 \cdot d' = a \\ q_4 \cdot d' = b. $$ Rewriting $d$ in terms of $d'$ we compute $$ \begin{align} d &= s \cdot a + t \cdot b \\ &= s\; ( q_3 \cdot d' ) + t\; ( q_4 \cdot d' ) \\ &= ( s \cdot q_3 + t \cdot q_4 ) \; d' \end{align} $$ where we find that since $0 < d$ and $0 < d'$ it follows that $1\leq ( s \cdot q_3 + t \cdot q_4 )$. And thus we know that $d\geq d'$. This gives our desired result that $d = \gcd( a, b )$.

Q.E.D.

Tags
  • When you are ready to submit this written work for grading, add the phrase [[!Submit]] to your page. This will tell me that you have completed the page (it's past rough draft form, and you believe it is in final draft form). Don't type [[!Submit]] on a rough draft.
  • If I put [[!NeedsWork]] on your page, then your job is to review what I've written, address any comments made, and then delete all the comments I made. When you have finished reviewing your work, leave [[!NeedsWork]] on your page and type [[!Submit]]. (Both tags will show up). This tells me you have addressed the comments.
  • I'll mark your work with [[!Complete]] after you have made appropriate revisions.