Show that if $D$ is a PID, then any two elements of $D$ have a g.c.d. which can be written in the form $xa+yb$, for some $x,y\in D$.

Question

Let $D$ be a domain, and let $a,b\in D$. An element $d\in D$ is called a greatest common divisor (g.c.d) of $a$ and $b$ if:
i) $d|a$ and $d|b$; and
ii) if $c$ is any element such that $c|a$ and $c|b$, then $c|d$.

Show that if $D$ is a PID, then any two elements of $D$ have a g.c.d. which can be written in the form $xa+yb$, for some $x,y\in D$. (Suggestion: consider the ideal $\{xa+yb|x,y\in D\}$.)

Answer 1

Let $a, b\in D$ and consider $I=\{xa+yb|x,y\in D\}$. Then $I$ is an ideal in $D$ because it is an additive subgroup of $D$ and $DI\subseteq I$. Since $D$ is a PID, (i.e., every ideal is a principal ideal domain) so $I=(d)$ form some $d\in I$. (Note that $d\in I$ so $d=x_0a+y_0b$ for some $x_0, y_0\in D$.) Then the claim is that $d$ is the gcd of $a$ and $b$. For this we show that $d$ has the required two properties that you have stated:

(1) We have $a\in I=(d)$ because $a$ can be written as $a=1.a+0.b$. So $a=rd$ for some $r\in D$. This means that $d|a$. Similarly $d|b$.

(2) Now if $c|a$ and $c|b$ then $a=r_1c$ and $b=r_2c$ for some $r_1, r_2\in D$. If $d=x_0a+y_0b$ then $d=x_0r_1c+y_0r_2c=(x_0r_1+y_0r_2)c$ which implies that $c|d$.