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
$\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.
No comments:
Post a Comment