# Definition:Greatest Common Divisor

## Contents

## Definition

### Integral Domain

Let $\struct {D, +, \times}$ be an integral domain whose zero is $0$.

Let $a, b \in D: a \ne 0 \lor b \ne 0$.

Let $d \divides a$ denote that $d$ is a divisor of $a$.

Let $d \in D$ have the following properties:

- $(1): \quad d \divides a \land d \divides b$
- $(2): \quad c \divides a \land c \divides b \implies c \divides d$

Then $d$ is called **a greatest common divisor of $a$ and $b$** (abbreviated **GCD** or **gcd**) and denoted $\gcd \set {a, b}$.

That is, in the integral domain $D$, $d$ is the GCD of $a$ and $b$ if and only if:

- $d$ is a common divisor of $a$ and $b$
- Any other common divisor of $a$ and $b$ also divides $d$.

We see that, trivially:

- $\gcd \set {a, b} = \gcd \set {b, a}$

so the set notation is justified.

### Integers

When the integral domain in question is the integers $\Z$, the GCD is often defined differently, as follows:

The **greatest common divisor of $a$ and $b$** is defined as:

- the largest $d \in \Z_{>0}$ such that $d \divides a$ and $d \divides b$

### Polynomial Ring over Field

Let $F$ be a field.

Let $P, Q, R \in F \left[{X}\right]$ be polynomials.

Then $R$ is **the greatest common divisor** of $P$ and $Q$ if and only if it is a monic greatest common divisor.

This is denoted $\gcd \left({P, Q}\right) = R$.

## Real Numbers

The concept can be extended to the set of real numbers:

Let $a, b \in \R$ be commensurable.

Then there exists a greatest element $d \in \R_{>0}$ such that:

- $d \divides a$
- $d \divides b$

where $d \divides a$ denotes that $d$ is a divisor of $a$.

This is called the **greatest common divisor of $a$ and $b$** and denoted $\gcd \set {a, b}$.

## Also known as

The **greatest common divisor** is often seen abbreviated as **GCD**, **gcd** or **g.c.d.**

Some sources write $\gcd \set {a, b}$ as $\tuple {a, b}$, but this notation can cause confusion with ordered pairs.

The notation $\map \gcd {a, b}$ is frequently seen, but the set notation, although a little more cumbersome, can be argued to be preferable.

The **greatest common divisor** is also known as the **highest common factor**, or **greatest common factor**.

**Highest common factor** when it occurs, is usually abbreviated as **HCF**, **hcf** or **h.c.f.**

It is written $\hcf \set {a, b}$ or $\map \hcf {a, b}$.

The archaic term **greatest common measure** can also be found, mainly in such as Euclid's *The Elements*.

## Also see

- Elements of Euclidean Domain have Greatest Common Divisor where it is shown that any two GCDs of $a$ and $b$ are associates.

- Results about
**greatest common divisors**can be found here.