二元一次不定方程 |
您所在的位置：网站首页 › 不定方程的定理是什么 › 二元一次不定方程 |
二元一次不定方程
|
在数论中，二元一次不定方程是形如 a x + b y = c {\displaystyle a x + b y = c} 的不定方程，其中 a , b {\displaystyle a, b} 是整数，这个方程是关于整数变量 x , y {\displaystyle x, y} 的方程。 目录 1 解法 2 示例 3 正解（非负解）问题 4 上下节 解法[]定理：上述方程有解的充要条件是 ( a , b ) ∣ c {\displaystyle (a, b) \mid c} ，在有解时，若已知方程有一组特解 ( x 0 , y 0 ) {\displaystyle (x_0, y_0)} ，那么它的所有解的形式是 { x = x 0 + b ( a , b ) s , y = y 0 − a ( a , b ) s , s ∈ Z . {\displaystyle \begin{cases} x = x_0 + \dfrac{b}{(a, b)}s, \\ y = y_0 - \dfrac{a}{(a, b)}s, \end{cases} \quad s \in \Z.}因此，我们仅需求出一组特解即可，如果方程有解，我们总可以将上述方程先做化简，为 a ( a , b ) x + b ( a , b ) y = c ( a , b ) {\displaystyle \dfrac{a}{(a, b)} x + \dfrac{b}{(a, b)} y = \dfrac{c}{(a, b)}} 下面，我们总假设 ( a , b ) = 1. {\displaystyle (a, b) = 1.} 做变换 x = c x ′ , y = c y ′ {\displaystyle x = c x', y = c y'} ，于是，原方程等价于 a x ′ + b y ′ = 1. {\displaystyle a x' + b y' = 1.} 当式子简单时可以直接看出一组解，其实，注意到这就是在辗转相除法中介绍的贝祖等式，它可以由辗转相除的方法求出一组特解 ( x 0 ′ , y 0 ′ ) {\displaystyle (x' _0, y'_0)} ，进而带入所作的变换中，有原方程的特解 ( x 0 , y 0 ) = ( c x 0 ′ , c y 0 ′ ) {\displaystyle (x_0, y_0) = (c x' _0, c y'_0)} 示例[]求方程 28 x + 92 y = 52 {\displaystyle 28x+92y=52} 的所有整数解。 因为 ( 28 , 92 ) = 4 ∣ 52 {\displaystyle (28, 92) = 4 \mid 52} ，所以原方程有解。原方程化为 7 x + 23 y = 13 {\displaystyle 7x+23y=13} ，先解方程 7 x ′ + 23 y ′ = 1 {\displaystyle 7x'+23y'=1} ，对 ( 23 , 7 ) {\displaystyle (23, 7)} 做辗转相除，有 23 = 3 × 7 + 2 7 = 3 × 2 + 1. {\displaystyle 23 = 3 \times 7 + 2 \qquad 7 = 3 \times 2 + 1.} 于是 1 = 7 − 3 × 2 = 7 − 3 × ( 23 − 3 × 7 ) = 10 × 7 − 3 × 23. {\displaystyle 1 = 7 - 3 \times 2 = 7 - 3 \times (23 - 3 \times 7) = 10 \times 7 - 3 \times 23.} 于是题目中的方程一组特解为 ( x 0 , y 0 ) = 13 ( 10 , − 3 ) = ( 130 , − 39 ) {\displaystyle (x_0, y_0) = 13 (10, -3) = (130, -39)} ，所有的解为 { x = 130 + 23 s , y = − 39 − 7 s , s ∈ Z . {\displaystyle \begin{cases} x = 130 + 23s, \\ y = -39 - 7s, \end{cases} \quad s \in \Z.} 当数字过大时，可以不用先找 ( a , b ) {\displaystyle (a,b)} ，也不用判断是否有解，直接做辗转相除即可。 正解（非负解）问题[]在实际应用场合中，有时要求方程的解取正数或非负数，这时由以上方法取得的解有一部分可能不适用，这时就要对方程做更精细的讨论。对于方程 a x + b y = c {\displaystyle a x + b y = c} 当 a , b {\displaystyle a, b} 异号（不妨假设 a > 0 {\displaystyle a>0} ）时，方程总有无穷多组非负解，只需要在解的通式 { x = x 0 − b ( a , b ) s , y = y 0 + a ( a , b ) s , s ∈ Z . {\displaystyle \begin{cases} x = x_0 - \dfrac{b}{(a, b)}s, \\ y = y_0 + \dfrac{a}{(a, b)}s, \end{cases} \quad s \in \Z.} 中取充分大的 s {\displaystyle s} 即可。当 a , b {\displaystyle a, b} 同号时，只有 a , b , c {\displaystyle a,b,c} 同号时才有可能存在非负解，实际上可以证明：当 c > a b − a − b {\displaystyle c > ab - a - b} 时不定方程有非负解，解的个数为 [ c a b ] {\displaystyle \left[\dfrac{c}{ab}\right]} 或 [ c a b ] + 1 {\displaystyle \left[\dfrac{c}{ab}\right] + 1} （需验证不同情形），而当 c = a b {\displaystyle c = ab} 时不定方程无非负解。要求出这些解，只需在解的通式中令两个未知元大于等于零即可。 而如果 x = 0 {\displaystyle x = 0} 或 y = 0 {\displaystyle y=0} ，必须满足 b ∣ c {\displaystyle b \mid c} 或 a ∣ c {\displaystyle a \mid c} 。同样假设 a , b , c {\displaystyle a,b,c} 同号，那么当 c > a b {\displaystyle c > ab} 时原不定方程有正解，且解数为 − [ − c a b ] − 1 {\displaystyle - \left[-\dfrac{c}{ab}\right]-1} 或 − [ − c a b ] {\displaystyle -\left[-\dfrac{c}{ab}\right]} ，而当 c = a b {\displaystyle c = ab} 时不定方程无正解。要求出这些解，只需在解的通式中令两个未知元大于零即可。 n {\displaystyle n} 元一次的不定方程可以化为 n − 1 {\displaystyle n-1} 个二元一次不定方程求解，其自由因子有 n − 1 {\displaystyle n-1} 个。求解的相关方法参看上一节。 上下节[] 上一节：不定方程 下一节：Pythagoras 方程 初等数论（学科代码：1101710，GB/T 13745—2009） 整除理论 整除 ▪ 带余除法 ▪ 素数 ▪ 公因数 ▪ 辗转相除法 ▪ 公倍数 ▪ 惟一因子分解定理 ▪ 容斥原理 同余理论 同余 ▪ 同余类（完全代表系，缩同余类） ▪ 同余类的代数结构 ▪ 一次同余方程 ▪ 中国剩余定理 ▪ 线性同余方程组 ▪ 二元一次同余方程组 剩余理论 Euler-Fermat 定理 ▪ 原根 ▪ 指数 ▪ 威尔森定理 ▪ K 次剩餘 ▪ 二次剩余 ▪ Legendre 符号 ▪ 二次互反律 ▪ Jacobi 符号 ▪ 二次同余方程 数论函数 除数函数 ▪ 除数和函数 ▪ Euler 函数 ▪ Liouville 函数 ▪ Möbius 反演公式 ▪ 数论函数的卷积 ▪ 数论函数的均值 ▪ Dirichlet 特征 不定方程 二元一次不定方程 ▪ Pythagoras 方程 ▪ 四平方和问题 ▪ 二平方和问题 ▪ Fermat 方程 ▪ 立方和问题 素数分布 Eratosthenes 筛法 ▪ 素数定理 ▪ Chebyshev 函数 ▪ Mangoldt 函数 ▪ Euler 恒等式 所在位置：数学（110）→ 数论（11017）→ 初等数论（1101710） |
的不定方程，其中
a
,
b
{\displaystyle a, b}
是整数，这个方程是关于整数变量
x
,
y
{\displaystyle x, y}
的方程。
目录
1 解法
2 示例
3 正解（非负解）问题
4 上下节
解法[]
，在有解时，若已知方程有一组特解
(
x
0
,
y
0
)
{\displaystyle (x_0, y_0)}
，那么它的所有解的形式是
下面，我们总假设
(
a
,
b
)
=
1.
{\displaystyle (a, b) = 1.}
做变换
x
=
c
x
′
,
y
=
c
y
′
{\displaystyle x = c x', y = c y'}
，于是，原方程等价于
a
x
′
+
b
y
′
=
1.
{\displaystyle a x' + b y' = 1.}
当式子简单时可以直接看出一组解，其实，注意到这就是在辗转相除法中介绍的贝祖等式，它可以由辗转相除的方法求出一组特解
(
x
0
′
,
y
0
′
)
{\displaystyle (x' _0, y'_0)}
，进而带入所作的变换中，有原方程的特解
(
x
0
,
y
0
)
=
(
c
x
0
′
,
c
y
0
′
)
{\displaystyle (x_0, y_0) = (c x' _0, c y'_0)}
示例[]
的所有整数解。
，所以原方程有解。原方程化为
7
x
+
23
y
=
13
{\displaystyle 7x+23y=13}
，先解方程
7
x
′
+
23
y
′
=
1
{\displaystyle 7x'+23y'=1}
，对
(
23
,
7
)
{\displaystyle (23, 7)}
做辗转相除，有
23
=
3
×
7
+
2
7
=
3
×
2
+
1.
{\displaystyle 23 = 3 \times 7 + 2 \qquad 7 = 3 \times 2 + 1.}
于是
1
=
7
−
3
×
2
=
7
−
3
×
(
23
−
3
×
7
)
=
10
×
7
−
3
×
23.
{\displaystyle 1 = 7 - 3 \times 2 = 7 - 3 \times (23 - 3 \times 7) = 10 \times 7 - 3 \times 23.}
于是题目中的方程一组特解为
(
x
0
,
y
0
)
=
13
(
10
,
−
3
)
=
(
130
,
−
39
)
{\displaystyle (x_0, y_0) = 13 (10, -3) = (130, -39)}
，所有的解为
当数字过大时，可以不用先找
(
a
,
b
)
{\displaystyle (a,b)}
，也不用判断是否有解，直接做辗转相除即可。
正解（非负解）问题[]
）时，方程总有无穷多组非负解，只需要在解的通式
{
x
=
x
0
−
b
(
a
,
b
)
s
,
y
=
y
0
+
a
(
a
,
b
)
s
,
s
∈
Z
.
{\displaystyle \begin{cases} x = x_0 - \dfrac{b}{(a, b)}s, \\ y = y_0 + \dfrac{a}{(a, b)}s, \end{cases} \quad s \in \Z.}
中取充分大的
s
{\displaystyle s}
即可。
同号时才有可能存在非负解，实际上可以证明：当
c
>
a
b
−
a
−
b
{\displaystyle c > ab - a - b}
时不定方程有非负解，解的个数为
[
c
a
b
]
{\displaystyle \left[\dfrac{c}{ab}\right]}
![{\displaystyle \left[{\dfrac {c}{ab}}\right]}](https://services.fandom.com/mathoid-facade/v1/media/math/render/svg/188c5e5c564deb033724e8368305c55314eed75f)
或
[
c
a
b
]
+
1
{\displaystyle \left[\dfrac{c}{ab}\right] + 1}
![{\displaystyle \left[{\dfrac {c}{ab}}\right]+1}](https://services.fandom.com/mathoid-facade/v1/media/math/render/svg/ce120c5061953a637ea6dcb70b2703e5a6bf7730)
（需验证不同情形），而当
c
=
a
b
{\displaystyle c = ab}
时不定方程无非负解。要求出这些解，只需在解的通式中令两个未知元大于等于零即可。
或
y
=
0
{\displaystyle y=0}
，必须满足
b
∣
c
{\displaystyle b \mid c}
或
a
∣
c
{\displaystyle a \mid c}
。同样假设
a
,
b
,
c
{\displaystyle a,b,c}
时原不定方程有正解，且解数为
−
[
−
c
a
b
]
−
1
{\displaystyle - \left[-\dfrac{c}{ab}\right]-1}
![{\displaystyle -\left[-{\dfrac {c}{ab}}\right]-1}](https://services.fandom.com/mathoid-facade/v1/media/math/render/svg/229179c9f5c86c5d14fe84597cb6996be03b2908)
或
−
[
−
c
a
b
]
{\displaystyle -\left[-\dfrac{c}{ab}\right]}
![{\displaystyle -\left[-{\dfrac {c}{ab}}\right]}](https://services.fandom.com/mathoid-facade/v1/media/math/render/svg/d64b3d25e8650d3d9236e53acd18f7cceca41ad0)
，而当
c
=
a
b
{\displaystyle c = ab}
元一次的不定方程可以化为
n
−
1
{\displaystyle n-1}
个二元一次不定方程求解，其自由因子有
n
−
1
{\displaystyle n-1}
【本文地址】