The Greatest Common Division Between Integers

Definition: If $a, b \in \mathbb{Z}$ then the Greatest Common Divisor of $a$ and $b$ denoted $\gcd (a, b)$ or $(a, b)$ is an integer $d \in \mathbb{Z}$ such that: 1. $d \mid a$ and $d \mid b$. 2. If $c \in \mathbb{Z}$, $c \mid a$, and $c \mid b$ then $c \leq d$.

Note that the number $1 \in \mathbb{Z}$ has the property such that $1 \mid a$ and $1 \mid b$ for all $a, b \in \mathbb{Z}$ and so we see that the greatest common divisor of any two integers is always at least $1$. As a result, we only need to compare positive divisors of $a$ and $b$. Furthermore, if $a \mid b$ then it's not hard to verify that $\gcd (a, b) = \mid a \mid$.

Let's look at an example of finding the greatest common divisor among two integers $a, b \in \mathbb{Z}$.

Consider the integers $a = 14$ and $b = 35$. The factors of $a$ are $1, 2, 7, 14$ and the factors of $b$ are $1, 5, 7, 35$. Both $a$ and $b$ share the factor $7$ and it is the largest factor they share, and so:

(1)

\begin{align} \quad \gcd (14, 35) = 7 \end{align}

As we elaborated on just moments ago, the greatest common divisor of any two integers is always at least $1$. We give a special name to pairs of integers for which their greatest common divisor is $1$ which we define below.

Definition: If $a, b \in \mathbb{Z}$ and $\gcd (a, b) = 1$ then $a$ and $b$ are said to be Relatively Prime to each other.

For example, consider the numbers $a = 5$ and $b = 8$. The greatest common divisor between these numbers is:

(2)

\begin{align} \quad \gcd (5, 8) = 1 \end{align}

Therefore $5$ and $8$ are relatively prime to each other.

Theorem 1: If $a, b, c \in \mathbb{Z}$, $c \mid a$, and $c \mid b$ then $c \mid \gcd (a, b)$.