The Greatest Common Divisor of Elements in a Commutative Ring

# The Greatest Common Divisor of Elements in a Commutative Ring

Recall from the Divisors and Associates of Commutative Rings page that if $(R, +, \cdot)$ is a commutative ring then for $a, b \in R$ we said that $b$ is a divisor of $a$ written $b | a$ if there exists an element $q \in R$ such that $a = bq$.

We also said that $a$ is an associate of $b$ written $a \sim b$ if there exists a unit $u \in R$ such that $a = bu$.

We can now define the greatest common divisor of elements in a commutative ring like we did for the set of integers and for polynomials over a field $F$.

Definition: Let $(R, +, \cdot)$ be a commutative ring and let $a_1, a_2, ..., a_n \in R$. Then a Greatest Common Divisor of $a_1, a_2, ..., a_n$ is an element $d \in R$ that satisfies the following properties:1) $d | a_1, a_2, ..., a_n$.2) If $c | a_1, a_2, ..., a_n$ then $c | d$. |

It is important to note that the greatest common divisor of elements $a_1, a_2, ..., a_n$ need not be unique. This is examined further in the following proposition.

Proposition 1: Let $(R, +, \cdot)$ be a commutative ring and let $a_1, a_2, ..., a_n \in R$. If $d$ is a greatest common divisor of $a_1, a_2, ..., a_n$ and if there exists a $d' \in R$ such that $d \sim d'$ then $d'$ is also a greatest common divisor of $a_1, a_2, ..., a_n$. |

**Proof:**If $d \sim d'$ then there exists a unit $u \in R$ such that $d = ud'$ and $d' = du^{-1}$. So $d | d'$ and $d' | d$. Since $d | a_1, a_2, ..., a_n$ we must have that $d' | a_1, a_2, ..., a_n$. So (1) and (2) are satisfied by the definition above. Hence $d'$ is also a greatest common divisor of $a_1, a_2, ..., a_n$. $\blacksquare$

Theorem 2: Let $(R, +, \cdot)$ be a commutative ring and let $a, b, d \in R$ with $d \neq 0$. If $aR + bR = dR$ then $d$ is a greatest common divisor of $a$ and $b$. |

**Proof:**Since $aR + bR = dR$ we have that $(a + b)R = dR$. Then $a \in (aR + bR)$ so $a \in dR$. Furthermore, $b \in (aR + bR)$ so $b \in dR$. So there exists elements $q_1, q_2 \in R$ such that $a = q_1d$ and $b = q_2d$. So $d | a$ and $d | b$ and (1) in the definition above is satisfied.

- Let $c \in R$ be such that $c | a$ and $c | b$. Then $c | (a + b)$. So $dR = (aR + bR) \subseteq cR$.

- Thus $c | d$ and (2) is the definition above is satisfied. So $d$ is a greatest common divisor of $a$ and $b$. $\blacksquare$

Theorem 3: Let $(R, +, \cdot)$ be a principal ideal domain and let $a, b \in R$ with $a \neq 0$ and $b \neq 0$. Then there exists a greatest common divisor of $a$ and $b$ of the form $d = as + bt$ where $s, t \in R$. |

**Proof:**Let $a, b \in R$ with $a \neq 0$ and $b \neq 0$. Consider the ideals $aR$ and $bR$. Then $aR + bR$ is an ideal. Since $R$ is a principal ideal domain we have that $aR + bR = dR$ for some generator element $d \in R$. By the previous theorem we have that $d$ is a greatest common divisor of $a$ and $b$ so there exists elements $s, t \in R$ such that $d = as + bt$. $\blacksquare$