Proof that $Z$ is a gcd ring

Question

Recall the general definition of a gcd in a commutative ring $R$.

For $a \in R$, $\mathcal D(a)$ is the set of elements that divide $a$ and if $S \subset R$, $\mathcal D(S) = \cap_{s \in S} \mathcal D(s)$

We say that $d$ is a gcd of $a$ and $b$ and we write $d \in \gcd(a,b)$ whenever we have $ d \in \mathcal D(a,b) \subset \mathcal D(d) $.

I would like to prove that, within the ring $\mathbb Z$ every pair of natural numbers has a gcd, that is, $\forall a,b \in \mathbb{N} \quad \gcd(a,b) \neq \emptyset $. Of course, they all have a gcd for the order in $\mathbb Z$, in which case I'd like to prove that the greatest common divisor for the order is a (the) greatest common divisor in the purely algebraic sense.

Once done, it almost goes without saying that the gcd is unique. Indeed, since $\forall x,y \in \mathbb N \quad (x|y \implies x \leq y)$, $\quad \mathcal D(a,b)$ is bounded by $\min(a,b)$ and has a unique maximal element. If $a$ and $b$ do have a gcd, then, once again by $x|y \implies x \leq y$ the gcd can only be that maximal element.

Therefore, proving that $a$ and $b$ have a gcd is equivalent to proving that the greatest element of $\mathcal D(a,b)$ (the "usual" greatest common divisor of $a$ and $b$) is a gcd of $a$ and $b$, that is, that every element of $\mathcal D(a,b)$ divides its greatest element.

I'm stuck here.

Answer 1

$\mathbf Z$ is a P.I.D., hence the ideal $\langle a,b\rangle$ has a generator $d$, and every generator is unique modulo units. The units of $\mathbf Z$ are $\pm 1$, so we can choose the positive generator.

By definition, $a, b\in\langle d\rangle$, so $d\mid a, b$.

On the other hand, we can write $d=ua+vb$ for some $u,v\in\mathbf Z$ since $d\in\langle a,b\rangle$. Let $e$ be a common divisor of $a$ and $b$: we can write $a=a'e$, $b=b'e$, so $$d=ua'e+vb'e=(ua'+vb()e\in\langle e\rangle ,$$ which means $e$ is a divisor of $d$.

Note

This proof is valid for any P.I.D., even if it has no Euclid's algorithm.

Answer 2

Euclid's algorithm for computing the GCD can be turned directly into a proof that the any two naturals $a$ and $b$ have a unique GCD, by long induction on $a+b$:

If $a=b$, then their common value is obviously their GCD.

Otherwise, suppose without loss of generality that $a>b$. Then the common divisors of $a-b$ and $b$ are easily seen to be the same as the common divisors of $a$ and $b$. But the induction hypothesis tells us that $a-b$ and $b$ have a unique GCD.