Bezout(裴蜀)定理

Bezout 定理：对于任意整数 a，b，存在一对整数 x，y，满足 ax + by = gcd(a, b).

证明：在欧几里得算法的最后一步，即 b = 0 时，显然有一对整数 x = 1, y = 0 ，使得 $a 1 + 0 0 = gcd(a, 0)$ 。若 b > 0, 则 gcd(a, b) = gcd(b, a mod b)。假设存在一对整数 x，y，满足 $b x + (a mod b) y = gcd(b, a mod b)$ ，因为 $bx + (a mod b)y = bx + (a - b\lfloor{a / b}\rfloor)y = ay - b(x - \lfloor{a / b}\rfloor y)$ ，所以令 $x^{‘} = x$ ，$y^{‘} = x - \lfloor{a / b}\rfloor y$ ，就得到了 $ax^{‘} + by^{‘} = gcd(a, b)$ 。

证毕。

Bezout定理是按照欧几里得算法的思路证明的，且上述证明同时给出了整数 x 和 y 的计算方法，即扩展欧几里得算法。