# Let $D$ be a PID and $a$ and $b$ be nonzero elements of $D$. Prove that there exist elements $s$ and $t$ in $D$ such that $\gcd(a, b) = as + bt$.

Let $$D$$ be a principal ideal domain and $$a$$ and $$b$$ be nonzero elements of $$D$$. Prove that there exist elements $$s$$ and $$t$$ in $$D$$ such that $$\gcd(a, b) = as + bt$$.

I would like to use some properties of $$\text{PID}$$s to prove this but I am only thinking of well-ordering principle that is used to prove for integers, which I don't think I can use since $$D$$ is not necessarily the set of integers, right? Any ideas?

• Consider the ideal generated by $a$ and $b$. – Lord Shark the Unknown Oct 30 '18 at 3:21

Consider the ideal

$$\langle a, b \rangle \subset D; \tag 1$$

since $$D$$ is a principal ideal domain, we have $$d \in D$$ such that

$$\langle a, b \rangle = \langle d \rangle; \tag 2$$

this in itself is sufficient for

$$\exists s, t \in D, \; d = as + bt; \tag 3$$

now (2) implies

$$d \mid a, \; d \mid b, \tag 4$$

and if

$$c \mid a, \; c \mid b, \tag 5$$

then

$$\exists x, y \in D \mid a = cx, \; b = cy; \tag 6$$

inserting these equations into (3) yields

$$d = as + bt = cxs + cyt = c(xs + yt), \tag 7$$

whence

$$c \mid d; \tag 8$$

$$d$$ is thus a divisor of $$a$$ and $$b$$ which is itself divided by any $$c$$ such that (5) binds; but this is the definition of a greatest common divisor; therefore,

$$d = \gcd(a, b). \tag 9$$

• What a beautiful reply! Truly easy to understand, thank you! – numericalorange Oct 30 '18 at 3:49
• @numericalorange: thanks. It is really the "standard proof". And thanks for the "acceptance"! Cheers! – Robert Lewis Oct 30 '18 at 3:50

Hint $$\,\ c\mid\gcd(a,b)\!\iff\! c\mid a,b\!\iff\! (c)\supseteq (a),(b)\!\iff\! (c)\supseteq \overbrace{(a,b)=(d)}^{\Large as+bt\ =\ d\ }\!\iff\! c\mid d$$

• Damn you are so concise, !!! – Robert Lewis Oct 30 '18 at 3:53