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?

  • 1
    $\begingroup$ Consider the ideal generated by $a$ and $b$. $\endgroup$ – 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$


$\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$


$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$

  • 1
    $\begingroup$ What a beautiful reply! Truly easy to understand, thank you! $\endgroup$ – numericalorange Oct 30 '18 at 3:49
  • $\begingroup$ @numericalorange: thanks. It is really the "standard proof". And thanks for the "acceptance"! Cheers! $\endgroup$ – 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$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.