浅谈裴蜀定理

MobiusInversion · 2026-08-16 07:39:31 · 算法·理论

疑似全洛谷最详细的裴蜀定理（？）

裴蜀定理，又名 Bézout 定理，由法国数学家艾蒂安・裴蜀提出。

定理

定理 1：\exists x,y\in\mathbb{Z},ax+by=\gcd(a,b)。

定理 2：集合 S=\{ax+by|x,y\in\mathbb{Z}\} 恰好为 \gcd(a,b) 的所有倍数。

:::info[证明（定理 1）]

我们设 g=\gcd(a,b)，集合 T=\{ax+by|x,y\in\mathbb{Z},ax+by>0\}。

很明显 T \ne \varnothing，由于自然数的良序原理，T 中是有最小值的，我们设它为 m，因此存在一个 x_0,y_0\in \mathbb{Z}，使得 ax_0+by_0=m。

对 a 做带余除法，a=mq+r，明显 0\le r< m。则 r=a-mq=a(1-qx_0)+b(-qy_0)，就是说 r\in T \cup\{0\}。由于 m 的最小，并且 0\le r< m，所以 r 必然为 0，所以 a=mq+0=mq，因此 m\mid a，同理 m\mid b，所以 m 为公约数，若有一个数 d 是另外的公约数，即 d\mid a 且 d\mid b，所以 d\mid ax_0,d\mid by_0，合并得 d\mid(ax_0+by_0)，即 d\mid m，所以 m 一定为最大公约数，即 m=g。

定理 1 证毕。

:::

:::info[证明（定理 2）]

我们还是设 g=\gcd(a,b)，集合 T=\{ax+by|x,y\in\mathbb{Z},ax+by>0\}。

我们沿用定理 1 证明中的结论 m=\gcd(a,b)。

任意取一个 s=ax+by\in S，做带余除法，s=mq+r，其中 0\le r<m，根据定理 1 证明中同样的过程可得 m\mid s，所以 S\subseteq\{mk\mid k\in\mathbb{Z}\}。

由于 m=ax_0+by_0，所以 s=mk=akx_0+bky_0\in S，因此 \{mk\mid k\in\mathbb{Z}\}\subseteq S。

综上 S=\{mk\mid k\in\mathbb{Z}\}=\{\gcd(a,b)\times k\mid k\in\mathbb{Z}\}。

定理 2 证毕。

:::

推论

根据这个定理我们可以得出若干个推论。

推论 1：线性方程的可解性

这个东西保证了拓展欧几里得定理整数解的存在。

:::info[证明]

设 g=\gcd(a,b)。

我们先考虑证明若 ax+by=c 有整数解，则 g\mid c。

因为 g=\gcd(a,b)，所以说 g\mid a 且 g\mid b。

所以对于任意整数 x,y，都有 g\mid ax 且 g\mid by，合并得 g\mid (ax+by)。

因为 ax+by=c 所以 g\mid c。

然后我们考虑证明若 g\mid c 则 ax+by=c 有整数解。

因为 g\mid c，所以一定有一个整数 k 使得 c=gk。

根据裴蜀定理的定理 1，可得 \exists x_0,y_0\in\mathbb{Z},ax_0+by_0=\gcd(a,b)=g。

我们把等式两边都乘上 k，得 ax_0k+by_0k=gk=c。

最后令 x=x_0k,y=y_0k 很明显 x 和 y 均为整数，因此若 g\mid c 则 ax+by=c 有整数解。

综上 ax+by=c \iff \gcd(a,b)\mid c。

:::

推论 2：n 元的推广

证明：

类比普通裴蜀定理的证明过程推广即可，具体过程略。

推论 3：互质的一个特性

若 \gcd(a,b)=1，则必有一组整数 x 和 y 满足 ax+by=1。

证明：

根据定理 1，稍加改变即可得结论。

例题

例题壹 P4549 【模板】裴蜀定理

根据裴蜀定理的推论 2 可得答案为 k\gcd(a_1,a_2,\dots,a_n)(k\in\mathbb{Z})，考虑让答案最小，让 k=1 即可，最终答案为 \gcd(a_1,a_2,\dots,a_n)。

:::success[代码]

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+1;
int n,ans;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        int a;
        cin>>a;
        ans=__gcd(ans,abs(a));
    }
    cout<<ans<<endl;
    return 0;
}

:::

例题贰 P2520 [HAOI2011] 向量

我们观察 8 个向量，不难发现有 4 个向量 (a,b),(a,-b),(b,a),(b,-a) 是和其他向量互为相反数的，因此我们只考虑对这 4 个向量进行加减。

我们设我们用了 (a,b) 这个向量 n 次，(a,-b) 这个向量 m 次，(b,a) 这个向量 p 次，(b,-a) 这个向量 q 次，假设我们得到了 (x,y)，即：

我们不难注意到 n+m 和 n-m、p+q 和 p-q 奇偶性相同，并且很明显只要这两组玩意内奇偶性相同，(x,y) 就一定能被凑出来。

为了方便，计 k_1=n+m,k_2=p+q,k_3=p-q,k_4=n-m，原式即：

然后我们大力分讨即可。

最后按照分讨的结果写代码即可。

:::success[代码]

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1e5+10;
int T;
int gcd(int x,int y){return y?gcd(y,x%y):x;}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--){
        int a,b,x,y;
        cin>>a>>b>>x>>y;
        int g=2*gcd(a,b);
        if((x%g==0 && y%g==0)||
           ((x+a)%g==0&&(y+b)%g==0)||
           ((x+b)%g==0&&(y+a)%g==0)||
           ((x+a+b)%g==0&&(y+a+b)%g==0)){
            cout<<"Y\n";
        }else{
            cout<<"N\n";
        }
    }
    return 0;
}

:::

后记

我在写这篇文章的时候也比较匆忙，是在集训和 whk 之间见缝插针写成的，里面未免有一些错误，希望有列文虎克大佬可以指出，也希望这里的内容可以帮到大家！