贝祖定理（Bézout’s identity），当 a, b 皆非零时，以下不定式的整数解 x, y 必存在：
$$ ax + by = gcd(a,b) $$上述问题等价于，当 \(a, b\) 互质时，即 \(gcd(a, b) = 1\)（通常记为 \(d\)）， 整数解 \(x, y\) 必存在：
$$ ax + by = 1 $$因为原式可表示为
$$ \begin{aligned} a = da' \\ b = db' \end{aligned} $$此时 \(a', b'\) 互质，代入原式，两边除以 \(d\)，便得等价形态：
$$ a'x + b'y = 1 $$换句话说，为什么两个互质数，你加我减，总能凑出 1 呢？
一个数总是另一个数的线性组合 #
因为 a 总能表达为 b 的某种线性组合；设 a 大 b 小：
$$ a = qb + r\quad(1 ≤ r ≤ b-1) $$即，a 模 b 等于 r。
而 a 乘上 \([1,b-1]\) 中的任一个数，余数依然在 \([1,b-1]\)里，不可能有碰撞。因为如果 \(ab'\) 和 \(ab''\) 模 b 同余：
$$ ab' ≡ ab''\pmod{b}\quad(1 ≤ b' < b'' ≤ b-1) $$则：
$$ b\mid a(b''-b') $$因 a, b 互质，只能：
$$ b\mid(b''-b') $$这是不可能的，因为有以下前提：
$$ 0 < b'' - b' < b $$一个更小的数怎能被一个更大的数整除？
显然，\([1,b-1]\) 个乘数，乘以 a，会一对一映射到 \([1,b-1]\) 个余数里，只会打乱顺序，但无冲突。那么必然有一个乘数，得到余数 1。
乘法逆元 #
这唯一乘数，称为 \(a\) 模 \(b\) 的乘法逆元。如 8 和 3 互质：
$$ \begin{aligned} 8\bmod{3} &= 2 \\ (2 * 2)\bmod{3} ≡ (8*2)\bmod{3} &= 1 \end{aligned} $$即 8 和 2 模 3 同余 1，2 是 8 在模 3 下的逆元。
b 是质数时 #
a 和 b 互质时，即 a 模 b 的余数 r 和 b 互质（否则，他们共享更小的因子），所有 r 组成的集合，是理论最大余数集合 \([1,b-1]\) 的子集，即：
$$ U(b)=\{r\in\{1,\ldots,b-1\}\mid\gcd(r,b)=1\} $$b 是质数 p 时，理论最大余数集合 \([1,p-1]\) 里的所有元素，都与 p 互质，于是 r 不再是子集。根据前面的推论，r 的集合（即 a 的集合，所有 a 的可能性）里的每个元素，都依然存在唯一乘法逆元。
两个例外，分别是 1 和 p - 1。
1 是单位元 #
任何余数 r 乘以 1 模 n 都还是 r，即 1 在模数乘法运算下，没有任何效果，这就是群论里的单位元。
$$ r * 1\bmod{n} = r\quad(1 < r < n) $$也可以说，1（单位元）的逆元是自身。
p - 1 逆元是自身 #
模质数 p 时，有以下规律：
$$ \begin{aligned} 1(p - 1)\bmod{p} &= p - 1 \\ 2(p - 1)\bmod{p} &= p - 2 \\ ... \\ (p - 1)(p - 1)\bmod{p} &= p - (p - 1) = 1 \\ p(p - 1)\bmod{p} &= p - p = 0 \\ \end{aligned} $$类似于，第一圈少走一步，再绕一圈，只会更少一步，以此类推，直到走了 p 圈，才能补回来。
自身即逆元 #
这两个特例，其实就是以下式的解：
$$ \begin{aligned} r^2 \equiv 1 \pmod{p} \\ r^2 - 1\equiv 0 \pmod{p} \\ (r+1)(r-1)\equiv 0 \pmod{p} \end{aligned} $$即 p 能整除左侧：
$$ \begin{aligned} p\mid(r+1)(r-1) \end{aligned} $$因 p 是质数， 它至少要能整除 \(r+1\) 或 \(r-1\) 中任一个，而 r 是模 p 下的余数，只剩两种可能：
$$ \begin{aligned} p\mid(r+1) \implies r+1 = p \\ p\mid(r-1) \implies r-1 = 0 \end{aligned} $$于是：
$$ r=p-1 \quad\text{或}\quad r=1 $$威尔逊定理 #
基于上述结论，对质数 p 的所有余数，除了 1 和 p - 1 以外，其他任何一个余数 r，都必定有集合内的另一个余数 \(r^{-1}\) 作为逆元，两两配对：
$$ rr^{-1} \equiv 1 \pmod p $$把所有余数相乘，即 p - 1 的阶乘，因为两两配对的余数们，都互相取消了，最终只剩下 1 和 p - 1：
$$ \begin{aligned} (p-1)! \bmod{p} &= 1*(p-1) \bmod{p} \\ &= p - 1 \end{aligned} $$标准写法：
$$ (p-1)!\equiv p-1\equiv-1\pmod p. $$这是数论里的基础定理之一，威尔逊定理。
GCD是尺子上的最小单位 #
回过头来看贝祖定理，当 \(gcd(a, b) = d\) 时，a 和 b 无论怎么凑，都只能得到 k 份 d，最小 0 份，即 a 份 b 减 b 份 a，ab - ba = 0。当 d 大于 1 时，如何也不可能通过 a 和 b 的线性组合，凑出 1。
假设要找一个数 \(x\)，同时满足：
\[ x\equiv r_a\pmod a \]和：
\[ x\equiv r_b\pmod b. \]第一式表示：
\[ x=r_a+ma \]第二式表示：
\[ x=r_b+nb \]其中 \(m,n\) 是整数。二者要描述同一个 \(x\)，就必须有：
\[ r_a+ma=r_b+nb. \]移项：
\[ r_b-r_a=ma-nb. \]右边正是 \(a,b\) 的整数线性组合，即 \(r_b - r_a\) 必须是 \(gcd(a,b) = d\) 的倍数：
$$ d\mid(r_b-r_a) $$比如 6 和 11 能凑出 1，显而易见，\(2 * 6 - 11 = 1\)。但 6 和 10 凑不出，因为那要求：
$$ r_b-r_a = 1 $$它不是 d = 2 的倍数，甚至小于 d。所以 6 和 10 只能凑出 2 的倍数，那是他们这个离散世界里的最小单位。下次有人问，如何用 4 升和 6 升的量杯，量出 3 升水，你可以直接回答不可能。
自然数的合成公式 #
任意自然数，必定由一个或多个质数 \(p^k\) 相乘而得。因为其要么是质数，要么是合数，合数便能继续拆分，直到只剩质数因子为止。
一个数只有一种合成方案。为什么？假如有两种合成法，先约掉共享的质因子，得到：
$$ p_1p_2\,...\,p_m = q_1q_2\,...\,q_n $$相除：
$$ 1 = \frac{p_1p_2\,...\,p_m}{q_1q_2\,...\,q_n} $$因为分子分母皆为质数，不存在任何其他大于 1 的因子，分子不可能整除分母，除非相等，那便刚好证明了唯一性。更明显的，不可能有两个不同的数用同一份合成公式，因为那显然就是一个数了。
所以任意自然数可以写成：
$$ n = p_1^{k_1}p_2^{k_2}\cdots p_m^{k_m} $$互质数的数量 #
小于自然数 n 的数里，与 n 互质的数，有多少？
当 \(n = p^k\)：
$$ \varphi(p^k) = p^k - p^{k-1} $$因为 \(p^k\) 个数里，含有因子 p 的数有 \(p^{k-1}\) 个（最后一项即是 \(p^k\) 自身）：
$$ p,\,2p,\,3p\,...\,p^{k-1}•p $$当 k = 1 时，就是经典形式，显而易见，质数的互质因子们，就是小于它的所有自然数：
$$ \varphi(p) = p - 1 $$当 n 是两个互质数合成时（多个同理）