Fungrim home page

Greatest common divisor

Table of contents: Definitions - Tables - Divisibility - Bézout identity - Connection formulas - Specific values - Functional equations - Factorization - Special sequences - Summation and counting - Bounds and inequalities

Definitions

287e28
Symbol: GCD gcd ⁣(a,b)\gcd\!\left(a, b\right) Greatest common divisor
c03ed9
Symbol: LCM lcm ⁣(a,b)\operatorname{lcm}\!\left(a, b\right) Least common multiple
5daceb
Symbol: XGCD xgcd ⁣(a,b)\operatorname{xgcd}\!\left(a, b\right) Extended greatest common divisor

Tables

8b2743
Table of gcd ⁣(n,k)\gcd\!\left(n, k\right) for 0n150 \le n \le 15 and 0k150 \le k \le 15
a0d13f
Table of lcm ⁣(n,k)\operatorname{lcm}\!\left(n, k\right) for 0n150 \le n \le 15 and 0k150 \le k \le 15
99dc4a
Table of xgcd ⁣(n,k)\operatorname{xgcd}\!\left(n, k\right) for 0n100 \le n \le 10 and 0k100 \le k \le 10

Divisibility

6880d0
gcd ⁣(a,b)=max({d:dZ1anddaanddb})\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)
805c7a
lcm ⁣(a,b)=min({m:mZ1andamandbm})\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)
7638c5
(daanddb)    (dgcd ⁣(a,b))\left(d \mid a \,\mathbin{\operatorname{and}}\, d \mid b\right) \implies \left(d \mid \gcd\!\left(a, b\right)\right)
3605cc
(amandbm)    (lcm ⁣(a,b)m)\left(a \mid m \,\mathbin{\operatorname{and}}\, b \mid m\right) \implies \left(\operatorname{lcm}\!\left(a, b\right) \mid m\right)
5d03d2
(daordb)    (dlcm ⁣(a,b))\left(d \mid a \,\mathbin{\operatorname{or}}\, d \mid b\right) \implies \left(d \mid \operatorname{lcm}\!\left(a, b\right)\right)
a9c81e
gcd ⁣(a,b)a\gcd\!\left(a, b\right) \mid a
272bc8
gcd ⁣(a,b)b\gcd\!\left(a, b\right) \mid b
67978f
alcm ⁣(a,b)a \mid \operatorname{lcm}\!\left(a, b\right)
4f1441
blcm ⁣(a,b)b \mid \operatorname{lcm}\!\left(a, b\right)
65cfe5
lcm ⁣(a,b)ab\operatorname{lcm}\!\left(a, b\right) \mid a b
b60924
gcd ⁣(a,b)ab\gcd\!\left(a, b\right) \mid a b
1277f6
gcd ⁣(a,b)lcm ⁣(a,b)\gcd\!\left(a, b\right) \mid \operatorname{lcm}\!\left(a, b\right)
e3392b
gcd ⁣(a,b)a+b\gcd\!\left(a, b\right) \mid a + b
663d9c
gcd ⁣(a,b)ax+by\gcd\!\left(a, b\right) \mid a x + b y

Bézout identity

be5fcd
gcd ⁣(a,b)=d=au+bv   where (d,u,v)=xgcd ⁣(a,b)\gcd\!\left(a, b\right) = d = a u + b v\; \text{ where } \left(d, u, v\right) = \operatorname{xgcd}\!\left(a, b\right)
965ac0
{ax+by:xZandyZ}={nd:nZ}   where d=gcd ⁣(a,b)\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)
e922c4
gcd ⁣(a,b)=min({ax+by:xZandyZandax+by1})\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)
f20503
d=ax+by   where (d,u,v)=xgcd ⁣(a,b),(x,y)=(u+kbd,vkad)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

4d3127
gcd ⁣(a,b)lcm ⁣(a,b)=ab\gcd\!\left(a, b\right) \operatorname{lcm}\!\left(a, b\right) = \left|a b\right|
6572c5
gcd ⁣(a,b)=ablcm ⁣(a,b)\gcd\!\left(a, b\right) = \frac{\left|a b\right|}{\operatorname{lcm}\!\left(a, b\right)}
927e6e
lcm ⁣(a,b)=abgcd ⁣(a,b)\operatorname{lcm}\!\left(a, b\right) = \frac{\left|a b\right|}{\gcd\!\left(a, b\right)}
126f3e
gcd ⁣(a,b)=d   where (d,u,v)=xgcd ⁣(a,b)\gcd\!\left(a, b\right) = d\; \text{ where } \left(d, u, v\right) = \operatorname{xgcd}\!\left(a, b\right)

Specific values

19ceaa
gcd ⁣(0,0)=0\gcd\!\left(0, 0\right) = 0
af512f
lcm ⁣(0,0)=0\operatorname{lcm}\!\left(0, 0\right) = 0
554b2e
gcd ⁣(1,1)=1\gcd\!\left(1, 1\right) = 1
34378a
lcm ⁣(1,1)=1\operatorname{lcm}\!\left(1, 1\right) = 1
c40be0
gcd ⁣(a,0)=a\gcd\!\left(a, 0\right) = \left|a\right|
0a7aff
lcm ⁣(a,0)=0\operatorname{lcm}\!\left(a, 0\right) = 0
720766
gcd ⁣(a,1)=1\gcd\!\left(a, 1\right) = 1
8d90e9
lcm ⁣(a,1)=a\operatorname{lcm}\!\left(a, 1\right) = \left|a\right|
0f26cc
gcd ⁣(a,a)=a\gcd\!\left(a, a\right) = \left|a\right|
c6631e
lcm ⁣(a,a)=a\operatorname{lcm}\!\left(a, a\right) = \left|a\right|
5fb5e2
gcd ⁣(a,2)=1+1+(1)a2\gcd\!\left(a, 2\right) = 1 + \frac{1 + {\left(-1\right)}^{a}}{2}
157c33
lcm ⁣(a,2)=a(1+1(1)a2)\operatorname{lcm}\!\left(a, 2\right) = \left|a\right| \left(1 + \frac{1 - {\left(-1\right)}^{a}}{2}\right)
c70178
gcd ⁣(a,a1)=1\gcd\!\left(a, a - 1\right) = 1
e19e40
lcm ⁣(a,a1)=a(a1)\operatorname{lcm}\!\left(a, a - 1\right) = a \left(a - 1\right)
80f20f
gcd ⁣(a,a2)=1+1+(1)a2\gcd\!\left(a, a - 2\right) = 1 + \frac{1 + {\left(-1\right)}^{a}}{2}
7a1799
lcm ⁣(a,a2)=a(a2)2(1+1(1)a2)\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

e352ca
xgcd ⁣(a,0)=(a,sgn ⁣(a),0)\operatorname{xgcd}\!\left(a, 0\right) = \left(\left|a\right|, \operatorname{sgn}\!\left(a\right), 0\right)
6fd925
xgcd ⁣(0,b)=(b,0,sgn ⁣(b))\operatorname{xgcd}\!\left(0, b\right) = \left(\left|b\right|, 0, \operatorname{sgn}\!\left(b\right)\right)
13ed5e
xgcd ⁣(a,1)=(1,0,1)\operatorname{xgcd}\!\left(a, 1\right) = \left(1, 0, 1\right)
bf877e
xgcd ⁣(1,b)=(1,sgn ⁣((b1)(b+1)),sgn ⁣(b)(sgn ⁣(b+1)sgn ⁣(b1)))\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)
945be9
xgcd ⁣(a,a)=(a,0,sgn ⁣(a))\operatorname{xgcd}\!\left(a, a\right) = \left(\left|a\right|, 0, \operatorname{sgn}\!\left(a\right)\right)
0bb73e
xgcd ⁣(a,a)=(a,0,sgn ⁣(a))\operatorname{xgcd}\!\left(a, -a\right) = \left(\left|a\right|, 0, -\operatorname{sgn}\!\left(a\right)\right)
b66d1e
xgcd ⁣(a,1)=(1,0,1)\operatorname{xgcd}\!\left(a, -1\right) = \left(1, 0, -1\right)
1b47db
xgcd ⁣(1,b)=(1,sgn ⁣((b1)(b+1)),sgn ⁣(b)(sgn ⁣(b+1)sgn ⁣(b1)))\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)
a5ef5f
(a=b)    ((u,v)=(0,sgn ⁣(b)))   where (d,u,v)=xgcd ⁣(a,b)\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)
633265
(abanda2d)    (2dv<a)   where (d,u,v)=xgcd ⁣(a,b)\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)
4e5aad
(abanda=2d)    (v=sgn ⁣(b))   where (d,u,v)=xgcd ⁣(a,b)\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)
da7d00
(abandb2d)    (2du<b)   where (d,u,v)=xgcd ⁣(a,b)\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)
569278
(abandb=2d)    (u=sgn ⁣(a))   where (d,u,v)=xgcd ⁣(a,b)\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

258fc7
gcd ⁣(a,b)=gcd ⁣(b,a)\gcd\!\left(a, b\right) = \gcd\!\left(b, a\right)
14b96c
lcm ⁣(a,b)=lcm ⁣(b,a)\operatorname{lcm}\!\left(a, b\right) = \operatorname{lcm}\!\left(b, a\right)
f1817f
gcd ⁣(a,b)=gcd ⁣(a,b)=gcd ⁣(a,b)=gcd ⁣(a,b)\gcd\!\left(a, b\right) = \gcd\!\left(-a, b\right) = \gcd\!\left(a, -b\right) = \gcd\!\left(-a, -b\right)
dc0823
lcm ⁣(a,b)=lcm ⁣(a,b)=lcm ⁣(a,b)=lcm ⁣(a,b)\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

e65763
gcd ⁣(a+b,b)=gcd ⁣(a,b)\gcd\!\left(a + b, b\right) = \gcd\!\left(a, b\right)
b36dba
gcd ⁣(ab,b)=gcd ⁣(a,b)\gcd\!\left(a - b, b\right) = \gcd\!\left(a, b\right)
07ac4a
gcd ⁣(a+nb,b)=gcd ⁣(a,b)\gcd\!\left(a + n b, b\right) = \gcd\!\left(a, b\right)
959a25
gcd ⁣(amodb,b)=gcd ⁣(a,b)\gcd\!\left(a \bmod b, b\right) = \gcd\!\left(a, b\right)
d4852c
gcd ⁣(na,nb)=ngcd ⁣(a,b)\gcd\!\left(n a, n b\right) = \left|n\right| \gcd\!\left(a, b\right)
9500d3
lcm ⁣(na,nb)=nlcm ⁣(a,b)\operatorname{lcm}\!\left(n a, n b\right) = \left|n\right| \operatorname{lcm}\!\left(a, b\right)
5781de
lcm ⁣(a+b,b)=a+blcm ⁣(a,b)a\operatorname{lcm}\!\left(a + b, b\right) = \frac{\left|a + b\right| \operatorname{lcm}\!\left(a, b\right)}{\left|a\right|}
e74d86
lcm ⁣(ab,b)=ablcm ⁣(a,b)a\operatorname{lcm}\!\left(a - b, b\right) = \frac{\left|a - b\right| \operatorname{lcm}\!\left(a, b\right)}{\left|a\right|}
1bbdaf
lcm ⁣(a+nb,b)=a+nblcm ⁣(a,b)a\operatorname{lcm}\!\left(a + n b, b\right) = \frac{\left|a + n b\right| \operatorname{lcm}\!\left(a, b\right)}{\left|a\right|}
646745
gcd ⁣(ad,bd)=gcd ⁣(a,b)d\gcd\!\left(\frac{a}{d}, \frac{b}{d}\right) = \frac{\gcd\!\left(a, b\right)}{\left|d\right|}
cb9f61
lcm ⁣(ad,bd)=lcm ⁣(a,b)d\operatorname{lcm}\!\left(\frac{a}{d}, \frac{b}{d}\right) = \frac{\operatorname{lcm}\!\left(a, b\right)}{\left|d\right|}

Distributivity

4366b2
gcd ⁣(a,gcd ⁣(b,c))=gcd ⁣(gcd ⁣(a,b),c)\gcd\!\left(a, \gcd\!\left(b, c\right)\right) = \gcd\!\left(\gcd\!\left(a, b\right), c\right)
1cde02
lcm ⁣(a,lcm ⁣(b,c))=lcm ⁣(lcm ⁣(a,b),c)\operatorname{lcm}\!\left(a, \operatorname{lcm}\!\left(b, c\right)\right) = \operatorname{lcm}\!\left(\operatorname{lcm}\!\left(a, b\right), c\right)
8dc1c9
gcd ⁣(a,lcm ⁣(b,c))=lcm ⁣(gcd ⁣(a,b),gcd ⁣(a,c))\gcd\!\left(a, \operatorname{lcm}\!\left(b, c\right)\right) = \operatorname{lcm}\!\left(\gcd\!\left(a, b\right), \gcd\!\left(a, c\right)\right)
c4a892
lcm ⁣(a,gcd ⁣(b,c))=gcd ⁣(lcm ⁣(a,b),lcm ⁣(a,c))\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)
1d1653
gcd ⁣(a,lcm ⁣(a,b))=a\gcd\!\left(a, \operatorname{lcm}\!\left(a, b\right)\right) = \left|a\right|
7009cc
lcm ⁣(a,gcd ⁣(a,b))=a\operatorname{lcm}\!\left(a, \gcd\!\left(a, b\right)\right) = \left|a\right|

Factorization

Coprime factors

8621f6
gcd ⁣(rs,c)=gcd ⁣(r,c)gcd ⁣(s,c)\gcd\!\left(r s, c\right) = \gcd\!\left(r, c\right) \gcd\!\left(s, c\right)
fbe121
lcm ⁣(rs,c)=lcm ⁣(r,c)lcm ⁣(s,c)c\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

5aad5c
gcd ⁣(rm,sn)=1\gcd\!\left({r}^{m}, {s}^{n}\right) = 1
250a45
lcm ⁣(r,s)=rs\operatorname{lcm}\!\left(r, s\right) = \left|r s\right|

Prime factorization

062423
gcd ⁣(p,q)=1\gcd\!\left(p, q\right) = 1
499cfc
gcd ⁣(pm,qn)=1\gcd\!\left({p}^{m}, {q}^{n}\right) = 1
25986e
gcd ⁣(k=1mpkek,k=1mpkfk)=k=1mpkmin(ek,fk)\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)}
6cefd7
lcm ⁣(k=1mpkek,k=1mpkfk)=k=1mpkmax(ek,fk)\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

fdae67
gcd ⁣(na1,nb1)=ngcd(a,b)1\gcd\!\left({n}^{a} - 1, {n}^{b} - 1\right) = {n}^{\gcd\left(a, b\right)} - 1
da45c0
gcd ⁣(Fm,Fn)=Fgcd(m,n)\gcd\!\left(F_{m}, F_{n}\right) = F_{\gcd\left(m, n\right)}

Summation and counting

7b27cd
#{k:k{1,2,n}andgcd ⁣(n,k)=1}=φ ⁣(n)\# \left\{ k : k \in \{1, 2, \ldots n\} \,\mathbin{\operatorname{and}}\, \gcd\!\left(n, k\right) = 1 \right\} = \varphi\!\left(n\right)
4099d2
limN1Nn#{T:T({1,2,N})nandgcd ⁣(T)=1}=1ζ ⁣(n)\lim_{N \to \infty} \frac{1}{{N}^{n}} \# \left\{ T : T \in {\left(\{1, 2, \ldots N\}\right)}^{n} \,\mathbin{\operatorname{and}}\, \gcd\!\left(T\right) = 1 \right\} = \frac{1}{\zeta\!\left(n\right)}
aaef97
k=1ngcd ⁣(n,k)=dndφ ⁣(nd)\sum_{k=1}^{n} \gcd\!\left(n, k\right) = \sum_{d \mid n} d \varphi\!\left(\frac{n}{d}\right)
c24323
k=1nlcm ⁣(n,k)=n2(1+dndφ ⁣(d))\sum_{k=1}^{n} \operatorname{lcm}\!\left(n, k\right) = \frac{n}{2} \left(1 + \sum_{d \mid n} d \varphi\!\left(d\right)\right)

Bounds and inequalities

125606
lcm ⁣(a,b)ab\operatorname{lcm}\!\left(a, b\right) \le \left|a b\right|
56acd6
gcd ⁣(a,b)max ⁣(a,b)\gcd\!\left(a, b\right) \le \max\!\left(\left|a\right|, \left|b\right|\right)
f91d1c
gcd ⁣(a,b)min ⁣(a,b)\gcd\!\left(a, b\right) \le \min\!\left(\left|a\right|, \left|b\right|\right)
b43dac
ubd   where (d,u,v)=xgcd ⁣(a,b)\left|u\right| \le \frac{\left|b\right|}{d}\; \text{ where } \left(d, u, v\right) = \operatorname{xgcd}\!\left(a, b\right)
10ed14
vad   where (d,u,v)=xgcd ⁣(a,b)\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-07-15 23:42:41.550119 UTC