For $a,b \in \mathbb{Z}$, a positive integer $c$ is said to be a common divisor of $a$ and $b$ if $c\mid a$ and $c\mid b$.

$c$ is the greatest common divisor of $a$ and $b$ if it is a common divisor of $a,b$ and for any common divisor $d$ of $a$ and $b$, we have $d\mid c$.

The Proof

For all $a,b \in \mathbb{Z^{+}}$ there exists a unique $c \in \mathbb{Z^{+}}$, that is the greatest common divisor of $a,b$.

Let $S = \{as + bt: s,t\in \mathbb{Z}, as+bt > 0\}$. Since $ S \neq \emptyset$, then by the WOP, S has a least element $c$. We claim $c$ is a greatest common denominator of $a,b$.

My Problem

$S = \{as + bt: s,t\in \mathbb{Z}, as+bt > 0\}$. I have no idea what this has to do with the greatest common divisor. I understand the WOP ensures the existence of a smallest element, but why can I just claim this as the GCD?

  • $\begingroup$ That's not a proof of the greatest common divisor. That's a proof of the least common multiple. $\endgroup$ – fleablood Apr 3 '17 at 3:11
  • $\begingroup$ The proof of gcd would be to let S={k| k|a,k||b}. It's not empty as 1 is in it. So it has a max element c. Gotta prove all divisors divide c $\endgroup$ – fleablood Apr 3 '17 at 3:18
  • $\begingroup$ @fleablood this comes from the book "Discrete and Combinatorial Mathematics: An Applied Introduction" by Ralph P. Grimaldi. Maybe an error? $\endgroup$ – Dunka Apr 3 '17 at 5:46
  • $\begingroup$ Oops. I assumed those had to be positive integers. So, yes this is the gcd. But you have to continue the prove to see that this is so. It's not imediately apparent. Example: gcd(6,15) is 3 and the smallest 15s+6t is 1x15-2x6=3. And 3 is the gcd. $\endgroup$ – fleablood Apr 3 '17 at 6:00
  • 1
    $\begingroup$ Are you asking how to finish the quoted proof (isn't that done in your book?), or, instead, do you seek some intuition about why the proof uses the set $S$? $\endgroup$ – Bill Dubuque Apr 3 '17 at 16:11

This is related to Bezout identity.

Let $c_0=as_0+bt_0=\min(S)\tag{0}$

Then if $d$ is a common divisor of $a,b$ then $a=da'$ and $b=db'$ we have $as_0+bt_0=d(a's_0+b't_0)=c_0$

$\text{d divides a,b}\Rightarrow d\mid c_0\tag{1}$

On the other hand for $c\in S$, we have $c=as+bt=c_0q+r=(as_0+bt_0)q+r$

So $r=(s-s_0q)a+(t-t_0q)b\ \overset{?}{\in} S\quad$ but $0\le r<c_0$ by euclidian division definition.

If $r>0$ this contradict the fact that $c_0$ is $\min(S)$, so $r=0$ and $c=c_0q$

Note: since $q\ge 1$ then $c\ge c_0$ ($q\ge 0$ integer, and cannot be $0$, else $c=0\notin S$). We already know it from the minimum assertion, but it's good to have it back as a verification.

$c\in S\Rightarrow c\text{ is a multiple of }c_0\tag{2}$

Using the same method of euclidian division by $c_0$, we can show that $a$ and $b$ are also multiples of $c_0$. (note: $q,r$ are dummy variables, they are not the same than previously).

$a=c_0q+r=(as_0+bt_0)q+r$ with $0\le r<c_0$ so $r=(1-s_0q)a+(-t_0q)b\overset{?}{\in} S$ and we conclude like previously, same with $b$.

$a,b\ \text{ are multiples of } c_0\tag{3}$

Combining $(0),(1),(2),(3)$ we proved that $c_0=\gcd(a,b)$ and that $c_0$ is the smallest number reachable by a relation of type $S$ whose elements are all multiples of $c_0$.

To put this in everyday words: if two numbers are multiple of $3$ for instance, then their sum and their difference is also a multiple of $3$. Plus if they are not equal, the smallest possible difference is $3$.

Replace $3$ by $\gcd(a,b)$ and this is exactly what is mathematically written above.

  • 1
    $\begingroup$ In paragraph 4 how do you know c_0 is a common divisor? $\endgroup$ – fleablood Apr 3 '17 at 6:30
  • $\begingroup$ @fleablood you are right, it is not written explicitly, I'll edit, this is equation (3). $\endgroup$ – zwim Apr 3 '17 at 8:20

We are asked to show the existence and uniqueness of the GCD denoted as $c$ of two integers $a,b$. There are two parts of of this proof: Showing the existence and showing the uniqueness. To show the existence we must show there is a $c$ that divides $a,b$ and for any common divisor $d$ of $a,b$, $d|c$.

Part I: Existence

1) Let $S = \{as+bt|s,t \in \mathbb{Z},as+bt > 0\}$. Since $S \neq \emptyset$, by WOP, $S$ has a smallest element $c$, which we will call the GCD.

2) Will now show any divisor $d$ also divided $c$. $c \in S \implies c =ax+by$ and any $d \in \mathbb{Z} \land d|a \land d|b \implies d|(ax+by) \implies d|c$

3) We now show that $c|a$ and $c|b$. If $c$ doesn't divide $a$, then $a = qc + r$ where $q,r \in \mathbb{Z^+} \land 0 < r < c \implies r = a - qc = a - q(ax + by) = a - qax - qby = a(1-qx) + (-qy)b \implies r \in S$ this contradicts that $c$ is the smallest element in $S$. Similar arguments apply for b

4) We have shown $c|a \land c|b \land d|c$ for any divisor $d$ of $a,b$, so now we must show that $c$ is unique.

Part II: Uniqueness

1) If $c_1,c_2$ both satisfy the conditions of GCD, then one is GCD and one is common divisor. If $c_1$ is GCD and $c_2$ is CD, then $c_2|c_1$ the other way around, we have $c_1|c_2$ which means $c_1 = c_2$ because they are both positive.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.