裴蜀（péi shǔ）Bézout /beɪzu/ 又称贝祖定理 内容：

更一般地说：

The integers of the form $ax+by$ are exactly the multiples of $\gcd(a,b)$.

如果 $ax+by=m$ 有解，那么 $m$ 一定是 $\gcd(a,b)$ 的若干倍。 这可用于判断这种类型的方程（丢番图方程）是否有解。

若关于整数 $x$ 和 $y$ 的方程 $ax+by=1$ 有解，即这里 $m=1$ ，$1$ 是$\gcd(a,b)$ 的倍数，那么显然有 $\gcd(a,b)=1$ 。即 $a$ 和 $b$ 互质。

又有：关于整数 $x$ 和 $y$ 的二元函数 $f(x,y)=ax+by$ 的最小正整数取值是 $\gcd(a,b)$，即：

推广到 $n$ 元函数：关于整数 $x_i\ (i\in[1,n])$ 的 $n$ 元函数 $f(x_1,x_2,\dots,x_n)=\sum^n_{i=1}a_ix_i$ 的最小正整数取值是 $\gcd(a_1,a_2,\dots,a_n)$。

证明

[[裴蜀定理的证明]]

链接

• 百度百科
• Wikipedia

相关题目

P4549 【模板】裴蜀定理 - 洛谷 求出序列 $A$ 中所有元素的最大公约数（正值）即为答案 参考代码：

#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
//---//
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

typedef unsigned int u;
typedef long long ll;
typedef unsigned long long llu;

#define rep(i, a, b) for (ll i = a; i < b; i++)
#define REP(i, a, b) for (ll i = a; i <= b; i++)
#define per(i, b, a) for (ll i = b; i >= a; i--)

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

signed main() {
  ll n, g, k;
  scanf("%lld%lld", &n, &g);
  while (n--) {
    scanf("%lld", &k);
    g = gcd(k, g);
  }
  printf("%lld", abs(g));
}

//https://www.luogu.com.cn/record/60899570

证明

[[裴蜀定理]] 参考：Bézout’s identity - Wikipedia 给定任意非零整数 $a$ 和 $b$ ，令：

当 $x$ 取 $\pm1$ ，且 $y$ 取 $0$ 时，$ax+by=\pm a$，必有一值属于 $S$ ，令 $d=as+bt=S_{\min}$，我们要证明 $d=\gcd(a,b)$ ，即是要证明：

对 $a$ 和 $d$ 实施带余除法，表示为：

我们要证明 $r=0$ ，尝试表示一下 $r$

可以看到，$r$ 也被表示为了 $ax+by$ 的形式，根据 $r$ 原本的定义，我们可以知道：

根据定义，$d=S_{\min}$ ，但 $0\leq r<d$ ，故 $r$ 不能属于 $S$ ，否则就与 $d$ 是最小值矛盾了，因此，我们只能断定 $r=0$，也就是 $d\mid a$ 。 我们能用同样的方法证明 $d\mid b$ 。 要证明最后一个子命题，我们令 $a=cu$ ，$b=cv$ ，这就有：

这就意味着：$d\mid c$，因此 $c\geq d$。 综上，$S_{\min}=d=\gcd(a,b)$。 这样，函数 $ax+by$ 的所有取值均为 $as+bt$ 加减几个 $a$ 或 $b$ 所得到的。 因为 $d\mid a$ 且 $d\mid b$ ，无论如何，结果总会是 $d=\gcd(a,b)$ 的整数倍，所以 $ax+by=m$ 有整数解当且仅当 $\gcd(a,b)\mid m$ 。