科数网知识库
首页
目录
知识库
初等数论 Elementary Number Theory
初等数论(高中版)
一元一次不定方程
一元一次不定方程
日期:
2023-11-09 19:02
查看:
9
次
更新
导出Word
不定方程是数论中最古老的一个分支. 我国古代对不定方程进行了大量研究, 且研究内容极为丰富. 早在公元前 1100 多年, 我国古代数学家商高就提出了直角三角形的 “勾广三, 股修四, 径隅五” 的著名论断, 这实际上给出了方程 $x^2+y^2=z^2$ 的一组正整数解 $x=3, y=4, z=5$. 大约 1500 年以前, 我国古代另一位数学家张丘建在他编写的《张丘建算经》里, 提出并解决了下面的数学问题: “鸡翁一, 值钱五, 鸡母一, 值钱三, 鸡维三, 值钱一, 百钱买百鸡, 问鸡翁、母、雉各几何?” 这就是人们常说的 “百钱买百鸡” 问题. 如果用 $x$, $y, z$ 分别表示鸡翁、鸡母和鸡维的个数, 那么我们可以得到下面的方程组: $$ \left\{\begin{array}{l} 5 x+3 y+\frac{1}{3} z=100, \\ x+y+z=100 . \end{array}\right. $$ 这两个问题最后都归结为求解一类方程或方程组的整数解. 由于其未知数个数多于方程的个数, 所以我们把这样的方程或方程组叫做不定方程. 由于公元 200 多年, 古希腊数学家丢番图 (Diophantus) 曾讨论了某些不定方程, 因而也有人把不定方程叫做丢番图方程. **二元一次不定方程** 二元一次不定方程是最简单的不定方程, 它的一般形式为 $$ a x+b y=c, $$ 其中 $a, b, c$ 为整数, 且 $a, b$ 不等于零. 显然, 这类不定方程不一定有整数解. 例如, $2 x+4 y=1$ 没有整数解, 因为对任意整数 $x, y, 2 x+4 y$ 恒为偶数, 它不可能等于 1 . 我们感兴趣的是, 不定方程 (1) 何时有整数解? 有解时是否有无穷多个整数解? 这些整数解是否有统一的表达式? 当然, 还有一个问题就是如何求出所有的整数解. 首先看不定方程 (1) 有解时, 整数 $a, b, c$ 具有什么特征. 观察不定方程 $a x+b y=c$ 的形式, 自然联想到它与整除、同余之间的联系. 假定不定方程 (1) 有整数解 $x=x_0, y=y_0$. 因为 $(a, b)|a,(a, b)| b$, 所以 $(a, b) \mid a x_0+b y_0=c$. 也就是说, 不定方程 (1) 有解时, 整数 $a, b, c$ 必须满足: 下面我们来检验一下. 设 $d=(a, b) \mid c$, 令 $a=a^{\prime} d, b=b^{\prime} d, c=c^{\prime} d$, 则不定方程 (1) 简化为 $$ a^{\prime} x+b^{\prime} y=c^{\prime}, $$ 其中 $\left(a^{\prime}, b^{\prime}\right)=1$. 由最大公约数的性质, 存在一对整数 $u, v$, 使得 $a^{\prime} u+b^{\prime} v=1$. 于是 $a^{\prime}\left(u c^{\prime}\right)+b^{\prime}\left(v c^{\prime}\right)=c^{\prime}$, 从而有 $a\left(c^{\prime} u\right)+b\left(c^{\prime} v\right)=c$. 那么 $x=c^{\prime} u, y=c^{\prime} v$ 就是不定方程 (1)的整数解. 综合上述, 我们可以得到不定方程 (1) 有整数解的一个判别准则. 如果不定方程 (1) 有整数解, 那么 $(a, b) \mid c$. 反过来, 当 $(a, b) \mid c$ 时, 不定方程 (1) 一定有整数解. 从前面的分析可以看出, 当不定方程 (1) 有整数解时, 它可以化简为 $x, y$ 的系数互素的不定方程 (2). 基于这个事实, 对有整数解的不定方程 (1), 我们不妨假定 $(a, b)=1$. 设 $(a, b)=1$, 且 $x=x_0, y=y_0$ 为不定方程 (1) 的整数解. 容易检验, 对任意整数 $t$, $$ \left\{\begin{array}{l} x=x_0+b t, \\ y=y_0-a t \end{array}\right. $$ 均为不定方程 (1) 的整数解. 这意味着不定方程 (1) 有整数解时, 必有无穷多个整数解, 从而回答了第二个问题. 任取不定方程 (1) 的整数解 $x=x^{\prime}, y=y^{\prime}$, 则有 $a x^{\prime}+b y^{\prime}=c$. 因为 $a x_0+b y_0=c$, 所以 $$ a\left(x^{\prime}-x_0\right)=b\left(y_0-y^{\prime}\right), $$ 从而 $b \mid a\left(x^{\prime}-x_0\right)$. 因为 $(a, b)=1$, 所以 $b \mid x^{\prime}-x_0$. 于是存在整数 $t$, 使得 $x^{\prime}-x_0=b t$,即 $x^{\prime}=x_0+b t$, 代人上式得 $y^{\prime}=y_0-a t$, 这表明, 不定方程 (1) 的每个解都可以表示成 (3) 式的形式. 至此, 最后两个问题也得到了回答. 通常, 我们把 (3) 式叫做不定方程 (1) 的整数通解, 而把 $x=x_0, y=y_0$ 叫做不定方程 (1) 的一个特解. 综上所述, 我们得到下面的结论. 设 $(a, b)=1$, 则不定方程 $a x+b y=c$ 的整数通解为 $$ \left\{\begin{array}{l} x=x_0+b t, \\ y=y_0-a t \end{array}\right. $$ 其中 $t$ 为任意整数, $x=x_0, y=y_0$ 为不定方程 $a x+b y=c$ 的一个特解. 从上述结论可以看出, 要描述二元一次不定方程的所有整数解, 只需知道它的一个特解即可. 对某些比较简单的不定方程, 如当 $a, b$ 的绝对值较小时, 我们可以直接通过观察或试验得到它的一个特解. 看下面两个例子. 例 1 求不定方程 $5 x+3 y=10$ 的整数通解. 解: 因为 $(5,3)=1$, 而 $1 \mid 10$, 所以原不定方程有整数解. 容易观察, $5 x+3 y=1$ 有一个特解 $x=-1, y=2$. 因此, $x=-10, y=20$ 就是原不定方程的一个特解. 由上述结论, 原不定方程的整数通解为 $$ \left\{\begin{array}{l} x=-10+3 t, \\ y=20-5 t \end{array}\right. $$ 其中 $t$ 为任意整数. 例 2 (百钱买百鸡问题) 求下列不定方程的非负整数解: $$ \left\{\begin{array}{l} 5 x+3 y+\frac{1}{3} z=100 . \\ x+y+z=100 . \end{array}\right. $$ 解: 首先由原不定方程中第一个方程的 3 倍减去第二个方程, 得 $7 x+4 y=100$. 通过观察发现, 不定方程 $7 x+4 y=1$ 有一个特解 $x=-1, y=2$. 因此 $x=-100, y=200$ 是不定方程 $7 x+4 y=100$ 的一个特解. 所以它的整数通解为 $$ \left\{\begin{array}{l} x=-100+4 t, \\ y=200-7 t, \end{array}\right. $$ 其中 $t$ 为任意的整数. 注意到, $0 \leqslant x \leqslant 100,0 \leqslant y \leqslant 100$, 因此有 $$ 25 \leqslant t \leqslant 50,14 \frac{2}{7} \leqslant t \leqslant 28 \frac{4}{7}, $$ 即 $25 \leqslant t \leqslant 28 \frac{4}{7}$. 从而 $t=25,26,27,28$. 再将 $x, y$ 的值代人方程 $x+y+z=100$, 可求得原不定方程有四组非负整数解: $$ \left\{\begin{array} { l } { x = 0 , } \\ { y = 2 5 , } \\ { z = 7 5 ; } \end{array} \quad \left\{\begin{array} { l } { x = 4 , } \\ { y = 1 8 , } \\ { z = 7 8 ; } \end{array} \quad \left\{\begin{array} { l } { x = 8 , } \\ { y = 1 1 , } \\ { z = 8 1 ; } \end{array} \quad \left\{\begin{array}{l} x=12, \\ y=4, \\ z=84 \end{array}\right.\right.\right.\right. $$
上一篇:
弃九验算法
下一篇:
二元一次不定方程的特解
知识库是科数网倾心打造的大型数学知识网站,欢迎各位老师、数学爱好者加入,联系微信 18155261033, 制作不易,也欢迎
赞助
本站。