Greatest Common Divisors (and Their Importance)

Direct Knowlege Contributor David A. Smith
  • By David A. Smith, Founder & CEO, Direct Knowledge
  • David Smith has a B.S. and M.S. in Mathematics and has enjoyed teaching calculus, linear algebra, and number theory at both Tarrant County College and the University of Texas at Arlington. David is the Founder and current CEO of Direct Knowledge.

We discuss several simple lemmas for greatest common divisors including Bezout’s identity. We also work through several elementary facts concerning relatively prime integers.

In addition, the discussion will cover the Euclidean algorithm, which happens to be one of the most efficient methods of computing the greatest common divisor between two integers, and show how it can be used to find the solutions to Bezout’s identity.

The application of Bezout’s identity in finding relatively prime integers is also discussed, while the proof of the Bezout’s identity left as an exercise. Note that the application of this identity extends to the field of greatest common divisors of polynomials and operates in the same way as on integers, as well as in the Principal Ideal Domain, PID.

Introduction to Greatest Common Divisors

Perhaps the most useful result concerning greatest common divisors is Bezout‘s lemma. This fact states that the greatest common divisor of two integers is always a linear combination of these two integers.  In fact we can say more, the greatest common divisor of two given integers is always the least positive linear combination of these two integers. 

Definition.  Let $a$ and $b$ be two integers that are not both zero. Then the greatest common divisor of $a$ and $b$ is the largest integer that divides both $a$ and $b.$  The greatest common divisor of $a$ and $b$ is denoted by $(a,b)$ or sometimes by $\gcd (a,b).$

The integers 4 and 8 have greatest common divisor of 4 and we write $(4,8)=4$ since 4 is the largest integer that divides both 4 and 8. Also $(23,2)=1$ and $(9,51)=3.$

Bezout’s Identity

The Bezout’s Identity has wide application, particularly in number theory, where it is used to establish the proof of certain basic results, among them the existence and operation of inverses modulo prime numbers. Ideally, the identity is a starting tool of Diophantine equation theory that explains modular arithmetic.

In this section, however, we will focus on its use in the calculation of the greatest common divisor between two integers, in addition to providing examples of how to find the solutions to the identity. First though, let us define what a linear combination is and what Bezout’s Identity is all about.

Definition. A linear combination of $a$ and $b$ is an integer of the form $m a+n b$ where $m$ and $n$ are integers.

Note that given 2 and 51 we can form many different linear combinations, here are three examples:

$3(2)+7(51)=363$

$3(2)-7(51)=-351$

$-31(2)+0(51)=-62$

The connection between linear combination and greatest common divisor is Bezout’s identity. 

Definition of Bezout’s Identity

Theorem. (Bezout’s Identity) Let $a$ and $b$ be integers, not both zero. Then $(a,b)=a m +b n$ for some integers $m$ and $n$.

Proof. Assume $a$ and $b$ are integers and w.l.o.g. assume $a\neq 0$. Consider the set  $$ S=\{a x+b y \mid a x+b y>0, \, x \text{ and } y \text{ are integers}\}. $$ Since $S$ is nonempty, because $|a|$ is in $S,$ the Well-Ordering Axiom yields a least positive natural number $d$ such that $d=a m+b n$ for some integers $m$ and $n.$  The idea is to show that $d=(a,b).$ To do this we use the Division Algorithm obtaining $q$ and $r$ such that $a=q d+r$ where $0\leq r<d.$ If $r>0,$ then $r$ is in $S$ because $$ r=a-q d=a-q(a m+b n)=a(1-q m)+b(-q n). $$ But we can not have $r$ is in S because $r<d$ and $d$ is the least in $S.$  Therefore $r=0$ and so $d|a.$ 

Using the same argument with $a$ replaced by $b,$ it is shown that $d|b.$  To show $d=(a,b)$ it remains to show that $d$ is greater than any other common divisor of $a$ and $b;$ and so let $c$ be a common divisor of $a$ and $b.$ Then, $c\mid a m+b n$ that is $c\mid d$ and  so $d\geq c.$ 

Applying Bezout’s Identity

In applying the Bezout’s Identity, we are going to assume that you are familiar with the basic concepts of divisibility of integers, as well as with certain basic facts about prime numbers. Also, we will restrict the definition of linear combination as used in this context to integers only, which may not be the same as it is used in linear algebra.

Effectively though, when applied to the qualitative statement that “two integers are relatively prime,” the Bezout’s identity turns such a statement into an equation that one can easily manipulate. Its importance for the greatest common divisor is in the computation of modular inverses of integers as well as for polynomials.

Corollary. There are an infinite number of ways to write $(a,b)$ as a linear combination of $a$ and $b.$

Proof. Let $d=(a,b).$  There exists integers $m$ and $n$ such that $d=a m+b n$ and thus, for any integer $k,$ we have $$ d=(m+k(b/d))a+(n-k(a/d))b $$ which expresses $(a,b)$ as a linear combination of $a$ and $b.$

Corollary. Let $a$ and $b$ be integers, then the set of linear combinations of $a$ and $b$ is the set of multiples of $(a,b)$.

Proof. If $d=(a,b)$, then $d=a m+b n$ for some integers $m$ and $n.$  Thus, every multiple of $d$ is also a linear combination of $a$ and $b.$ Conversely, let $a x+b y$ be a linear combination of $a$ and $b.$ Then $d|a m+b y$, and so  $a m+b y$ is a multiple of $d.$ 

Relatively Prime Integers

Foremost and noteworthy is that relatively prime integers must not be prime themselves, however, two prime numbers are always relatively prime. Since relatively prime numbers tend to show up frequently in formulas and derivations in number theory, they provide interesting insights into the divisibility of integers.

Two integers are said to be relatively prime if their greatest common divisor is 1. 

Definition. If $(a,b)=1$ then $a$ and $b$ are said to be relatively prime.

Note that $(2,5)=1$ and so 2 and 5 are relatively prime. But $(8,24)=8$ and so 8 and 24 are not relatively prime.

Definition. Integers $a_1, a_2, \ldots, a_n$ are called pairwise relatively prime when $\left(a_i,a_j\right)=1$ for every possible $i$ and $j$ with $i\neq j.$

For example, The integers 3, 5, 7 are pairwise relatively prime because $(3,5)=1,$ $(5,7)=1,$ and $(3,7)=1.$ The integers 4, 19, 27 are pairwise relatively prime because $(4,19)=1,$ $(4,27)=1,$ and $(4,27)=1.$  The integers 10, 14, and 35 are mutually relatively prime because $(10,14,35)=1$ (there is no common divisor for all three) however they are not pairwise relatively prime because $(10,14)=2.$ 

Further Examples on Relatively Prime Integers

Example.  Show that if $k$ is an integer, then the integers $6k-1,$ $6k+1,$ $6k+2,$ $6k+3,$ and $6k+5$ are relatively prime.

Solution. Suppose that $(6k+a,6k+b)=d.$ Then $d|(b-a).$ We have $a,b\in \{-1,1,2,3,5\},$ so if $a<b$ it follows that $b-a\in \{1,2,3,4,6\}.$ Hence $d\in \{1,2,3,4,6\}.$ To show that $d=1$ it is sufficient to show that neither 2 nor 3 divides $(6k+a,6k+b).$ If $p=2$ or $p=3$ and $p|(6k+a,6k+b)$ then $p|a$ and $p|b.$ However, there are no such pairs $a,b$ in the set $\{-1,1,2,3,5\}.$

Example.  Show that every positive integer greater than 6 is the sum of two relatively prime integers greater than 1.

Solution. By the previous example, we know that  $6k-1,$ $6k+1,$ $6k+2,$ $6k+3,$ and $6k+5$ are pairwise relatively prime. To represent $n$ as the sum of two relatively prime integers greater than one, let $n=12k+h,$ $0\leq h<12.$ We now examine the twelve cases, one for each possible value of $h,$ in the following tables: $$ \begin{array}{c|c} h & n \\ \hline 0 & (6k-1)+(6k+1) \\ 1 & (6k-1)+(6k+2) \\  2 & (6k-1)+(6k+3) \\ 3 & (6k+1)+(6k+2) \\ 4 & (6k+2)+(6k+2) \\ 5 & (6k+2)+(6k+3) \end{array} \hspace{2cm} \begin{array}{c|c} h & n \\ \hline 6 & (6k+1)+(6k+5) \\ 7 & (6k+2)+(6k+5) \\  8 & (6k+3)+(6k+5) \\ 9 & (12k+7)+2 \\ 10 & (12k+7)+3 \\  11 & (12k+9)+2 \end{array} $$ So for all possible cases very positive integer greater than 6 is the sum of two relatively prime integers greater than 1.

Linear Combinations

The concept of linear combination is not only integral to the field of number theory, but also finds extensive use in linear algebra, as well as in vector spaces. Ideally, it is a mathematical statement that seeks to express a given set of numbers as multiples of certain constants, which are themselves natural numbers. Add some text here.

Corollary. Let $a$ and $b$ be integers, then $(a,b)=1$ if and only if there exists integers $m$ and $n$ such that $a m+b n=1$.

Proof. If $(a,b)=1$, then there exists integers $m$ and $n$ such that $1=a m +b y.$  Conversely, suppose $(a,b)=d$ and that $1=a x+b y$ for some integers $x$ and $y.$ Then $d|1$ because $d|a$ and so $d=1.$ 

Example.  Show that $3k+2$ and $5k+3$ are relatively prime.

Solution. Since $5(3k+2)-3(5k+3)=1,$ the previous proposition implies that $(3k+2,5k+3)=1.$

Theorem. Let $a$ and $b$ be integers, then $(a,b)$ is the least positive integer that is a linear combination of $a$ and $b$.

Proof.  This follows from the Well Ordering Axiom. The proof is left for the reader as an exercise. 

Example. What is $\left(a^2+b^2,a+b\right),$ where $a$ and $b$ are relatively prime integers that are not both 0?

Solution.  Let $p$ be a prime dividing $\left(a^2+b^2,a+b\right)$. Then  $$ p \, | (a+b)^2 – (a^2+b^2) =2 a b. $$ Now if $p|a,$ then $p|b$ since $p|(a+b).$ But $(a,b)=1,$ so $p\nmid a.$ Similarly, $p\nmid b.$ Therefore, $p|2$ and so $p=1$ or $p=2.$ If $a$ and $b$ have the same parity, then $2|(a+b)$ and $2\left| \left(a^2+b^2 \right)\right.$ and so $\left(a^2+b^2,a+b\right)=2.$  But if $a$ and $b$ have opposite parity, then $a+b$ and $\left(a^2+b^2,a+b\right)=1.$

Corollary. If $(a,b)=d,$ then $(a/d,b/d)=1$.

Proof.  If $(a,b)=d$ then $d=a m+b n$ for some integers $m$ and $n.$ Since $d|a$ and $d|b$ we have $1=(a/d) m+(b/d) n$ and so $(a/d,b/d)=1.$ 

Greatest Common Divisor Characterization

In number theory, the greatest common divisor is concept premised on the idea that any set of two integers must have common integers that divides both of them, and hence it is possible to find the largest of such common divisors. This concept has been applied variously and in different fields, among them in the simplification of fractions.

Theorem.  Let $a$ and $b$ be integers, then $(a,b)=d$ if and only if $d|a,$ $d|b,$ and if $c$ is another common divisor then $c|d$.

Proof.  If $(a,b)=d$ then by definition, $d|a$ and $d|b.$ Let $c$ be a common divisor of $a$ and $b$ with $a=c x$ and $b=c y$ for some integers $x$ and $y.$ There exists $m$ and $n$ such that $d=a m+b n;$ and therefore we have  $d=c (x m+y n).$ Whence, $c|d.$

Corollary. If $b|a c$ and $(a,b)=1,$ then $b|c$.

Proof.  If $b| a c$ there exists an integer $k$ such that $a c = b k$. Since $(a,b)=1$ there exists integers $m$ and $n$ such that $a m+b n=1$. Then $$ c=c (1)=c (a m + b n) = (a c) m + b c n = b k m+b n = b ( k m + c n) $$ which shows $b|c$ since $km + c n$ is an integer.

Corollary. If $b|a$, $c|a$, and $(b,c)=1$, then $b c|a$.

Proof.  If $b|a,$ $c|a,$ and $(b,c)=1,$ there exist natural numbers $s$, $t$, $m$ and $n$ with $a= sb$, $a =t c$, and $bm+nc=1$. Then $$ a=a(1)=a(bm+nc)=a b m+a n c = t c b m +s b n c= bc(tm+sn) $$ which shows $bc|a$ since $tm+sn$ is an natural number.

Euclid’s Lemma

Euclid’s algorithm that is often used in the computation of the greatest common divisor of any two numbers also happens to be the oldest proper algorithm known in this field. Yet, while it faces challenges in expressing the result as a linear combination of the input, its simplicity makes it admirable.

Corollary. If $(a,b c)=1$, then $(a,b)=1$ and $(a,c)=1$; and conversely.

Proof.  If $(a,b c)=1$, there exists natural numbers $u$ and $v$ such that $a u+ b c v=1$. Since 1 is a linear combination of $a$ and $b$ and is also a linear combination of $a$ and $c$, it follows $(a,b)=1$ and $(a,c)=1$.

Conversely, if $(a,c)=1$ then $(a,b)=1$ there exists natural numbers $s$, $t$, $m$ and $n$ such that $a s+b ct=1$ and $a m+b n=1$. Multiplying, $$ 1=(a s+b ct)(a m+b n)=a (sm+sbn+ctm)+ bc (tn) $$ which shows 1 is a linear combination of $a$ and $bc$ and so $(a,bc)=1$.

Corollary. (Euclid’s Lemma) If $(a,b)=1$ and $c|a$, then $(c,b)=1$.

Proof.  If $(a,b)=1$ and $c|a,$ then there exists natural numbers $m$, $n$, and $k$ such that $am+bn=1$ and $a=ck$. Then $$1=am+bn=c(km)+bn$$ which shows $(b,c)=1$.

Example. What is $\left(a^2+b^2,a+b\right),$ where $a$ and $b$ are relatively prime integers that are not both 0?

Solution. Let $p$ be a prime dividing $\left(a^2+b^2,a+b\right).$ Then  $$ p\left|(a+b)^2-\left(a^2+b^2\right)\right.=2 a b. $$

Now if $p|a,$ then $p|b$ since $p|(a+b).$ But $(a,b)=1,$ so $p\nmid a.$ Similarly, $p\nmid b.$ Therefore, $p|2$ and so $p=1$ or $p=2.$ If $a$ and $b$ have the same parity, then $2|(a+b)$ and $2\left|\left(a^2+b^2\right)\right.$ and so $\left(a^2+b^2,a+b\right)=2.$ But if $a$ and $b$ have opposite parity, then $a+b$ and $\left(a^2+b^2,a+b\right)=1.$

Exercises on Greatest Common Divisors

Exercise.  Find the greatest common divisor of each of the following pairs of integers. 

$(1) \quad 5, 15$

$(2) \quad 0,100$

$(3) \quad -27,-45$

$(4) \quad -90, 100$

$(5) \quad 100, 121$

$(6) \quad 1001, 289$

Exercise. Find the greatest common divisor of each of the following.

$(1) \quad (a,2a)$

$(2) \quad (a,a^2)$

$(3) \quad (a,a+1)$

$(4) \quad (a,a+2)$

Exercise.  Show that $(n,1)=1$ for all integers $n.$

Exercise. Show that $(n+1,n)=1$ for all integers $n.$

Exercise.  Show that $(2n+1,2n-1)=1$ for all integers $n.$

Exercise. Show that if $a$ is an even integer and $b$ is an odd integer, then $(a,b)=\left(\frac{a}{2},b\right).$

Exercise.  Show that if $a, b,$ and $c$ are integers, then $[a,b]|c$ if and only if $a|c$ and $b|c.$

Exercise.  Show that if $a$ and $b$ are positive integers, then $(a,b)=(a+b,[a,b]).$

Exercise.  Show that $8a+3$ and $5a+2$ are relatively prime for all integers $a.$

Exercise. For any integer $a$ show that $(2a+1,9a+4)=1.$

Exercise. For any integer $a$ show that $(5a+2,7a+3)=1.$

Exercise. Show that if $a$ is odd, then $(3a,3a+2)=1.$

Exercise.  Show that if $a$ and $b$ are integers with $(a,b)=1,$ then $(a+b,a-b)=1$ or 2.

Exercise. Show that if $a$ and $b$ are even integers that are not both zero, then $(a,b)=2\left(\frac{a}{2},\frac{b}{2}\right).$

Exercise. Show that if $a, b,$ and $c$ are integers such that $(a,b)=1$ and $c|(a+b),$ then $(c,a)=(c,b)=1.$

Exercise. Show that if $a, b,$ and $c$ are integers with $(a,b)=(a,c)=1,$ then $(a,b c)=1.$

Additional Exercises on Greatest Common Divisors

Exercise. Show that if $a$ and $b$ are relatively prime integers, then $(a+2b,2a+b)=1$ or 3.

Exercise. Show that if $(a,b)=1$ and $a|b c$ then $a|c.$

Exercise. Show that if $r|a$, $r|b$, and $r|c$, then $r|\gcd(a,b,c)$.

Exercise. Which of the following are true and which are false? For those that are false provide a counterexample.

(1) If $a|b$ and $b|c$, then $a|c$.

(2) If $a|c$ and $b|d$, then $a b |c d$.

(3) If $m^2 |n^2$, then $m|n$.

(4) If $m |n$, then $m^2 | n^2$.

(5) If $m$ is a positive integer, then $\gcd(ma , mb)=m \gcd(a,b)$.

(6) If $n |a b$ and $n$ does not divide $a$, then $n|b$.

(7) If $n |a b$ and $\gcd(n,a)=1$, then $n|b$.

(8) If $n$ is a positive integer, then $\gcd(a^n,b^n)=\gcd(a,b)^n$.

(9) If $n$ is an integer, then $\gcd(a,b)=\gcd(a,b+n a)$.

(10) If $n$ is composite and $n|a b$, then $n|a$ or $n|b$.

Exercise. Show that if $k$ is a positive integer, then $3k+2$ and $5k+3$ are relatively prime.

Exercise. Show that if $(a,b)=1$ and $c|a$, then $(c,b)=1$.

Exercise. Show that if $a$, $b$, and $c$ are integers such that $(a,b)=1$ and $c|(a+b)$, then $(c,a)=(c,b)=1$.

Leave a Comment