前言
在学习本节内容前，最好先学习同余的基本性质以加深理解。
一堆定理
若
a,b,m,n \in \mathbb Z,c \mid a,c \mid b
则
c \mid (ma+nb)
证明：
令 a=ce,b=cf ，
代入 ma+nb 再提公因式即可。
若
a,b,c \in \mathbb Z
则
(a+cb,b)=(a,b)
证明：
由定理1证明二者公因子相同即可。
两个不全为零的整数 a,b 的最大公因子是 a,b 线性组合的最小正整数.
证明：令 d 是 a,b 的线性组合中最小的正整数， d = ma + nb , 其中 m,n 是整数，我们将证明 d \mid a,d \mid b 。
由带余除法，得到 a=dq+r, 0≤r<d 。
由 a=dq+r 和 d=ma+nb ，得到 r=a-dq=a-q(ma+nb)=(1-qm)a-qnb .
这就证明了整数 r 是 a,b 的线性组合。因为 0 ≤ r < d ，而 d 是 a,b 的线性组合中最小的正整数，
于是我们得到 r=0 （如果 r 不是等于 0 ，那意味着 r 才是所有线性组合中最小的正整数，这与 d 是所有线性组合中最小的正整数矛盾），因此 d \mid a ，同理可得， d \mid b .
我们证明了 a,b 的线性组合中最小的正整数 d 是 a,b 的公因子，剩下要证的是它是 a,b 的最大公因子，为此只需证明 a,b 所有的公因子都能整除 d 。
由于 d = ma + nb ，因此如果 c \mid a 且 c \mid b ，那么由定理2有 c \mid d ，因此 d > c 。
得证。
若 a,b 是正整数，
则所有 a,b 的线性组合构成的集合与所有 (a,b) 的倍数构成的集合相同。
证明：由定理1得 a,b 的线性组合都是 (a,b) 倍数。
由定理3得 (a,b) 属于线性组合，其倍数显然也属于线性组合。
得证。
若
a,b,c \in \mathbb Z , m \in \mathbb Z^+ ,d=(c,m)
且有
ac \equiv bc \pmod m
则
a \equiv b \pmod {m/d}
证明：令 ac=km+bc \to (a-b)c=km
两边同除 d 得到：(a-b)(c/d)=k(m/d)
因为 (c/d) 与 (m/d) 互质，
所以有 (m/d) \mid (a-b)
得到结论：a \equiv b \pmod {m/d}
得证。
若
a,b,c \in \mathbb Z , m \in \mathbb Z^+, (c,m)=1
且有
ac \equiv bc \pmod m
则有
a \equiv b \pmod m
若 r_1,r_2,…,r_m 是一个模 m 的完全剩余系，且有正整数 a 满足 (a,m)=1
则对任何整数 b 有： ar_1+b,ar_2+b,…,ar_m+b 也是一个模 m 的完全剩余系。
证明：若有 ar_i+b 与 ar_j+b 同余，则有 ar_i 与 ar_j 同余。
由定理5推论可得：此时有 r_i 与 r_j 同余，矛盾！
故定理成立。
朴素欧几里得定理
若
a,b \in \mathbb Z
则
(a,b)=gcd(b,a \% b)
证明：
令 a=bq+r ,
得 r=a-bq.
由定理2得，
gcd(a,b)=gcd(a-bq,b)=gcd(r,b)=gcd(a\%b,b)=gcd(b,a\%b)
扩展欧几里得算法
对于
ax+by=(a,b)
不妨设 a>b ，
$(2) a>b>0
设 ax_1+by_1=gcd(a,b)，bx_2+(a \mod b) y_2
由朴素欧几里得得：gcd(a,b)=gcd(b,a \mod b)
所以 ax_1 + by_1 = bx_2 + (a \mod b)y_2
即 ax_1 + by_1 = bx_2 + (a - \lfloor \frac{a}{b} \rfloor *b)y_2
化简得：ax_1 + by_1 = bx_2 + ay_2 - \lfloor \frac{a}{b} \rfloor *b *y_2
由贝祖等式得 x_1 = y_2 , y_1 = x_2 - \lfloor \frac{a}{b} \rfloor *y_2
裴蜀定理
若
a,b \in \mathbb Z
则存在
x,y \in \mathbb Z,ax+by=(a,b)
证明：由定理3易证。
- 推论：
整数 a 与 b 互质，
当且仅当存在整数 m,n 使得 ma+nb=1.
证明：若 ma+nb=1 ，由定理3得 (a,b)=1 ,易证。
二元一次不定方程
对于一些方程形如
ax+by=c
如果 x = x_0, y = y_0 是方程的一个特解，
那么所有的解可以表示为：
code：
```cpp
//二元一次不定方程
#include<bits/stdc++.h>
#define int long long
using namespace std;
int G,a,b,c,d,x,y;
void exgcd(int a,int b,int& d,int& x,int& y) {
if(!b) {
d=a,x=1,y=0;
return ;
}
exgcd(b,a%b,d,x,y);
int t=x;
x=y,y=t-a/b*y;
return ;
}
signed main() {
scanf("%lld",&G);
while(G--) {
scanf("%lld%lld%lld",&a,&b,&c);
exgcd(a,b,d,x,y);
if(c%d!=0) {
printf("-1\n");
continue;
}
x*=c/d,y*=c/d;
int mx=b/d,my=a/d,minx=-1,maxx=-1,miny=-1,maxy=-1,t;
if(x>0) {
minx=x-(x/mx)*mx;
int ty=y+(x/mx)*my;
if(!minx) minx+=mx,ty-=my;
if(ty>0) maxx=minx+ty/my*mx-mx*(ty%my==0?1:0),t=ty/my+1-(ty%my==0?1:0);
}
else {
minx=x+(-x)/mx*mx+mx;
int ty=y-((-x)/mx+1)*my;
if(ty>0) maxx=minx+ty/my*mx-mx*(ty%my==0?1:0),t=ty/my+1-(ty%my==0?1:0);
}
if(y>0) {
miny=y-(y/my)*my;
int tx=x+(y/my)*mx;
if(!miny) miny+=my,tx-=mx;
if(tx>0) maxy=miny+tx/mx*my-my*(tx%mx==0?1:0);
}
else {
miny=y+(-y)/my*my+my;
int tx=x-((-y)/my+1)*mx;
if(tx>0) maxy=miny+tx/mx*my-my*(tx%mx==0?1:0);
}
if(maxx!=-1) printf("%lld %lld %lld %lld %lld\n",t,minx,miny,maxx,maxy);
else printf("%lld %lld\n",minx,miny);
}
return 0;
}
```
# 多元一次不定方程
对于方程形如
$$a_1x_1 + a_2x_2 + … + a_nx_n = c$$
由前文所述，我们知道
$$a_1x_1 + a_2x_2 = k(a_1,a_2) \ (k \in \mathbb Z)$$
所以原式就可以换成：
$$(a_1,a_2)x + a_3x_3 + … + a_nx_n = c$$
重复以上操作，就可以得到：
$$(a_1,a_2,…,a_{n-1})x + a_nx_n =c$$
再一层层解回去即可。
code:(仅供参考)
```cpp
//多元一次不定方程
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=5+5;
long long n,c,a[maxn],ans[maxn];
void exgcd(int a,int b,int& d,int& x,int& y) {
if(!b) {
d=a,x=1,y=0;
return ;
}
exgcd(b,a%b,d,x,y);
int temp=x;
x=y,y=temp-a/b*y;
return ;
}
void f(long long t,int now,int& nc) {
if(now<n) f(__gcd(t,a[now]),now+1,nc);
int x,y,d;
exgcd(t,a[now],d,x,y);
if(nc%d!=0) {
printf("-1");
exit(0);
}
x*=nc/d,y*=nc/d;
ans[now]=y;
if(now==2) ans[now-1]=x;
nc=t*x;
return ;
}
signed main() {
scanf("%lld%lld",&n,&c);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
f(a[1],2,c);
for(int i=1;i<=n;i++)
printf("%lld ",ans[i]);
return 0;
}
```