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:
- $n|0$ (every integer divides $0$)
- $d|n$ and $d|m \implies d|(an + bm)$ (linearity property)
- $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:
- $d|(|a| - |b|)$.
- $d|(|b|)$.
- $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.
This CW answer intends to remove the question from the Unanswered queue.
As remarked in the comments, your proof is correct. Cheers!