# My attempt to prove GCD exists

Please review my attempt to prove a theorem. Any mistakes you point would be highly appreciated by me.

To prove the theorem, I'll be using the following properties which I'm assuming have already been proven.

Properties:

1. $n|0$ (every integer divides $0$)
2. $d|n$ and $d|m \implies d|(an + bm)$ (linearity property)
3. $d|n$ and $n \neq 0 \implies |d| \leq |n|$

THEOREM:

Given any two integers $a$ and $b$, there is a common divisor $d$ of $a$ and $b$ of the form:

$$d = ax + by$$

where $x$ and $y$ are integers. Moreover, every common divisor of $a$ and $b$ divides $d$.

PROOF:

We will do an induction on the value of $|a| + |b|$.

Induction base: If $a = b = 0$, clearly $d = 0$ and every integer divides $0$. So, the theorem is true when $|a| + |b| = 0.$

Induction hypothesis: Let us assume that the theorem is true when $|a| + |b| < n$ where $n$ is an integer.

Induction: Now, let us see what happens when $|a| + |b| = n.$

There are two possible cases:

• $|b| = 0$.
• $|b| > 0$.

When $|b| = 0, d = |a|$. This can be justified as follows. $|a|$ divides $a$ and $0$. Every integer that divides $a$ and $0$, also divides $\text{sgn}(a).a = |a|$.

When $|b| > 0$, without loss of generality, we can assume $|a| \geq |b|.$

$|a| = n - |b| < n$.

So, $|a| = (|a| - |b|) + |b| < n$.

From the induction hypothesis, there is an integer $d$ such that:

1. $d|(|a| - |b|)$.
2. $d|(|b|)$.
3. $d = (|a| - |b|)x + |b|y$ where $x$ and $y$ are integers.

From (1) and (2), $d|(|a| - |b|) + |b|$ or $d|(|a|)$ or $d|\text{sgn}(a).|a|$ or $d|a$.

From (2), $d|(|b|)$ or $d|\text{sgn}(b).|b|$ or $d|b.$

From (3), $d = |a|x + |b|(y - x)$ or $d = a(\text{sgn}(a).x) + b(\text{sgn}(b)(y - x))$.

If $c|a$ and $c|b$, from the linearity property,

$c|a(\text{sgn}(a).x) + b(\text{sgn}(b)(y - x))$ or $c|d$.

Q.E.D.

-
Daniel, In my proof I have omitted the step of dealing with a < 0, b < 0 separately. You believe that it can not be omitted. If you are right, my proof should have an error. Do you find any error in my proof or do you agree that the a < 0, b < 0 related step can be omitted? –  Lone Learner Jan 28 '12 at 15:28
If the problem were ONLY to prove that a gcd exists, it would be simpler. The set of common divisors always contains $1$, so it's not empty, and it cannot be infinite, since the gcd of of two numbers is no more than the max of the two numbers. –  Michael Hardy Jan 28 '12 at 17:13
Lone Learner: I have gone through the proof. It is correct. I don't like your use of "or" many ($7$?) times close to the end to mean essentially "and therefore." Too easily confused with logical or. The proof would be much clearer if you got rid of absolute values. Once $a$ and $b$ non-negative have been dealt with, the rest is trivially dealt with. –  André Nicolas Jan 28 '12 at 18:02
@LoneLearner: you were right and I think the proof is an interesting departure from the standard one I had cited. –  daniel Jan 28 '12 at 23:46
And where is the question? If there is no mistake, does "Yes you are right." count for an answer? –  awllower Feb 22 '13 at 11:50