裴蜀定理

定义

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

其内容是：

设 \(a,b\) 是不全为零的整数，则存在整数 \(x,y\), 使得 \(ax+by=\gcd(a,b)\).

证明

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\) 的情况。