[基础数论]不定方程笔记
2026-07-19 18:58:25
[基础数论]不定方程笔记
Glassy_Sky
·
2023-05-11 21:06:01
·
个人记录
前言
在学习本节内容前，最好先学习同余的基本性质以加深理解。
一堆定理
定理1：
若
a,b,m,n \in \mathbb Z,c \mid a,c \mid b
则
c \mid (ma+nb)
证明：
令 a=ce,b=cf ，
代入 ma+nb 再提公因式即可。
定理2：
若
a,b,c \in \mathbb Z
则
(a+cb,b)=(a,b)
证明：
由定理1证明二者公因子相同即可。
定理3：
两个不全为零的整数 a,b 的最大公因子是 a,b 线性组合的最小正整数.
证明：令 d 是 a,b 的线性组合中最小的正整数， d = ma + nb , 其中 m,n 是整数，我们将证明 d \mid a,d \mid b 。
由带余除法，得到 a=dq+r, 0≤r 由 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 。 得证。 定理4： 若 a,b 是正整数， 则所有 a,b 的线性组合构成的集合与所有 (a,b) 的倍数构成的集合相同。 证明：由定理1得 a,b 的线性组合都是 (a,b) 倍数。 由定理3得 (a,b) 属于线性组合，其倍数显然也属于线性组合。 得证。 定理5： 若 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 定理6： 若 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) 扩展欧几里得算法 扩展欧几里得算法就是在朴素欧几里得上求一组未知数 (x,y) 的解。 公式推导 对于 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 #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 #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 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; } ```