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

Ordering of integers 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.

Minimum and maximum of integers 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}\]

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\).

Calculation rules for gcd and lcm 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\).

\(\mathrm{lcm}(488,296)={}\) \(18056\)

The prime factorisations of the given numbers are: \[488 = 2^3\times 61 \qquad\text{and}\qquad 296 =2^3\times 37\] For the gcd we take the product of the highest powers of the prime numbers that divide both \(488\) and \(296\). For the lcm we take the product of the highest powers of the prime numbers that divide \(488\) or \(296\) (or both). So:

\[\begin{aligned}

\mathrm{gcd}(488,296) &= 2^3\\&=8\\ \\

\mathrm{lcm}(488,296) &= 2^3\times 37\times 61\\&=18056

\end{aligned}\]

Euclid's algorithm 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)\).