$Project Greater Ed Logo$

Greatest Common Divisors and Coprimality

Discrete Mathematics Greatest Common Factors, Least Common Multiples, and Coprimality Greatest Common Divisors and Coprimality

Greatest Common Divisor

Let $n,m\in \mathbb{Z}$. The greatest common divisor (GCD) of $n$ and $m$, denoted $\gcd(n,m)$ is the greatest integer that divides both $n$ and $m$.

For now, the simplest way of finding the GCD of two numbers $n$ and $m$ is by considering all the different factors of $n$ and $m$ and picking the biggest one that divides both $n$ and $m$. We can use a little less brute force more often than not, however.

Ex: If we want to find $\gcd(20,44)$, it helps to list factors of the smaller number from biggest to smallest until you find the biggest factor that also divides $44$. Listing the factors of 20 in decreasing order, we have $20, 10, 5,4, 2, 1$, and the greatest of these that also divides $44$ is $4$. Thus, $\gcd(20,44)=4$.

Occasionally we will come across numbers $n$ and $m$ that have (basically) no factors in common. We give this case a special name.

Coprime (or, Relatively Prime)

Two integers $n$ and $m$ are said to be coprime (or relatively prime) if $\gcd(n,m)=1$.

Since every integer is divisible by $1$, we are guaranteed that the GCD of two numbers is no less than $1$. When two numbers have a GCD of $1$, this means that the two numbers share no other positive factors whatsoever.

NOTE: Despite the name “coprime,” neither $n$ or $m$ needs to be prime. However, if one of $n$ or $m$ is indeed prime, then $n$ and $m$ are coprime.

There are many different theorems pertaining to GCD’s and coprimality, but the following two are of interest to us.

Theorem

Let $n$ and $m$ be integers such that $\gcd(n,m)=d$. Then $n/d$ and $m/d$ are coprime (i.e. $\gcd\left(\frac{n}{d},\frac{m}{d}\right)=1$).

The above is true essentially because when you divide each of $n$ and $m$ by their GCD, you are cancelling out any common factor the two numbers could possible share (as such factors are baked into the GCD).

To illustrate, $\gcd(20,44)=4$ and so $20/4=5$ and $44/4=11$. $5$ and $11$ share no factors, i.e. $\gcd(5,11)$. Dividing out the $4$ from $20$ and $44$ effectively cancelled out all common factors of $20$ and $44$, leaving us with the $5$ and $11$ respectively, which have no factors in common.

Linear Combination (of Integers)

Let $\textbf{n}$ and $\textbf{m}$ be integers. Then, a linear combination of $\textbf{n}$ and $\textbf{m}$ is a sum of the form $a\textbf{n}+b\textbf{m}$, where the integers $a$ and $b$ are called coefficients of $\textbf{n}$ and $\textbf{m}$, respectively.

Theorem

Let $\textbf{n}$ and $\textbf{m}$ be integers. Then there exist integers $a$ and $b$ such that $a\textbf{n}+b\textbf{m}=\gcd(n,m)$.

Stated another way, the GCD of two numbers $n$ and $m$ can be written as a linear combination of $n$ and $m$.

Note that the theorem above does not give us a way of finding the coefficients $a$ and $b$. All it states is that $a$ and $b$ exist. It’s your job to find them.

Interesting Note: There are objects in math that can be proven to exist, but are impossible to explicitly find an example of such.

$\gcd(56,12)=4$

The factors of $12$ are, in decreasing order, 12, 6, 4,3,2, 1. Neither 12 nor 6 divides 56, however 4 does indeed divide 56.

$\gcd(123,66)=3$

The factors of $66$ are, in decreasing order, 66, 33, 22, 11, 6, 3, 2, 1. The greatest of these that divides 123 is 3.

$\gcd(125,51)=1$

The factors of $51$ are, in decreasing order, 51, 17, 3, 1. The only factor in this list that divides 125 is 1.

$\gcd(-144,26)=2$

Don’t let the negative fool you! When we are looking for GCD’s we are looking for the greatest factor that divides two numbers. Positive numbers divide negative numbers! For instance, $-54$ is divisible by both $-9$ as well as $9$! So, in essence, we can basically ignore the negative we see here and proceed as usual.

Note that the factors of $26$ are, in decreasing order, $26,13, 2,1$. Only $2$ divides both $26$ and $-144$.

$\gcd(-552,123)=3$

Note that the factors of $123$ are, in decreasing order, $123, 41, 3, 1$. Only $3$ divides both $123$ and $-552$.

$a=-1$ and $b=1$.

Nothing ever said that the integers have to be positive when building these linear combinations.

Note that $\gcd(2,3)=1$ so we need to find $a$ and $b$ such that $2a+3b=1$. Choosing $b=1$ and $a=-1$ make the equation true.

Note there are infinitely many solutions. Here is one:

$a=-2$ and $b=3$

By one of the theorems above, we are guaranteed the existence of an $a$ and $b$ such that $56a+40b=8$ since the $gcd(56,40)=8$. If you divide both sides by this common divisor, and FOIL correctly, you end up with the equation $7a+5b=1$ which is easier to solve for $a$ and $b$.

My thought process with this is “What can I multiply 7 and 5 by, respectively so that the difference of the two numbers is 1?” This is because having $a$ and $b$ be positive numbers cannot give us $7a+5b=1$. After a bit of guess and check, you will end up with a valid $a$ and $b$ such that this equation balances out.

Note there are infinitely many solutions. Here is one:

$a=-4$ and $b=6$

Notice that $a$ and $b$ here are double the solutions we got for the equation $a\cdot 56+b\cdot 40=8$ (two problems ago). Notice also that the right-hand-side of our equation is double the right-hand side of the equation $a\cdot 56+b\cdot 40=8$.

By one of the theorems above, we are guaranteed the existence of an $a$ and $b$ such that $56a+40b=8$ since the $gcd(56,40)=8$. If you divide both sides of the given equation by this common divisor, and FOIL correctly, you end up with the equation $7a+5b=2$ which is easier to solve for $a$ and $b$.

My thought process with this is “What can I multiply 7 and 5 by, respectively so that the difference of the two numbers is 2?” This is because having $a$ and $b$ be positive numbers cannot give us $7a+5b=2$. After a bit of guess and check, you will end up with a valid $a$ and $b$ such that this equation balances out.

Note there are infinitely many solutions. Here is one:

$a=-6$ and $b=9$

Notice that $a$ and $b$ here are triple the solutions we got for the equation $a\cdot 56+b\cdot 40=8$ (two problems ago). Notice also that the right-hand-side of our equation is triple the right-hand side of the equation $a\cdot 56+b\cdot 40=8$.

My thought process with this is “What can I multiply 7 and 5 by, respectively so that the difference of the two numbers is 2?” This is because having $a$ and $b$ be positive numbers cannot give us $7a+5b=3$. After a bit of guess and check, you will end up with a valid $a$ and $b$ such that this equation balances out.

There are infinitely many other possibilities; here is one.

$a=-2n$ and $b=3n$.

First, to show that the answer works without explaining where it came from, notice that $56a+40b=56\cdot(-2n)+40\cdot(3n)=-112n+120n=8n$, so the equation balances out.

After the last three problems, one observes that when we multiply the right-hand-side of the equation $56a+40b=8$ by a certain number, say 2 or 3, our solution $a$ and $b$ also get multiplied by that amount. This is because if we multiply one side of the equation $56a+40b=8$ by some number, the left-hand-side of the equation must somehow be multiplied by that same amount so the equation balances. The only things that can be altered on the left-hand-side of the equation are the $a$ and $b$.

Observe:

$$\begin{align}56\cdot a+40\cdot b&=8 \\ (56a+40b)n&=8n \\ 56(an)+40(bn)&=8n\end{align}$$

So, by the above, if one can find solution $a$ and $b$ to the equation $56a+40b=8$, we can find a solution to the equation $56a+40b=8n$ simply by multiplying the earlier $a$ and $b$ by $n$.

Previous Lesson

Back to Lesson

Next Topic