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

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

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

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

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

modular/02_gcd.txt ยท Last modified: 2014/02/01 00:00 by marje