# Greatest common divisor

## Definitions

Symbol: GCD $\gcd\!\left(a, b\right)$ Greatest common divisor
Symbol: LCM $\operatorname{lcm}\!\left(a, b\right)$ Least common multiple
Symbol: XGCD $\operatorname{xgcd}\!\left(a, b\right)$ Extended greatest common divisor

## Tables

Table of $\gcd\!\left(n, k\right)$ for $0 \le n \le 15$ and $0 \le k \le 15$
Table of $\operatorname{lcm}\!\left(n, k\right)$ for $0 \le n \le 15$ and $0 \le k \le 15$
Table of $\operatorname{xgcd}\!\left(n, k\right)$ for $0 \le n \le 10$ and $0 \le k \le 10$

## Divisibility

$\gcd\!\left(a, b\right) = \max\left(\left\{ d : d \in \mathbb{Z}_{\ge 1} \,\mathbin{\operatorname{and}}\, d \mid a \,\mathbin{\operatorname{and}}\, d \mid b \right\}\right)$
$\operatorname{lcm}\!\left(a, b\right) = \min\left(\left\{ m : m \in \mathbb{Z}_{\ge 1} \,\mathbin{\operatorname{and}}\, a \mid m \,\mathbin{\operatorname{and}}\, b \mid m \right\}\right)$
$\left(d \mid a \,\mathbin{\operatorname{and}}\, d \mid b\right) \implies \left(d \mid \gcd\!\left(a, b\right)\right)$
$\left(a \mid m \,\mathbin{\operatorname{and}}\, b \mid m\right) \implies \left(\operatorname{lcm}\!\left(a, b\right) \mid m\right)$
$\left(d \mid a \,\mathbin{\operatorname{or}}\, d \mid b\right) \implies \left(d \mid \operatorname{lcm}\!\left(a, b\right)\right)$
$\gcd\!\left(a, b\right) \mid a$
$\gcd\!\left(a, b\right) \mid b$
$a \mid \operatorname{lcm}\!\left(a, b\right)$
$b \mid \operatorname{lcm}\!\left(a, b\right)$
$\operatorname{lcm}\!\left(a, b\right) \mid a b$
$\gcd\!\left(a, b\right) \mid a b$
$\gcd\!\left(a, b\right) \mid \operatorname{lcm}\!\left(a, b\right)$
$\gcd\!\left(a, b\right) \mid a + b$
$\gcd\!\left(a, b\right) \mid a x + b y$

## Bézout identity

$\gcd\!\left(a, b\right) = d = a u + b v\; \text{ where } \left(d, u, v\right) = \operatorname{xgcd}\!\left(a, b\right)$
$\left\{ a x + b y : x \in \mathbb{Z} \,\mathbin{\operatorname{and}}\, y \in \mathbb{Z} \right\} = \left\{ n d : n \in \mathbb{Z} \right\}\; \text{ where } d = \gcd\!\left(a, b\right)$
$\gcd\!\left(a, b\right) = \min\left(\left\{ a x + b y : x \in \mathbb{Z} \,\mathbin{\operatorname{and}}\, y \in \mathbb{Z} \,\mathbin{\operatorname{and}}\, a x + b y \ge 1 \right\}\right)$
$d = a x + b y\; \text{ where } \left(d, u, v\right) = \operatorname{xgcd}\!\left(a, b\right),\,\left(x, y\right) = \left(u + \frac{k b}{d}, v - \frac{k a}{d}\right)$

## Connection formulas

$\gcd\!\left(a, b\right) \operatorname{lcm}\!\left(a, b\right) = \left|a b\right|$
$\gcd\!\left(a, b\right) = \frac{\left|a b\right|}{\operatorname{lcm}\!\left(a, b\right)}$
$\operatorname{lcm}\!\left(a, b\right) = \frac{\left|a b\right|}{\gcd\!\left(a, b\right)}$
$\gcd\!\left(a, b\right) = d\; \text{ where } \left(d, u, v\right) = \operatorname{xgcd}\!\left(a, b\right)$

## Specific values

$\gcd\!\left(0, 0\right) = 0$
$\operatorname{lcm}\!\left(0, 0\right) = 0$
$\gcd\!\left(1, 1\right) = 1$
$\operatorname{lcm}\!\left(1, 1\right) = 1$
$\gcd\!\left(a, 0\right) = \left|a\right|$
$\operatorname{lcm}\!\left(a, 0\right) = 0$
$\gcd\!\left(a, 1\right) = 1$
$\operatorname{lcm}\!\left(a, 1\right) = \left|a\right|$
$\gcd\!\left(a, a\right) = \left|a\right|$
$\operatorname{lcm}\!\left(a, a\right) = \left|a\right|$
$\gcd\!\left(a, 2\right) = 1 + \frac{1 + {\left(-1\right)}^{a}}{2}$
$\operatorname{lcm}\!\left(a, 2\right) = \left|a\right| \left(1 + \frac{1 - {\left(-1\right)}^{a}}{2}\right)$
$\gcd\!\left(a, a - 1\right) = 1$
$\operatorname{lcm}\!\left(a, a - 1\right) = a \left(a - 1\right)$
$\gcd\!\left(a, a - 2\right) = 1 + \frac{1 + {\left(-1\right)}^{a}}{2}$
$\operatorname{lcm}\!\left(a, a - 2\right) = \frac{\left|a \left(a - 2\right)\right|}{2} \left(1 + \frac{1 - {\left(-1\right)}^{a}}{2}\right)$

### Canonical Bézout coefficients

$\operatorname{xgcd}\!\left(a, 0\right) = \left(\left|a\right|, \operatorname{sgn}\!\left(a\right), 0\right)$
$\operatorname{xgcd}\!\left(0, b\right) = \left(\left|b\right|, 0, \operatorname{sgn}\!\left(b\right)\right)$
$\operatorname{xgcd}\!\left(a, 1\right) = \left(1, 0, 1\right)$
$\operatorname{xgcd}\!\left(1, b\right) = \left(1, \left|\operatorname{sgn}\!\left(\left(b - 1\right) \left(b + 1\right)\right)\right|, \operatorname{sgn}\!\left(b\right) \left(\operatorname{sgn}\!\left(b + 1\right) - \operatorname{sgn}\!\left(b - 1\right)\right)\right)$
$\operatorname{xgcd}\!\left(a, a\right) = \left(\left|a\right|, 0, \operatorname{sgn}\!\left(a\right)\right)$
$\operatorname{xgcd}\!\left(a, -a\right) = \left(\left|a\right|, 0, -\operatorname{sgn}\!\left(a\right)\right)$
$\operatorname{xgcd}\!\left(a, -1\right) = \left(1, 0, -1\right)$
$\operatorname{xgcd}\!\left(-1, b\right) = \left(1, -\left|\operatorname{sgn}\!\left(\left(b - 1\right) \left(b + 1\right)\right)\right|, \operatorname{sgn}\!\left(b\right) \left(\operatorname{sgn}\!\left(b + 1\right) - \operatorname{sgn}\!\left(b - 1\right)\right)\right)$
$\left(\left|a\right| = \left|b\right|\right) \implies \left(\left(u, v\right) = \left(0, \operatorname{sgn}\!\left(b\right)\right)\right)\; \text{ where } \left(d, u, v\right) = \operatorname{xgcd}\!\left(a, b\right)$
$\left(\left|a\right| \ne \left|b\right| \,\mathbin{\operatorname{and}}\, \left|a\right| \ne \left|2 d\right|\right) \implies \left(2 d \left|v\right| \lt \left|a\right|\right)\; \text{ where } \left(d, u, v\right) = \operatorname{xgcd}\!\left(a, b\right)$
$\left(\left|a\right| \ne \left|b\right| \,\mathbin{\operatorname{and}}\, \left|a\right| = \left|2 d\right|\right) \implies \left(v = \operatorname{sgn}\!\left(b\right)\right)\; \text{ where } \left(d, u, v\right) = \operatorname{xgcd}\!\left(a, b\right)$
$\left(\left|a\right| \ne \left|b\right| \,\mathbin{\operatorname{and}}\, \left|b\right| \ne \left|2 d\right|\right) \implies \left(2 d \left|u\right| \lt \left|b\right|\right)\; \text{ where } \left(d, u, v\right) = \operatorname{xgcd}\!\left(a, b\right)$
$\left(\left|a\right| \ne \left|b\right| \,\mathbin{\operatorname{and}}\, \left|b\right| = \left|2 d\right|\right) \implies \left(u = \operatorname{sgn}\!\left(a\right)\right)\; \text{ where } \left(d, u, v\right) = \operatorname{xgcd}\!\left(a, b\right)$

## Functional equations

### Symmetry

$\gcd\!\left(a, b\right) = \gcd\!\left(b, a\right)$
$\operatorname{lcm}\!\left(a, b\right) = \operatorname{lcm}\!\left(b, a\right)$
$\gcd\!\left(a, b\right) = \gcd\!\left(-a, b\right) = \gcd\!\left(a, -b\right) = \gcd\!\left(-a, -b\right)$
$\operatorname{lcm}\!\left(a, b\right) = \operatorname{lcm}\!\left(-a, b\right) = \operatorname{lcm}\!\left(a, -b\right) = \operatorname{lcm}\!\left(-a, -b\right)$

### Addition and multiplication formulas

$\gcd\!\left(a + b, b\right) = \gcd\!\left(a, b\right)$
$\gcd\!\left(a - b, b\right) = \gcd\!\left(a, b\right)$
$\gcd\!\left(a + n b, b\right) = \gcd\!\left(a, b\right)$
$\gcd\!\left(a \bmod b, b\right) = \gcd\!\left(a, b\right)$
$\gcd\!\left(n a, n b\right) = \left|n\right| \gcd\!\left(a, b\right)$
$\operatorname{lcm}\!\left(n a, n b\right) = \left|n\right| \operatorname{lcm}\!\left(a, b\right)$
$\operatorname{lcm}\!\left(a + b, b\right) = \frac{\left|a + b\right| \operatorname{lcm}\!\left(a, b\right)}{\left|a\right|}$
$\operatorname{lcm}\!\left(a - b, b\right) = \frac{\left|a - b\right| \operatorname{lcm}\!\left(a, b\right)}{\left|a\right|}$
$\operatorname{lcm}\!\left(a + n b, b\right) = \frac{\left|a + n b\right| \operatorname{lcm}\!\left(a, b\right)}{\left|a\right|}$
$\gcd\!\left(\frac{a}{d}, \frac{b}{d}\right) = \frac{\gcd\!\left(a, b\right)}{\left|d\right|}$
$\operatorname{lcm}\!\left(\frac{a}{d}, \frac{b}{d}\right) = \frac{\operatorname{lcm}\!\left(a, b\right)}{\left|d\right|}$

### Distributivity

$\gcd\!\left(a, \gcd\!\left(b, c\right)\right) = \gcd\!\left(\gcd\!\left(a, b\right), c\right)$
$\operatorname{lcm}\!\left(a, \operatorname{lcm}\!\left(b, c\right)\right) = \operatorname{lcm}\!\left(\operatorname{lcm}\!\left(a, b\right), c\right)$
$\gcd\!\left(a, \operatorname{lcm}\!\left(b, c\right)\right) = \operatorname{lcm}\!\left(\gcd\!\left(a, b\right), \gcd\!\left(a, c\right)\right)$
$\operatorname{lcm}\!\left(a, \gcd\!\left(b, c\right)\right) = \gcd\!\left(\operatorname{lcm}\!\left(a, b\right), \operatorname{lcm}\!\left(a, c\right)\right)$
$\gcd\!\left(a, \operatorname{lcm}\!\left(a, b\right)\right) = \left|a\right|$
$\operatorname{lcm}\!\left(a, \gcd\!\left(a, b\right)\right) = \left|a\right|$

## Factorization

### Coprime factors

$\gcd\!\left(r s, c\right) = \gcd\!\left(r, c\right) \gcd\!\left(s, c\right)$
$\operatorname{lcm}\!\left(r s, c\right) = \frac{\operatorname{lcm}\!\left(r, c\right) \operatorname{lcm}\!\left(s, c\right)}{\left|c\right|}$

### Coprime arguments

$\gcd\!\left({r}^{m}, {s}^{n}\right) = 1$
$\operatorname{lcm}\!\left(r, s\right) = \left|r s\right|$

### Prime factorization

$\gcd\!\left(p, q\right) = 1$
$\gcd\!\left({p}^{m}, {q}^{n}\right) = 1$
$\gcd\!\left(\prod_{k=1}^{m} {p_{k}}^{{e}_{k}}, \prod_{k=1}^{m} {p_{k}}^{{f}_{k}}\right) = \prod_{k=1}^{m} {p_{k}}^{\min\left({e}_{k}, {f}_{k}\right)}$
$\operatorname{lcm}\!\left(\prod_{k=1}^{m} {p_{k}}^{{e}_{k}}, \prod_{k=1}^{m} {p_{k}}^{{f}_{k}}\right) = \prod_{k=1}^{m} {p_{k}}^{\max\left({e}_{k}, {f}_{k}\right)}$

## Special sequences

$\gcd\!\left({n}^{a} - 1, {n}^{b} - 1\right) = {n}^{\gcd\left(a, b\right)} - 1$
$\gcd\!\left(F_{m}, F_{n}\right) = F_{\gcd\left(m, n\right)}$

## Summation and counting

$\left|\left\{ k : k \in \{1, 2, \ldots n\} \,\mathbin{\operatorname{and}}\, \gcd\!\left(n, k\right) = 1 \right\}\right| = \varphi\!\left(n\right)$
$\lim_{N \to \infty} \frac{1}{{N}^{n}} \left|\left\{ T : T \in {\left(\{1, 2, \ldots N\}\right)}^{n} \,\mathbin{\operatorname{and}}\, \gcd\!\left(T\right) = 1 \right\}\right| = \frac{1}{\zeta\!\left(n\right)}$
$\sum_{k=1}^{n} \gcd\!\left(n, k\right) = \sum_{d \in \{1, 2, \ldots n\},\,d \mid n} d \varphi\!\left(\frac{n}{d}\right)$
$\sum_{k=1}^{n} \operatorname{lcm}\!\left(n, k\right) = \frac{n}{2} \left(1 + \sum_{d \in \{1, 2, \ldots n\},\,d \mid n} d \varphi\!\left(d\right)\right)$

## Bounds and inequalities

$\operatorname{lcm}\!\left(a, b\right) \le \left|a b\right|$
$\gcd\!\left(a, b\right) \le \max\!\left(\left|a\right|, \left|b\right|\right)$
$\gcd\!\left(a, b\right) \le \min\!\left(\left|a\right|, \left|b\right|\right)$
$\left|u\right| \le \frac{\left|b\right|}{d}\; \text{ where } \left(d, u, v\right) = \operatorname{xgcd}\!\left(a, b\right)$
$\left|v\right| \le \frac{\left|a\right|}{d}\; \text{ where } \left(d, u, v\right) = \operatorname{xgcd}\!\left(a, b\right)$

Copyright (C) Fredrik Johansson and contributors. Fungrim is provided under the MIT license. The source code is on GitHub.

2019-06-18 07:49:59.356594 UTC