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