Greatest common divisor and least common multiple
Let $a,b\in\mathbb{Z}$.
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$.
- $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$.
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.
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.
- $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.
- $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)$.
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.$$