# 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)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)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)$. |