裴枢定理 扩展欧几里得算法 中国余数定理

---

裴蜀定理

裴蜀定理的定义

若 $a,b$ 是正整数，且 $gcd(a,b)=d$，那么：

• 对于任意的整数 $x,y，ax+by$ 都一定是 $d$ 的倍数。
• $gcd(a,b)$ 是 $ax+by$ 能凑出来的最小正整数。
• 一定存在整数 $x,y$ (不唯一)，使 $ax+by=d$ 成立。

什么是贝祖数？

例如：$2x+y=3$，那么符合这个等式的 $\{\begin{array}{l}x=1\\ y=1\end{array}$ 就是一组贝祖数。

裴蜀定理求解二元不定方程

设二元一次不定方程

$$ax+by=c$$

(其中 $a,b,c$ 是整数，且 $a,b$ 都不是 $0$)

假定有一组整数解$\{\begin{array}{l}x=x_0\\ y=y_0\end{array}$，则原式的一切整数的通解可以表示成：

$$\{\begin{array}{l}x=x_0-\frac{b}{(a,b)}t\\ y=y_0+\frac{a}{(a,b)}t(t\in \mathbb{Z})\end{array}$$

其中 $(a,b)$ 代表 $a$ 和 $b$ 的最大公约数。

证明过程：

设 $x_0,y_0$ 是方程(1)的一个整数解组，即：
$$a{x}_0+b{y}_0=c(1)$$

将 $x_0,y_0$ 代入方程(1)，可得：
$$a(x-x_0)+b(y-y_0)=0$$

因为 $a,b$ 都是非0整数，所以上式等价于：
$$\frac{a}{(a,b)}(x-x_0)+\frac{b}{(a,b)}(y-y_0)=0$$

上式为：
$$-\frac{b}{(a,b)}(y-y_0)=\frac{a}{(a,b)}(x-x_0)$$

因为：
$$(\frac{b}{(a,b)},\frac{a}{(a,b)})=1$$

所以：
$$\frac{a}{(a,b)}|(y-y_0)$$
$$y=y_0+\frac{a}{(a,b)}t(t\in \mathbb{Z})$$

对 $x$ 同理，让 $t$ 取所有整数，可以得到方程(1)的全部整数解：
$$\{\begin{array}{l}x=x_0-(a,b)\end{array}$$

推荐阅读

• 一篇了解裴枢、扩欧、乘法逆元、中国余数定理的文章

• (扩展）欧几里得算法，裴枢定理（贝祖定理）

• 裴枢定理及反演元素的扩展欧几里得算法详解

• 裴枢定理、扩展欧几里得算法及其证明

• 裴枢定理 扩展欧几里得算法 中国余数定理

• 裴枢定理（欧几里得算法的扩展）

• 算法基础》学习笔记 - ⑭ 欧拉函数 \ 快速幂 \ 扩展欧几里得算法 \ 中国余数定理