最后更新: 2025-03-08 12:01 查看: 293 次纠错评论(0) 课件开VIP

百鸡问题

## 百鸡问题
这是公元 5 世纪末，我国数学家张丘建在他所著《算经》里提出的一个著名的不定方程问题。百鸡问题通俗叙述为：

> 公鸡一只值五文钱，母鸡一只值三文钱，小鸡三只值一文钱，现在买了这三种鸡共一百只，恰用了一百文钱。问公鸡，母鸡，小鸡各买多少只？

古希腊伟大的数学家丢番图（Diophantus），在他所著《算术》中，共载有 189 个问题，对每个题都给出了出人意料的巧妙解法，启迪着人们的智慧。后人把这类关于不定方程的题目叫做丢番图问题。在求整系数方程的整数解时，这个方程就称为不定方程。一次不定方程（又称线性不定方程）的形式是

$$
a_1 x_1+a_2 x_2+\cdots+a_n x_n=k
$$

其中 $a_1, a_2, \cdots, a_n, k$ 都为整数。
该方程有解的充分必要条件是 $\left(a_1, a_2, \cdots, a_n\right) \mid k$ 。
设 $x=x_0, y=y_0$ 是不定方程 $a x+b y=k$ 的一个解，则它的一切解是

$$
x=x_0-\frac{b}{(a, b)} r, \quad y=y_0+\frac{a}{(a, b)} r,
$$

其中 $r$ 为任意整数．
对有些不定方程，由题目的特点，可以用更简捷和巧妙的方法去解。

## 求解
现在我们来解百鸡问题。
设 $x, y, z$ 分别表示公鸡，母鸡，小鸡的只数，由题意有

$$
\left\{\begin{array}{l}
5 x+3 y+\frac{1}{3} z=100 ...(1) \\
x+y+z=100  ...(2)
\end{array}\right.
$$

$(1) \times 3- (2)$得

$$
14 x+8 y=200
$$

这是个一次不定方程．用 $(14,8)=2$ 除，就有
$$
7 x+4 y=100  ...(3）
$$

即

$$
y=\frac{-7 x+100}{4}=-x+25+\frac{-3 x}{4}
$$

令 $-3 x / 4=z_1$ ，即

$$
3 x+4 z_1=0
$$

从而

$$
x=\frac{-4 z_1}{3}=-z_1+\frac{-z_1}{3}
$$

再令 $-z_1 / 3=t$ ，即 $z_1=-3 t$ ，代入 $x$ 的表达式，
得

$$
x=\frac{-4 \times(-3 t)}{3}=4 t
$$

再代入 $y$ 的表达式，得

$$
y=\frac{-7 \times 4 t+100}{4}=25-7 t
$$

于是由方程（2），得

$$
z=100-x-y=75+3 t
$$

因此有

$$
\left\{\begin{array}{l}
x=4 t, \\
y=25-7 t, \\
z=75+3 t,
\end{array} \quad t\right. \text { 为整数. }
$$

因 $x, y, z$ 是非负数，所以 $t$ 只能取 $0,1,2,3$ ，因此得四组解

$$
\left\{\begin{array} { l } 
{ x = 0 , } \\
{ y = 2 5 , } \\
{ z = 7 5 ; }
\end{array} \quad \left\{\begin{array} { l } 
{ x = 1 , } \\
{ 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.
$$

如果 $x, y, z$ 是正整数，那么只有后三组解．

## 思路总结
在解一次不定方程时，总的思路是导入新的未知数，使方程系数的绝对值逐渐减少，逐步归结为解与原方程同解的其他不定方程，最后变为有一个未知数的系数是 1 或 -1 的这种最简单的情况．在有的情况下，可以直接观察而找出解，如求出 $2 x+6 y=18$ 的所有解．该式除以公因子后，得 $x+3 y=$ 9 ，由观察法知 $y=0, x=9$ 是一组解，因此方程所有解可写为

$$
\left\{\begin{array}{l}
x=9+3 t, \\
y=-t,
\end{array} \quad \text { 其中 } t\right. \text { 为整数. }
$$

现在，我们给出解一次不定方程的另一个更好的方法，即用同余式去解不定方程。我们给出线性同余式

$$
a x \equiv b(\bmod m) .
$$

> 同余的定义： 若两个数 $a$ 与 $b$ 除以 $m$ 的余数相同，或说 $a-b$ 可被 $m$ 整除，则说 $a$ 与 $b$ 同余于 $m$ 或 $a$ 等于 $b$ 模 $m$ 。 详见[数论](https://kb.kmath.cn/kbase/detail.aspx?id=792)

一般将“ $a$ 与 $b$ 同余于 $m$ "记作 $a \equiv b \quad(\bmod m)$

显然，当且仅当有整数 $x$ 和 $k$ 满足 $a x=b+k m$ 时，同余式 $a x$ $\equiv b(\bmod m)$ 有解．这本质上是解一次不定方程问题，但引进了不同的记法后，我们会看到，这不但不会令人厌烦，反倒使问题处理得更优美和发人深思。

我们易知，要存在一个整数解 $r$ 满足

$$
a x \equiv b(\bmod m),
$$

即

$$
a r \equiv b(\bmod m)
$$

则对任一整数 $k$ ，有

$$
a(r+k m) \equiv a r \equiv b(\bmod m)
$$

在 $r+k m(k=0, \pm 1, \pm 2, \cdots)$ 这些整数中，恰有一个（比方说$S)$ 满足 $0 \leqslant S<m$ ，这是因为每个整数都介于 $m$ 的相继两个倍数之间．若 $r$ 对某个 $k$ 满足

$$
k m<r<(k+1) m,
$$

则有

$$
0 \leqslant r-k m<m,
$$

我们可令 $S=r-k m$ 。我们将这样一个数挑出，并称它为 $a x \equiv$ $b(\bmod m)$ 的一个解，故解就是这样一个数 $r$ ，它满足 $a x \equiv$ $b(\bmod m)$ ，且为一个最小正剩余。如 $x=2,9,16, \cdots,-5$ ， $-12, \cdots$ 均满足同余式 $2 x \equiv 4(\bmod 7)$ ，它们都包含在 $x \equiv$ $2(\bmod 7)$ 中，也都包含在 $x \equiv 9(\bmod 7)$ 中，但按我们的约定，只把 2 称为解，因它是对模 7 的最小剩余．

线性同余式 $a x \fallingdotseq b(\bmod m)$ 可以无解，只有一解或许多解，这可归结为如下定理：

若 $(a, m)\ne |b\}$ ，则 $a x \equiv b(\bmod m)$ 无解；若 $(a, m) \mid b$ ，则它恰有 $(a, m)$ 个解．

例如， $2 x \equiv 1(\bmod 3)$ 只有 $x=2$ 一个解； $2 x \equiv 1(\bmod 4)$ 无解； $2 x \equiv 4(\bmod 6)$ 有两个解 2 和 5 。

求解同余式可以用观察法，但一般还是变换其系数，使之有可能进行消去的步骤。如 $4 x \equiv 1(\bmod 15)$ ，改写成

$$
4 x \equiv 1 \equiv 16(\bmod 15)
$$

消去4，得

$$
x \equiv 4(\bmod 15)
$$

在解一次不定方程时，同余式方法也可使用，如求解不定方程 $a x+b y=c$ ，可以考虑下面两个同余式：

$$
a x \equiv c(\bmod b), \quad b y \equiv \equiv c(\bmod a),
$$

我们可选其中任一个，并解出其变量，然后将结果代入原方程而求得其全部解．如解不定方程 $9 x+16 y=35$ ，由

$$
16 y \equiv 35(\bmod 9),
$$

变换系数，得

$$
7 y \equiv 35(\bmod 9)
$$

约去 7 ，得

$$
y \equiv 5(\bmod 9)
$$

也即对某一个整数 $t$ ，有 $y=5+9 t$ ，将此代入原方程，得

$$
9 x+16(5+9 t)=35 \text { 或 } 9 x+144 t=-45 \text {, }
$$

即

$$
x+16 t=-5
$$

因而我们求得了所有解；

$$
\left\{\begin{array}{l}
x=-5-16 t, \\
y=5+9 t,
\end{array} \quad t\right. \text { 是整数. }
$$

## 推广
现在把上面学到的问题应用到更多民间故事“搬砖”里：
> 100个人，100块砖，男搬4，女搬3,3个小孩搬一块砖，问有多少男人？多少女人，多少小孩？

题目解释：搬砖时，男人一次能搬4块，女人一次能搬3块，3个小孩一次能搬1块，现在有100个人100块砖，问有多少男人？多少女人？多少小孩？

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：没有了

下一篇：聪明的囚徒

本文对您是否有用？有用 (0) 无用 (0)