The gcd and the lcm

Calculating with numbers: Computing with integers

The gcd and the lcm

Integers can be placed on a number line, and this also makes clear that you can order them. Negative numbers are to the left of the positive numbers on the number line, and the number $1$ is to the left of the number $2$ on the number line, as can be seen from the following figure.

When go on the number line from left the right the integer values increase, for example, the number three is greater than the number two and this is denoted by $3>2$ . When we go on the number line from right to left the integer values decrease, for example $-3$ is less than $-2$ and this is denoted by $-3<-2$ . Symbols for greater than or equal to and less than or equal to are $\ge$ and $\le$ , respectively.

The ordering $\le$ has the following three characteristics:

Antisymmetry: for all integers $a$ and $b$ we have: if $a\le b$ and $b\le a$ than $a=b$ .
Transitivity: for all integers $a$ , $b$ and $c$ we have: if $a\le b$ and $b\le c$ than $a\le c$ .
Totality: for all integers $a$ and $b$ we have: $a\le b$ or $b\le a$ (or both).

Ordering of natural numbers The ordering of integers also induces an ordering of the natural numbers by simply limiting the ordering to these numbers.

Using the ordering $\le$ of the set of integers you can define for any two numbers $a$ and $b$ the minimum and maximum: $\begin{aligned} \min(a,b)&= \begin{cases} a\quad\text{if }a\le b\\ b\quad\text{otherwise}\end{cases} \\ \\ \max(a,b)&= \begin{cases} b\quad\text{if }a\le b\\ a\quad\text{otherwise}\end{cases}\end{aligned}$

$\min(3,2)=2\qquad \max(3,2)=3\qquad\min(-3,-2)=-3\qquad \max(-3,-2)=-2$

You can define the minimum or maximum of three or more integers. Let $c$ a third integer. Then you can use the following definitions: $\text{min}(a,b,c)=\text{min}\bigl(\text{min}(a,b), c\bigr)\qquad\text{and}\qquad \text{max}(a,b,c)=\text{max}\bigl(\text{max}(a,b), c\bigr)$

The gcd and lcm Two natural numbers could have common divisors. The greatest common divisor (gcd), as the name implies, is their greatest common divisor.

For example $2$ , $3$ and $6$ are divisors of both $12$ and $18$ . The greatest common divisor of $12$ and $18$ is $6$ . We write this as $\mathrm{gcd}(12,18)=6$ .

The numbers $2$ and $3$ only have $1$ as common divisor and so their gcd is equal to $1$ . We also say that these number relatively prime. In general, we say the following :

Two natural numbers are said to be relatively prime if they have no common factor other than $1$ , i.e. if their gcd is equal to $1$ .

The least common multiple (lcm) of two natural numbers is, as the name implies, the smallest number that is a multiple of both numbers.

For example, $36$ is a multiple of both $12$ and $18$ and there is no smaller number with this property. We write this as $\mathrm{lcm}(12,18)=36$ .

$\begin{array}{lcllcr} \mathrm{gcd}(2,3)&=&1\qquad\qquad &\mathrm{lcm}(2,3)&=&6\\ \mathrm{gcd}(3,5)&=&1\qquad\qquad &\mathrm{lcm}(3,5)&=&15\\ \mathrm{gcd}(12,20)&=&4\qquad\qquad &\mathrm{lcm}(12,20)&=&60 \\ \mathrm{gcd}(0,4)&=&4\qquad\qquad &\mathrm{lcm}(0,4)&=&0 \end{array}$ We explain one example: the numbers $12$ and $20$ .

The divisors of $12$ are $1$ , $2$ , $3$ , $4$ , $6$ , and $12$ .
The divisors of $20$ are $1$ , $2$ , $4$ , $5$ , $10$ , and $20$ .
In this case, the common divisors are $2$ and $4$ ; so $\mathrm{gcd}(12,20)=4$ .

Multiples of $12$ are the numbers that are divisible by $12$ so: $12, 24, 36, 48, 60, 72,\ldots$
Multiples of $20$ are the numbers that are divisible by $20$ so: $20, 40, 60, 80, \ldots$
In this case, common multiples are $60,120,180,\ldots$ ; so $\mathrm{lcm}(12,20)=60$ .

Property The main properties will be treated separately because they play a role in the systematic and efficient calculation of the gcd and lcm.

Let $a$ and $b$ be natural numbers. Because $1$ is a divisor of each number we have: $1\le \mathrm{gcd}(a,b)\le \min(a,b)$ By definition of least common multiple and because $a\times b$ is a multiple of both $a$ and $b$ we have: $\max(a,b)\le \mathrm{lcm}(a,b)\le a\times b$

You can also define the greatest common divisor and least common multiple of three or more integers. Let $c$ a third natural number. Then you can use the following definitions: $\mathrm{gcd}(a,b,c)=\mathrm{gcd}\bigl(\mathrm{gcd}(a,b), c\bigr)\qquad\text{and}\qquad \mathrm{lcm}(a,b,c)=\mathrm{lcm}\bigl(\mathrm{lcm}(a,b), c\bigr)$

You can also define the gcd and lcm of integers and this always yields a nonnegative number. The minus symbol actually plays no role in the definition of gcd and lcm because of the following properties for integers $a$ and $b$ : $\begin{array}{ccccccc}\mathrm{gcd}(a,b)&=&\mathrm{gcd}(-a,b)&=&\mathrm{gcd}(a,-b)&=&\mathrm{gcd}(-a,-b)\\ \mathrm{lcm}(a,b)&=&\mathrm{lcm}(-a,b)&=&\mathrm{lcm}(a,-b)&=&\mathrm{lcm}(-a,-b)\end{array}$

Let $a$ and $b$ be natural numbers. Then the following statements for the gcd and lcm are correct.

$\mathrm{gcd}(a,b)= \mathrm{gcd}(b,a)$ .
If $c$ is a common divisor of $a$ and $b$ then $\mathrm{gcd}(a,b)= c\times \mathrm{gcd}\left(\frac{a}{c},\frac{b}{c}\right)$ .
If $a=q\times b+r$ , i.e. the remainder of dividing $a$ by $b$ is $r$ , then $\mathrm{gcd}(a,b)=\mathrm{gcd}(b,r)$ .
$\mathrm{gcd}(a,b)$ is equal to the product of the highest powers of prime numbers that divide both $a$ and $b$ .
$\mathrm{lcm}(a,b)$ is equal to the product of the highest powers of prime numbers that divide $a$ or $b$ (or both).
$\mathrm{gcd}(a,b)\times\mathrm{lcm}(a,b)=a\times b$ .

Our example is $a=2\times 3^2\times 5 \times 7=630$ and $b=2^2\times3^3\times 5=540$ .

When prime factorisations of $a$ and $b$ are known, then the calculation rules 4 and 5 almost immediately yield the gcd and lccm. From $\begin{array}{rcccccccc} 630&=&2&\times&3^2&\times&5&\times&7\\ 540&=&2^2&\times&3^3&\times& 5&&\end{array}$ we read off and conclude: $\begin{array}{rcccccccccr} \mathrm{gcd}(630,540)&=&2&\times&3^2& \times& 5 &&&=&90\\ \mathrm{lcm}(630,180)&=& 2^2&\times& 3^3&\times& 5&\times& 7&=&3780\end{array}$

In this example, rule 2 quickly yields the gcd because you easily see that 10 divides the two numbers. So: $\mathrm{gcd}(630,540)=10\times \mathrm{gcd}(63,54)=10\times 9\times\mathrm{gcd}(7,6)=10\times 9\times1=90$ The lcm can be determined by rule 6: $\mathrm{lcm}(630,540)=\frac{630\times 540}{\mathrm{gcd}(630,540)}=\frac{630\times 540}{90}=7\times 540=3780$

The basic idea behind rule 3 is that the gcd of two numbers is also a divisor of the difference between these two numbers. For example, $\mathrm{gcd}(630,540)$ also divides $630-540=90$ , and then you already almost done because $90$ is a divisor of both $630$ as $540$ .

Rule 3 is the basis of the most efficient and systematic method to calculate the gcd, namely Euclid's algorithm.

Determine the greatest common divisor (gcd) and the least common multiple (lcm) of $333$ and $351$ through prime factorisations of these numbers.

$\mathrm{gcd}(333,351)={}$ $9$
$\mathrm{lcm}(333,351)={}$ $12987$

The prime factorisations of the given numbers are: $333 = 3^2\times 37 \qquad\text{and}\qquad 351 =3^3\times 13$ For the gcd we take the product of the highest powers of the prime numbers that divide both $333$ and $351$ . For the lcm we take the product of the highest powers of the prime numbers that divide $333$ or $351$ (or both). So:
$\begin{aligned} \mathrm{gcd}(333,351) &= 3^2\\&=9\\ \\ \mathrm{lcm}(333,351) &= 3^3\times 13\times 37\\&=12987 \end{aligned}$

New example

Let $a$ and $b$ be two natural numbers with $a\ge b$ (if this condition is not met you just swap the two numbers). The gcd of $a$ and $b$ can now be calculated as follows:

Calculate the remainder of $a$ divided by $b$ .
Replace $a$ by $b$ and $b$ by $r$ .
Repeat the previous steps until $b$ equals $0$ .
The last value of $a$ is equal to $\mathrm{gcd}(a,b)$ .

$\begin{array}{rcllcl}\mathrm{gcd}(999,195) &=& \mathrm{gcd}(195,24) & \blue{\text{because}\;\;\;999}&\blue{=}&\blue{5\times 195+24}\\ &=& \mathrm{gcd}(24,3) & \blue{\text{because}\;\;\;195}&\blue{=}&\blue{8\times 24+3}\\ &=& \mathrm{gcd}(3,0) & \blue{\text{because}\;\;\;\;24}&\blue{=}&\blue{8\times 3+0}\end{array}$ Thus: $\mathrm{gcd}(999,195)=3$ .

For any natural numbers $a$ and $b$ it is possible to find numbers $x$ and $y$ such that $\mathrm{gcd}(a,b)=x\times a + y\times b$ . The numbers $x$ and $y$ are not unique.

An example explains how $x$ and $y$ can be determined. Through Euclid's algorithm we have: $\begin{array}{rcllcl}\mathrm{ggd}(999,195) &=& \mathrm{ggd}(195,24) & \blue{\text{because}\;\;\;999}&\blue{=}&\blue{5\times 195+24}\\ &=& \mathrm{ggd}(24,3) & \blue{\text{because}\;\;\;195}&\blue{=}&\blue{8\times 24+3}\\ &=& \mathrm{ggd}(3,0) & \blue{\text{because}\;\;\;\;24}&\blue{=}&\blue{8\times 3+0}\end{array}$ So: $\begin{array}{rcl}999&=&5\times 195+24\\ 195&=&8\times 24+3 \\ 24&=&8\times 3+0\end{array}$ Now we go from the penultimate row upward row by row, where we substitute that remainder.
From $195=8\times 24+3$ follows that $3= 195-8\times 24$ .
From $999=5\times 195+24$ follows that $24=999-5\times 195$ and substitution in $3= 195-8\times 24$ gives $3= 195-8\times (999-5\times 195)=41\times195-8\times 999$ .
So $3=\mathrm{gcd}(999,195)=-8\times 999+41\times 195$ This is not a unique relationship. For example, we also have: $3=\mathrm{gcd}(999,195)=187\times 999-958\times 195$

Calculate the greatest common divisor (gcd) of $371$ and $175$ via Euclid's algorithm.

Euclid's algorithm goes as follows: $\begin{array}{rcllcl}\mathrm{gcd}(371,175) &=& \mathrm{gcd}(175,21) & \blue{\text{because}\;\;\;371}&\blue{=}&\blue{2\times 175+21}\\ &=& \mathrm{gcd}(21,7) & \blue{\text{because}\;\;\;175}& \blue{=}& \blue{8\times 21+7}\\ &=& \mathrm{gcd}(7,0) & \blue{\text{because}\;\;\;21}&\blue{=}&\blue{3\times 7+0}\\ &=& 7&&&\end{array}$

New example