证明裴蜀定理（一位刚学数论两天的初三生发明的证法）

大家好，欢迎来到IT知识分享网。

裴蜀定理：对于整数 $a,b$，若 $a,b$ 不全为0，则存在 $x,y$ 使得 $a\times x+b\times y=\text{gcd(a,b)}$。

不失一般性，设 $0\le a\le b$，对于 $a<0$ 则将 $-a,b$ 的解的 $x$ 取反，$b<0$ 同理。

如：$a=3,b=2$ 的一种解为 $x=3,y=-4$，那么 $a=-3,b=2$ 的一组解就是 $-3,-4$。

$s{t}_1：a=0,\text{gcd}(a,b)=b$

此时取 $x=0,y=1$ 则 $a\times x+b\times y=b=\text{gcd}(a,b)$，条件成立。

$s{t}_2：a\ne 0,\text{gcd}(a,b)=0$

设 $v=b\%a$ 即 $v=b-t\times v$ 其中 $t=\lfloor a/b\rfloor$。

证明：存在 $k(1\le k\le a)$ 使得 $(k\times v)\%a=1$

先证明：对于 $k(1\le k\le a)$ 不存在 $t$ 使得 $(t\times v)\%a=(k\times v)\%a$，其中 $(t<k)$。

问题可转化为：证明 不存在 $t$ 使得 $t\%a=k\%a$,$(t<k)$。

运用 我今天刚学的 反证法：

设 $t\%a=b$

若 $b\ne 0$，则 $k=b+m\times a，(m\ne 1)$。

所以 $m<1$ 或 $m>a$，矛盾。

若 $b=0$，则 $t=a$。

因为 $k>t$，所以 $k>a$，矛盾。

所以，对于 $k(1\le k\le a)$ 不存在 $t$ 使得 $(t\times v)\%a=(k\times v)\%a$，其中 $(t<k)$。

因为：对于 $k(1\le k\le a)$ 不存在 $t$ 使得 $(t\times v)\%a=(k\times v)\%a,(t<k)$。

所以，$(k\times v)\%a$ 包含了 $0\sim a-1$ 的所有数。

所以，$(k\times v)\%a$ 包含 $1$。

所以 ，存在 $k(1\le k\le a)$ 使得 $(k\times v)\%a=1$

所以，存在 $k(1\le k\le a)$ 使得 $k\times b-\lfloor (k\times b)/a\rfloor =1$

所以，当 $x=-\lfloor (k\times b)/a\rfloor ,y=k$ 时,$a\times x+b\times y=\text{gcd(a,b)}=1$。

$s{t}_3：a\ne 0,\text{gcd}(a,b)\ne 0$

设 $g=\text{gcd}(a,b)$。

设 $x,y$ 为当 { a = a / g , b = b / g } \{ a=a/g,b=b/g \} {
a=a/g,b=b/g} 时的解，这里 $\text{gcd}(a/g,b/g)=1$，所以可以使用 $s{t}_2$。

因为，$\frac{a}{g}\times x+\frac{b}{g}\times y=g$。

所以，$a\times x+b\times y=g=\text{gcd(a,b)}$。

至此，证毕。

下面是我用我的结论写出来的代码，缺点是时间复杂度是 $O(n)$ 的，这个日后在优化吧。

在代码中我只打开了 $x,y$ 的打印，想看的详细一点的请自行解开封印 。

我的 $a,b$ 是随机的，可以改为自己输入。

#include<bits/stdc++.h> #define ll long long using namespace std; inline ll Rand_1(ll x,ll y){ 
      return (rand()*rand())%(y-x+1)+x; } inline Rand(ll x,ll y){ 
      if(x>0)return Rand_1(x,y); if(y<0)return -Rand_1(-y,-x); ll op=Rand(1,2); if(op==1)return Rand_1(0,y); else return -Rand_1(1,-x); } inline pair<ll,ll>peishu(ll a,ll b){ 
      if(a==0){ 
      if(b<0)return{ 
     0,-1}; if(b>0)return{ 
     0,1}; } if(a<0){ 
      pair<ll,ll>res=peishu(-a,b); res.first*=-1; return res; } if(b<0){ 
      pair<ll,ll>res=peishu(a,-b); res.second*=-1; return res; } if(a==1)return{ 
     -(b-1),1}; if(a==b)return{ 
     1,0}; if(a>b){ 
      pair<ll,ll>res=peishu(b,a); swap(res.first,res.second); return res; } if(b%a==0)return{ 
     1,0}; if(__gcd(a,b)>1){ 
      ll g=__gcd(a,b); pair<ll,ll>res=peishu(a/g,b/g); return res; } ll v=b-(b/a)*a; for(ll k=1;k<=a;k++)if(v*k%a==1)return{ 
     -(b*k/a),k}; } signed main(){ 
      srand(time(0)); ios::sync_with_stdio(false); for(ll q=1;q<=;q++){ 
      // cout<<endl<<"q = "<<q<<endl; cout<<endl; ll k=Rand(1,100); ll a=k*Rand(-1000,1000),b=k*Rand(-1000,1000); // ll a,b;cin>>a>>b; cout<<"a = "<<a<<" b = "<<b<<endl; pair<ll,ll>res=peishu(a,b); ll x=res.first,y=res.second; cout<<"x = "<<x<<" y = "<<y<<endl; // cout<<"a*x = "<<a*x<<" b*y = "<<b*y<<" a*x+b*y = "<<a*x+b*y<<" gcd(a,b) = "<<abs(__gcd(a,b))<<endl; if(a*x+b*y!=abs(__gcd(a,b)))break; } return 0; }