贝祖定理（Bézout’s identity）是其他数论重要结论的基石。当 a, b 皆非零时，以下不定式的整数解 x, y 必存在：
$$ ax + by = gcd(a,b) $$上述问题等价于，当 \(a, b\) 互质时，即 \(gcd(a, b) = 1\)， 整数解 \(x, y\) 必存在：
$$ ax + by = 1 $$因为原式可表示为
$$ a = gcd(a,b) * a' $$$$ b = gcd(a,b) * b' $$此时 \(a', b'\) 互质，原式两边除以gcd，便得到等价形态：
$$ a'x + b'y = 1 $$换句话说，为什么在两数互质时，总能找到一组系数，让他们互相抵消，最终剩下1呢？
因为 a 总能表达为 b 的某种线性组合，设 a 大 b 小：
$$ a = wb + r\quad(1 ≤ r ≤ b-1) $$等价于说，a 模 b 等于 r。
而 a 乘上 \([0,b-1]\) 中的任一个数，余数依然在 \([0,b-1]\)里，且不可能有碰撞。
因为如果 \(ab'\) 和 \(ab''\) 模 b 同余，即：
$$ ab' ≡ ab''\quad(mod\,b)\quad(0 ≤ b' < b'' ≤ b-1) $$则：
$$ b\mid a(b''-b') $$因 a, b 互质，只能：
$$ b\mid(b''-b') $$而这是不可能的，因为有前提：
$$ 0 < b'' - b' < b $$显然，\([0,b-1]\) 共 b 个乘数，一对一映射到 \([0,b-1]\) 共 b 个余数里，无冲突，那么必然有一个乘数，得到余数 1。