裴蜀定理

定义

裴蜀定理，又称贝祖定理（Bézout's lemma）、贝祖等式（Bézout's identity）。是一个关于最大公约数的定理。

其内容是：

设 $a,b$ 是不全为零的整数，对任意整数 $x,y$，满足 $\gcd(a,b)\mid ax+by$，且存在整数 $x,y$, 使得 $ax+by=\gcd(a,b)$.

证明

对于第一点

由于 $\gcd(a,b)\mid a,\gcd(a,b)\mid b$

所以 $\gcd(a,b)\mid ax,\gcd(a,b)\mid by$，其中 $x,y$ 均为整数

因此 $\gcd(a,b)\mid ax+by$

对于第二点

1. 若任何一个等于 $0$, 则 $\gcd(a,b)=a$. 这时定理显然成立。

2. 若 $a,b$ 不等于 $0$.

   由于 $\gcd(a,b)=\gcd(a,-b)$,

   不妨设 $a,b$ 都大于 $0$，$a\geq b,\gcd(a,b)=d$.

   对 $ax+by=d$, 两边同时除以 $d$, 可得 $a_1x+b_1y=1$, 其中 $(a_1,b_1)=1$.

   转证 $a_1x+b_1y=1$.

   我们先回顾一下辗转相除法是怎么做的，由 $\gcd(a, b) \rightarrow \gcd(b,a\mod b) \rightarrow \dots$ 我们把模出来的数据叫做 $r$ 于是，有

   $$\gcd(a_1,b_1)=\gcd(b_1,r_1)=\gcd(r_1,r_2)=\cdots=(r_{n-1},r_n)=1$$

   把辗转相除法中的运算展开，做成带余数的除法，得

   $$\begin{aligned}a_1 &= q_1b_1+r_1 &(0\leq r_1<b_1) \\ b_1 &= q_2r_1+r_2 &(0\leq r_2<r_1) \\ r_1 &= q_3r_2+r_3 &(0\leq r_3<r_2) \\ &\cdots \\ r_{n-3} &= q_{n-1}r_{n-2}+r_{n-1} \\ r_{n-2} &= q_nr_{n-1}+r_n \\ r_{n-1} &= q_{n+1}r_n\end{aligned}$$

   不妨令辗转相除法在除到互质的时候退出则 $r_n=1$ 所以有（$q$ 被换成了 $x$，为了符合最终形式）

   $$r_{n-2}=x_nr_{n-1}+1$$

   即

   $$1=r_{n-2}-x_nr_{n-1}$$

   由倒数第三个式子 $r_{n-1}=r_{n-3}-x_{n-1}r_{n-2}$ 代入上式，得

   $$1=(1+x_nx_{n-1})r_{n-2}-x_nr_{n-3}$$

   然后用同样的办法用它上面的等式逐个地消去 $r_{n-2},\cdots,r_1$,

   可证得 $1=a_1x+b_1y$. 这样等于是一般式中 $d=1$ 的情况。

推广

逆定理

设 $a, b$ 是不全为零的整数，若 $d > 0$ 是 $a, b$ 的公因数，且存在整数 $x, y$, 使得 $ax+by=d$，则 $d = \gcd(a, b)$。

特殊地，设 $a, b$ 是不全为零的整数，若存在整数 $x, y$, 使得 $ax+by=1$，则 $a, b$ 互质。

多个整数

裴蜀定理可以推广到 $n$ 个整数的情形：设 $a_1, a_2, \dots, a_n$ 是不全为零的整数，则存在整数 $x_1, x_2, \dots, x_n$, 使得 $a_1 x_1 + a_2 x_2 + \cdots + a_n x_n=\gcd(a_1, a_2, \dots, a_n)$。其逆定理也成立：设 $a_1, a_2, \dots, a_n$ 是不全为零的整数，$d > 0$ 是 $a_1, a_2, \dots, a_n$ 的公因数，若存在整数 $x_1, x_2, \dots, x_n$, 使得 $a_1 x_1 + a_2 x_2 + \cdots + a_n x_n=d$，则 $d = \gcd(a_1, a_2, \dots, a_n)$。