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

内容

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

证明

对于前半句，因为 $\gcd (a,b) | a$ 且 $\gcd (a,b) | b$，所以 $\gcd (a,b) | ax$ 且 $\gcd (a,b) | by$，故 $\gcd (a,b)∣(ax+by)$。

对于后半句，考虑由所有 $ax+by(x,y \in \mathbb{Z})$ 构成的整数集合 $S$，因为 $a,b$ 不全为零，所以 $S$ 中显然包含正整数。所以 $S$ 的正整数部分（以下记为 $S'$）是正整数集的一个子集。由良序原理可得 $S'$ 中必定存在最小值。将最小值记作

$$d = ax_0 + by_0, \quad x_0, y_0 \in \mathbb{Z}.$$

对 $a$ 做带余除法：$a=qd+r$，其中 $0\le r < d$，将这个形式转换一下，得

$$r=a-qd=a-q(ax_0+by_0)=a-qax_0-qby_0=a(1-qx_0)+bqy_0$$

因为 $q,x_0,y_0\in \mathbb{Z}$，所以 $r\in S$。

我们发现，如果 $r>0$，那么 $r\in S'$，此时因为 $r<d$，所以 $r$ 才是 $S'$ 中最小的正整数，这与我们原先的假设相悖。所以 $r\le 0$。

又因为 $r\ge 0$，所以 $r=0$，即 $d | a$。 同理可以证明 $d|b$，即 $d$ 是 $a$ 和 $b$ 的公因数。

此时因为 $d\in S$，所以 $\gcd (a,b)|d$，即 $d=k\times \gcd (a,b)(k\ge 1)$，如果 $k>1$，那么我们找到了一个比 $\gcd (a,b)$ 更大的 $a$ 和 $b$ 的公因数，与 $\gcd (a,b)$ 的定义矛盾。所以 $k=1$，即 $d= \gcd (a,b)$。所以存在 $x$ 和 $y$ 使得 $ax+by= \gcd (a,b)$。后半句得证。

注：此定理可以扩展成多个整数的情况。

模版题

应用

那么它有什么用呢？

1. 不定方程

裴蜀定理可以用于判定不定方程是否有解。

即对于关于 $x,y$ 的方程 $ax+by=c$ 有解等价于 $\gcd (a,b)|c$。

例：二元一次不定方程

线性同余方程

G16 裴蜀定理

#include<iostream>
#include<cmath>
using namespace std;

int n,a,s;

int gcd(int a, int b){
  return b==0?a:gcd(b,a%b);
}
int main(){
  cin >> n;
  for(int i=1;i<=n;i++){
    cin >> a;
    s = gcd(s,abs(a));
  }
  cout << s;
  return 0;
}