多元一次不定方程
多元一次不定方程的定义以及解的判定定理
形如
a 1 x 1 + a 2 x 2 + ⋯ + a n x n = N a_1x_1 + a_2x_2 + \dots + a_nx_n = N a1x1+a2x2+⋯+anxn=N
的方程称为多元一次不定方程，其中 a 1 , a 2 , … , a n , N ∈ Z , n ≥ 2 , a_1,a_2,\dots,a_n,N \in \mathbb{Z}, n \ge 2, a1,a2,…,an,N∈Z,n≥2,并且 a 1 , a 2 , … , a n a_1,a_2,\dots,a_n a1,a2,…,an都不为零。
我们研究的时候研究 a 1 , a 2 , … , a n a_1,a_2, \dots, a_n a1,a2,…,an都大于零的情况，可以通过变量替换转换成这个形式，也方便我们写代码
我们可以由二元一次不定方程的有解的判定联想到多元的形式，注意到
a 1 x 1 + a 2 x 2 + ⋯ + a n x n = N 有整数解 ⇔ g c d ( a 1 , a 2 , … , a n ) ∣ N a_1x_1 + a_2x_2 + \dots + a_nx_n = N 有整数解 \Leftrightarrow gcd(a_1, a_2, \dots, a_n) \mid N a1x1+a2x2+⋯+anxn=N有整数解⇔gcd(a1,a2,…,an)∣N
这个是成立的。
于是我们有定理1
定理1
不定方程 a 1 x 1 + a 2 x 2 + ⋯ + a n x n = N a_1x_1 + a_2x_2 + \dots + a_nx_n = N a1x1+a2x2+⋯+anxn=N有整数解的充要条件是 ( a 1 , a 2 , … , a n ) ∣ N (a_1,a_2,\dots,a_n) \mid N (a1,a2,…,an)∣N。
这里就不证了，与二元的证明是类似的，读者自证（不会的读者请移步上一节）。
由定理1我们可以得到一个推论1。
推论1
若 ( a 1 , a 2 , … , a n ) = d , (a_1,a_2,\dots,a_n)=d, (a1,a2,…,an)=d,则存在 x 1 , x 2 , … , x n ∈ Z , x_1,x_2,\dots,x_n \in \mathbb{Z}, x1,x2,…,xn∈Z,有 a 1 x 1 + a 2 x 2 + ⋯ + a n x n = d a_1x_1+a_2x_2+\dots+a_nx_n=d a1x1+a2x2+⋯+anxn=d。
这个推论跟之前的那个是类似的，是裴蜀定理的一个扩展。这个也是可以反过来的，可以互相推出。
推论2
( a 1 , a 2 , … , a n ) = 1 (a_1,a_2,\dots,a_n)=1 (a1,a2,…,an)=1当且仅当存在 x 1 , x 2 , … , x n ∈ Z , x_1,x_2,\dots,x_n \in \mathbb{Z}, x1,x2,…,xn∈Z,有
a 1 x 1 + a 2 x 2 + ⋯ + a n x n = 1 a_1x_1+a_2x_2+\dots+a_nx_n=1 a1x1+a2x2+⋯+anxn=1
推论3
( a 1 , a 2 , … , a n ) = d (a_1,a_2,\dots,a_n)=d (a1,a2,…,an)=d当且仅当 a i = d c i a_i=dc_i ai=dci且 ( c 1 , c 2 , … , c n ) = 1 (c_1,c_2,\dots,c_n)=1 (c1,c2,…,cn)=1.
这个实际上是第二节注解4的一个推广。
下面我们来看怎么解。
例1
求 9 x + 24 y − 5 z = 1000 9x+24y-5z=1000 9x+24y−5z=1000的一切整数解
首先 g c d ( 9 , 24 , 5 ) = 1 ∣ 1000 gcd(9, 24, 5) = 1 \mid 1000 gcd(9,24,5)=1∣1000一定有整数解。
我们转化一下
9 x + 24 y = g c d ( 9 , 24 ) t = 3 t , 3 t − 5 z = 1000 9x+24y=gcd(9, 24)t=3t, 3t-5z=1000 9x+24y=gcd(9,24)t=3t,3t−5z=1000
我们分别解然后带进去就很容易求解了，再多次也是一样的方法，只是过程可能比较繁琐
也就是说我们要解
3 x + 8 y = t , 3 t − 5 z = 1000 3x+8y=t,3t-5z=1000 3x+8y=t,3t−5z=1000
我们先来求 3 x + 8 y = 1 3x+8y=1 3x+8y=1的特解，
根据瞪眼法 x 0 = 3 , y 0 = − 1 x_0=3,y_0=-1 x0=3,y0=−1
所以 3 x + 8 y = t 3x+8y=t 3x+8y=t有特解 x 0 = 3 t , y 0 = − t x_0=3t,y_0=-t x0=3t,y0=−t
所以 3 x + 8 y = t 3x+8y=t 3x+8y=t的通解 x = 3 t − 8 u , y = − t + 3 u x=3t-8u,y=-t+3u x=3t−8u,y=−t+3u
类似的我们可以得出 3 t − 5 z = 1000 3t-5z=1000 3t−5z=1000的通解 t = 2000 + 5 v , z = 1000 + 3 v t=2000+5v,z=1000+3v t=2000+5v,z=1000+3v
把 t t t带入上式中的 x , y x,y x,y，于是我们可以得到整个方程通解
x = 6000 + 15 v − 8 u , y = − 2000 − 5 v + 3 u , z = 1000 + 3 v , u , v ∈ Z x=6000+15v-8u,y=-2000-5v+3u,z=1000+3v, u,v \in \mathbb{Z} x=6000+15v−8u,y=−2000−5v+3u,z=1000+3v,u,v∈Z
可以发现，我们用两个参数表示了三元一次不定方程的通解。