Greatest common divisor and least common multiple

Let $a,b\in\mathbb{Z}$ .

An integer

$c$ is common divisor of

$a$ and

$b$ , if

$c \mid a$ and

$c \mid b$ , i.e.,

$c$ divides both

$a$ and

$c$ .

For example, a common divisor of $30$ and $20$ is $10$ , but also $5$ , $2$ and $1$ .

Find all common divisors of $18$ and $24$ .

Answer $6,\ 3,\ 2,\ 1$

An integer

$c$ is greatest common divisor (gcd) of

$a$ and

$b$ , if

$c$ is a common divisor of $a$ and $b$ , and
for all common divisors $d$ of $a$ and $b$ holds $d\leq c$ , i.e., $c$ is the greatest of all common divisors.

We already know that common divisors of $20$ and $30$ are $10,\ 5,\ 2,\ 1$ , thus the greatest common divisor is $10$ . It is usually denoted $\gcd(20,30)=10$ .

Find the greatest common divisor of $36$ and $78$ .

Answer $\gcd(36,78)=6$

If the prime factorisations are known, its is really easy to calculated the greatest common divisor.

Let $n = p_1^{e_1}\cdot\dots\cdot p_k^{e_k}$ and $m = p_1^{e'_1}\cdot\dots\cdot p_l^{e'_l}$ . Then $\gcd(n,m) = p_1^{\displaystyle\min(e_1, e'_1)}\cdot\dots\cdot p_s^{\displaystyle\min(e_s, e'_s)},$ where $s=\max\{k,l\}$ .

For example, since
$50=2^{\color{blue}1} \cdot 3^{\color{blue}0}\cdot 5^{\color{blue}2}$ ,
$210=2^{\color{red}1} \cdot 3^{\color{red}1} \cdot 5^{\color{red}1}\cdot 7^{\color{red}1}$ ,

primes	$2$	$3$	$5$	$7$
powers for $\gcd$	$\min\{\color{blue}1,\color{red}1\}$	$\min\{\color{blue}0,\color{red}1\}$	$\min\{\color{blue}2,\color{red}1\}$	$\min\{\color{blue}0,\color{red}1\}$

We obtain $\gcd(50,210)=2^1\cdot 3^0\cdot 5^1\cdot 7^0=10$ .

Find $\gcd(24, 3675)$ by using the prime factorisation.

Answer $\gcd(24, 3675) = 2^{\min(3,0)} \cdot 3^{\min(1,1)} \cdot 5^{\min(0,2)} \cdot 7^{\min(0, 2)} = 2^0 \cdot 3^1 \cdot 5^0 \cdot 7^0 = 3$

Note that the common divisors of $20$ and $30$ ( $10,\ 5,\ 2,\ 1$ ) form a lattice of divisibility:

This is not a coincidence.

If $d\mid a$ and $d\mid b$ then $d\mid \gcd(a,b).$

We can also find the greatest common divisor for any set of integers.

It is said that

$x = \gcd(a_1, a_2, \dots , a_n )$ if

$x \mid a_i$ for all $i$ ,
$y \mid x$ for any other common divisor $y$ of $\{a_1, a_2, \dots , a_n\}$ .

A symmetric notion to the greatest common divisor is the least common multiple.

The least common multiple of a set of numbers

$\{a_1, a_2, \dots , a_n\}$ is denoted

$\operatorname{lcm}(a_1, a_2, \dots , a_n ).$ It is a number

$x$ such that

$a_i \mid x$ for all $i$ , i.e., $x$ is a common multiple of $\{a_1, a_2,\dots , a_n\}$ ,
$x \mid y$ for any other common multiple $y$ of $\{a_1, a_2, \dots , a_n \}$ .

Let $n = p_1^{e_1}\cdot\dots\cdot p_k^{e_k}$ and $m = p_1^{e'_1}\cdot\dots\cdot p_l^{e'_l}$ . Then $\operatorname{lcm}(n,m) = p_1^{\displaystyle\max(e_1, e'_1)}\cdot\dots\cdot p_s^{\displaystyle\max(e_s, e'_s)},$ where $s=\max\{k,l\}$ .

Find $\operatorname{lcm}(24, 3675)$ .

Answer $\operatorname{lcm}(24, 3675) = 2^{\max(3,0)} \cdot 3^{\max(1,1)} \cdot 5^{\max(0,2)} \cdot 7^{\max(0, 2)} = 2^3 \cdot 3^1 \cdot 5^2 \cdot 7^2 = 8 \cdot 3 \cdot 25 \cdot 49 = 29400$

Clearly $\min(e_i, e'_i) +\max(e_i, e'_i)=e_i+e'_1$ (for example, $\min\{4,10\}+\max\{4,10\}=4+10=14$ ), thus

$\gcd(a,b)\cdot\operatorname{lcm}(a,b)=a\cdot b.$

Euclidean algorithm