$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 1.5: The Greatest Common Divisor

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

$$\newcommand{\NN}{\mathbb N}$$
$$\newcommand{\RR}{\mathbb R}$$
$$\newcommand{\QQ}{\mathbb Q}$$
$$\newcommand{\ZZ}{\mathbb Z}$$
$$\newcommand{\Cc}{\mathcal C}$$
$$\newcommand{\Dd}{\mathcal D}$$
$$\newcommand{\Ee}{\mathcal E}$$
$$\newcommand{\Ff}{\mathcal F}$$
$$\newcommand{\Kk}{\mathcal K}$$
$$\newcommand{\Mm}{\mathcal M}$$
$$\newcommand{\Pp}{\mathcal P}$$
$$\newcommand{\ind}{\operatorname{ind}}$$
$$\newcommand{\ord}{\operatorname{ord}}$$

In this section, we define the greatest common divisor ($$\gcd$$) of two integers and discuss its properties. We also prove that the greatest common divisor of two integers is a linear combination of these integers.

Two integers $$a$$ and $$b$$, not both $$0$$, can have only finitely many divisors (see Exercise 1.3.1(5)), and thus can have only finitely many divisors in common. In this section, we are interested in the greatest of these common divisors.

Definition: Greatest Common Divisor

Given $$a,b\in\ZZ$$, not both zero, the greatest common divisor is the largest integer that divides both $$a$$ and $$b$$, and is written $$\gcd(a,b)$$ (or sometimes just $$(a,b)$$).

When it makes some formulæ simpler, we will write $$\gcd(0,0)=0$$.

Example $$\PageIndex{1}$$

The greatest common divisor of $$24$$ and $$18$$ is $$6$$. In other words, $$\gcd(24,18)=6$$.

Definition: Relatively Prime

$$a,b\in\ZZ$$ are said to be relatively prime if $$\gcd(a,b)=1$$.

Example $$\PageIndex{2}$$

The greatest common divisor of $$9$$ and $$16$$ is $$1$$, thus they are relatively prime.

Note that every integer has positive and negative divisors. If $$a$$ is a positive divisor of $$m$$, then $$-a$$ is also a divisor of $$m$$. Therefore by our definition of the greatest common divisor, we can see that $$\gcd(a,b)=\gcd(|a|, |b|)$$.

We can use the $$\gcd$$ of two integers to make relatively prime integers:

Theorem $$\PageIndex{1}$$

If $$a,b\in\ZZ$$ have $$\gcd(a,b)=d$$ then $$\gcd(\dfrac{a}{d}, \dfrac{b}{d})=1$$.

Proof

Fix $$a,b\in\ZZ$$. We will show that $$\dfrac{a}{d}$$ and $$\dfrac{b}{d}$$ have no common positive divisors other than $$1$$. Let $$k\in\NN$$ be a divisor of both $$\dfrac{a}{d}$$ and $$\dfrac{b}{d}$$, so $$\exists m,n\in\NN$$ such that $\dfrac{a}{d}=km \hspace{0.3 cm}\mbox{and} \ \ \dfrac{b}{d}=kn$ Thus we get that $a=kmd \hspace{0.3 cm}\mbox{and} \ \ b=knd.$ Hence $$kd$$ is a common divisor of both $$a$$ and $$b$$. Also, $$kd\geq d$$. However, $$d$$ is the greatest common divisor of $$a$$ and $$b$$. As a result, we get that $$k=1$$.

The next theorem shows that the greatest common divisor of two integers does not change when we add a multiple of one of the two integers to the other.

Theorem $$\PageIndex{2}$$

Let $$a,b,c\in\ZZ$$. Then $$\gcd(a,b)=\gcd(a+cb,b)$$.

Proof

We will show that every divisor of $$a$$ and $$b$$ is also a divisor of $$a+cb$$ and $$b$$ and vise versa. Hence they have exactly the same divisors. So we get that the greatest common divisor of $$a$$ and $$b$$ will also be the greatest common divisor of $$a+cb$$ and $$b$$. Let $$k$$ be a common divisor of $$a$$ and $$b$$. By Theorem 1.3.3, $$k \mid (a+cb)$$ and hence $$k$$ is a divisor of $$a+cb$$. Now assume that $$l$$ is a common divisor of $$a+cb$$ and $$b$$. Also by Theorem 1.3.3 we have, $l\mid ((a+cb)-cb)=a.$ As a result, $$l$$ is a common divisor of $$a$$ and $$b$$ and the result follows.

Example $$\PageIndex{3}$$

Notice that $$\gcd(4,14)=\gcd(4,14-3\cdot 4)=\gcd(4,2)=2$$.

We now present a theorem which proves that the greatest common divisor of two integers can be written as a linear combination of the two integers.

Theorem $$\PageIndex{3}$$

Let $$a,b\in\ZZ$$ not both be zero. Then $$\gcd(a,b)$$ is the smallest natural number which is of the form $$d=ma+nb$$ for some $$m,n\in\ZZ$$.

Proof

Assume without loss of generality that $$a,b\in\NN$$ are positive integers. Consider the set $S=\{d\in\NN\mid d=ma+nb\text{ for some }m,n\in\ZZ\}\ .$ $$S$$ is non-empty since $$a=1\cdot a+0\cdot b$$ and $$b=0\cdot a+1\cdot b$$ are both in $$S$$. Let $$d\in\NN$$ be the least element of $$S$$, whose existence is guaranteed by the well-ordering principle. Notice $$d=ma+nb$$ for some $$m,n\in\ZZ$$, since $$d\in S$$. We still must prove that $$d$$ divides both $$a$$ and $$b$$ and that it is the greatest such common divisor.

By the division algorithm, $$\exists q,r\in\ZZ$$ such that $a=qd+r, \ \ \ 0\leq r<d.$ Thus we have $r=a-qd=a-q(ma+nb)=(1-qm)a-qnb.$ We then have that $$r$$ is a linear combination of $$a$$ and $$b$$. Since $$0\leq r<d$$ and $$d$$ is the least positive integer which is a linear combination of $$a$$ and $$b$$, we must have $$r=0$$ and so $$a=qd$$. Hence $$d\mid a$$.

The same sort of argument will show that $$d\mid b$$.

Now notice that if there is a divisor $$c$$ that divides both $$a$$ and $$b$$. Then $$c$$ divides any linear combination of $$a$$ and $$b$$ by Theorem 1.3.3. Hence $$c\mid d$$. This proves that any common divisor of $$a$$ and $$b$$ divides $$d$$. Hence $$c\leq d$$, and $$d$$ is the greatest common divisor.

There is a simple application of this which will be very useful in the future:

Corollary $$\PageIndex{1}$$

If $$a,b\in\ZZ$$ are relatively prime, then $$\exists m,n\in\ZZ$$ such that $$ma+nb=1$$

For some $$n\in\NN$$, let $$a_1,a_2,\dots,a_n\in\ZZ$$ not be all $$0$$. The greatest common divisor of these integers is the largest integer that divides all of them, and is denoted $$\gcd(a_1,\dots,a_n)$$.

Definition: Mutually Relatively Prime

For some $$n\in\NN$$, $$a_1,a_2,\dots,a_n\in\ZZ$$ are said to be mutually relatively prime if $$\gcd(a_1,a_2,\dots,a_n)=1$$.

Example $$\PageIndex{4}$$

The integers $$3, 6, 7$$ are mutually relatively prime since $$(3,6,7)=1$$ although $$(3,6)=3$$.

Definition: Pairwise Relatively Prime

For some $$n\in\NN$$, $$a_1,a_2,\dots,a_n\in\ZZ$$ are called pairwise relatively prime if $$\forall i,j\in\NN$$ such that $$i\le n$$, $$j\le n$$, and $$i\neq j$$, we have $$\gcd(a_i,a_j)=1$$.

Example $$\PageIndex{5}$$

The integers $$3,14,25$$ are pairwise relatively prime. Notice also that these integers are mutually relatively prime.

Proposition $$\PageIndex{1}$$

For $$n\in\NN$$ and $$a_1,\dots,a_n\in\ZZ$$, if $$a_1,a_2,\dots,a_n$$ are pairwise relatively prime then they are mutually relatively prime.

Exercise $$\PageIndex{1}$$

1. Find the greatest common divisor of $$15$$ and $$35$$
2. Find the greatest common divisor of $$100$$ and $$104$$.
3. Find the greatest common divisor of $$-30$$ and $$95$$.
4. Let $$m\in\NN$$. Find the greatest common divisor of $$m$$ and $$m+1$$.
5. Let $$m\in\NN$$, find the greatest common divisor of $$m$$ and $$m+2$$.
6. Show that if $$m,n\in\ZZ$$ have $$\gcd(m,n)=1$$, then $$\gcd(m+n,m-n)=1$$ or $$2$$.
7. Show that if $$m\in\NN$$, then $$3m+2$$ and $$5m+3$$ are relatively prime.
8. Show that if $$a,b\in\ZZ$$ are relatively prime, then $$\gcd(a+2b,2a+b)=1$$ or $$3$$.
9. Show that if $$a_1,a_2,\dots,a_n\in\ZZ$$ are not all $$0$$ and $$c\in\NN$$, then $$\gcd(ca_1,ca_2,\dots,ca_n)=c\cdot\gcd(a_1,a_2,\dots,a_n).$$