Def/Greatest common divisor

Definition of Greatest common divisor: Suppose that $R$ is a Euclidean domain (such as $\ZZ$ or $\RR[X]$, for example). Suppose that $a$ and $b$ are elements of $R$. A greatest common divisor of $a$ and $b$, sometimes called $GCD(a,b)$ (especially when $R = \ZZ$), is an element $g \in R$ satisfying the following two conditions:

• $g$ divides $a$ and $g$ divides $b$, i.e., $g$ is a common divisor of $a$ and $b$.
• If $d$ divides $a$ and $d$ divides $b$, then $d$ divides $g$.

When $R = \ZZ$, it is most common to let $GCD(a,b)$ denote the unique positive greatest common divisor of $a$ and $b$.

More generally, suppose that $a_1, \ldots, a_k$ is a (nonempty) finite sequence of elements of $R$. A greatest common divisor of the sequence, sometimes called $GCD(a_1, \ldots, a_k)$ is an element $g \in R$ satisfying the following two conditions:

• If $i \in \NN$, and $1 \leq i \leq k$, then $g$ divides $a_i$.
• If $d$ divides every element $a_i$, for $1 \leq i \leq k$, then $d$ divides $g$.

The existence of a greatest common divisor $GCD(a,b)$ (when $a \neq 0$ or $b \neq 0$) can be proven using the Euclidean algorithm. The existence of a greatest common divisor $GCD(a_1, \ldots, a_k)$ (when one element of the sequence is nonzero) can be proven since greatest common divisors can be computed pairwise.