多元一次不定方程
多元一次不定方程的定义以及解的判定定理定理1推论1推论2推论3
例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
∈
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
可以发现，我们用两个参数表示了三元一次不定方程的通解。