====== - #3 Greatest common divisor  and least common multiple ======

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

<box 100% round blue>
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$.
</box>

{{ :modular:common_divisor.png?300 }}

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

<WRAP task>
Find all common divisors of $18$ and $24$.

++Answer| $6,\ 3,\ 2,\ 1$++
</WRAP>

<box 100% round blue>
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. 
</box>

{{ :modular:gcd.png?600 }}

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

<WRAP task>
Find the greatest common divisor of $36$ and $78$.

++Answer| $\gcd(36,78)=6$++
</WRAP>

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

<WRAP def>
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\}$.
</WRAP>

{{ :modular:gcd_primes.png?650 }}

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

<WRAP task>
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$++
</WRAP>

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

<graphviz nod center>
digraph {
	rankdir=BT;
	node [shape = circle];
        1->2
        1->5
        2->10
        5->10
}
</graphviz>

This is not a coincidence. 

<WRAP def>
If $d\mid a$ and $d\mid b$ then
$d\mid \gcd(a,b).$
</WRAP>

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

<box 100% round blue>
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\}$.
</box>

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

<box 100% round blue>
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  \}$.
</box>

<WRAP def>
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\}$.
</WRAP>

<WRAP task>
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$++
</WRAP>

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

<WRAP nl>
[[modular:04_euclidean_algorithm]]\\
</WRAP>