如何解二元一次不定方程
- 格式：docx
- 大小：33.58 KB
- 文档页数：3
如何解二元一次不定方程
意思就是说求方程𝓪x+by=c中𝓍,𝓎的整数解。
对于这个问题，数论中有专门的解法，一般是采用辗转相除法来做，就是类似于求最大公因子的相除过程。因为可能直接用辗转相除法大家可能不好理解，我先用普通的解方程的方法来做，然后再跟大家介绍数论中的做法。
为了简化问题，我们先求7𝓍+4𝓎=1的一切整数解。
解：我们对等式进行变形，得到𝔂=𝟏−𝟕𝔁𝟒=−𝔁+𝟏−𝟑𝔁𝟒 式①
因为𝓎是整数，所以1−3𝓍4也必须是整数，再另𝓎′=1−3𝓍4，变形得到4𝓎′+3𝓍=1，再次变形表达成𝔁=𝟏−𝟒𝔂′𝟑=−𝔂′+𝟏−𝔂′𝟑 式②
因为𝓍是整数，所以1−𝓎′3也必须是整数，然而1−𝓎′3是整数的条件就是1−𝓎′是3的倍数，所以𝔂′=𝟑𝓶+𝟏 式③
这样1−𝓎′3是整数才能满足。从式③反推回式②，得到 𝔁=−𝟏−𝟒𝓶
再反推回式①得到 𝔂=𝟐+𝟕𝓶
至此，我们就得到了不定方程7𝓍+4𝓎=1的全部整数解𝓍=−1−4𝓂，𝓎=2+7𝓂式中𝓂可以取任意的整数。
对结果表示怀疑？那么我们试几个𝓂值：
当𝓂=0时，𝓍=−1，𝓎=2；7𝓍+4𝓎=7×(−1)+4×2=1
当𝓂=1时，𝓍=−5，𝓎=9；7𝓍+4𝓎=7×(−6)+4×9=1
如果还想试的话，自己去试吧，如果找到不对的情况请立刻去买彩票！ O(∩_∩)O~
我们来分析一下这种计算方法，看看这么巧妙是如何实现的：
式①之中，我们通过变形把系数大的项移动到等式右边，然后把左边的系数除过去，得到𝓎=1−7𝓍4 式中𝓍 𝓎都为整数，所以我们又变形得到𝓎=−𝓍+1−3𝓍4，为何要这样呢？这就是关键所在！因为这样做就逐步的把系数减小了，前面的式子分子系数为7，而后面的变成了3！而根据𝟏−𝟑𝔁𝟒是一个整数，所以我们又可以列出新的不定方程，这个方程就要比我们最早的方程更简单，这样一直演算下去，最后分子系数肯定会变成1，比如𝓍=−𝒶𝓎′+𝒶−𝓎′𝒸，这时因为𝒶−𝓎′𝒸是整数，假设等于𝓂，得到𝒶−𝓎′𝒸=𝓂，变形得到𝓎′=𝒶−𝒸𝓂，这就是最愉快的时候的，我们再一路反推回去，就可以得到原始的𝓍 𝓎的通解表达式了。
上面的分析例子虽然简单，但是思想是对所有的不定方程都通用的，如果没有理解的话，请再仔细的看一遍，自己再演算一遍，肯定就OK了。
以上就是普通解二元不定方程的方法，时间很晚了，数论上的方法我就先不讲了，下次补上。
Winxos 2009-8-26 3:02:53 今天我接着上次的给大家讲一下数论中用的辗转相除法。
实际上辗转相除法就是上面解方程法的简化计算版本，原理是一样的。
我们还是以𝟕𝔁+𝟒𝔂=𝟏为例子来讨论
式中𝒶=7,𝒷=4，我们对𝒶,𝒷来辗转相除（就是求𝒶,𝒷的最大公因子的过程），如下：
𝒶=7除以𝒷=4，商𝓆1为1，余数为𝟑，然后让𝒷的值做𝒶，余数做𝒷，重复上一步操作，
𝒶=4除以𝒷=𝟑，商𝓆2为1，余数为1，停止计算（余数为0或者1就停止计算）。
我们建立一个辅助表格：
0 1 2 3 … K
𝓆 𝓆1 𝓆2 𝓆3 … 𝓆k
𝓅 1 𝓆1 𝓅2 𝓅3 … 𝓅k
ℚ 0 1 ℚ2 ℚ3 … ℚk
表1 二元一次不定方程辅助表
下面我来告诉大家如何使用这个表，我们已经计算得到𝓺𝟏=𝟏，𝓺𝟐=𝟏，
我们也知道𝓅0=1，𝓅1=𝓆1，ℚ0=0，ℚ1=1，将上面的数填入表中，我们得到下面的表：
0 1 2
𝓆 1 1
𝓅 1 1 𝓅2
ℚ 0 1 ℚ2
表2
根据𝓹𝐤=𝓺𝐤𝓹𝐤−𝟏+𝓹𝐤−𝟐我们得到𝓹𝟐=𝓺𝟐𝓹𝟏+𝓹𝟎=𝟏×𝟏+𝟏=𝟐
根据ℚ𝐤=𝓺𝐤ℚ𝐤−𝟏+ℚ𝐤−𝟐我们得到ℚ𝟐=𝓺𝟐ℚ𝟏+ℚ𝟎=𝟏×𝟏+𝟎=𝟏
公式 1：不定方程的一个特解为𝔁=(−𝟏)𝐧−𝟏ℚ𝐧 ,𝔂=(−𝟏)𝐧𝓹𝐧 其中n就是表中的第一行。
所以我们得到了不定方程𝟕𝔁+𝟒𝔂=𝟏的：
一个特解为：𝔁=(−𝟏)𝟐−𝟏=−𝟏 ,𝔂=(−𝟏)𝟐𝟐=𝟐
下面给出几个相关的定理：
定理 1：如果二元一次不定方程𝓪𝔁+𝓫𝔂=𝓬有一整数解𝔁=𝔁𝟎 ,𝔂=𝔂𝟎 ；
又假定(𝓪,𝓫)=𝓭即𝓪=𝓪𝟏𝓭 ,𝓫=𝓫𝟏𝓭
则𝓪𝔁+𝓫𝔂=𝓬的一切解可以表示为𝔁=𝔁𝟎−𝓫𝟏𝓽 ,𝔂=𝔂𝟎+𝓪𝟏𝓽 ,其中 𝓽=𝟎,±𝟏,±𝟐,…
定理 2：𝓪𝔁+𝓫𝔂=𝓬有整数解的充分必要条件是(𝓪,𝓫)|𝓬
术语解释：(𝓪,𝓫)表示 𝓪,𝓫的最大公因子，(𝓪,𝓫)|𝓬 表示𝓪,𝓫的最大公因子能整除𝓬
根据上面的定理1，我们可以得到不定方程𝟕𝔁+𝟒𝔂=𝟏的通解为：
𝔁=−𝟏−𝟒𝓽 ,𝔂=𝟐+𝟕𝓽
经过上面的练习，现在给出具体的求解𝓪𝔁+𝓫𝔂=𝓬的步骤：
① 判断是否有解，看是否(𝓪,𝓫)|𝓬
② 若(𝓪,𝓫)|𝓬 将𝓪𝔁+𝓫𝔂=𝓬 两边同时除以(𝓪,𝓫)，得到𝓪′𝔁+𝓫′𝔂=𝓬′ ；𝓪′,𝓫′互质
③ 先利用表1及公式1，求的|𝓪′|𝔁+|𝓫′|𝔂=𝟏的一个特解
④ 将特解放大𝓬′倍，再绝对值变换，得到𝓪′𝔁+𝓫′𝔂=𝓬′的特解
⑤ 根据定理1，求得𝓪′𝔁+𝓫′𝔂=𝓬′的通解，这也是原方程𝓪𝔁+𝓫𝔂=𝓬的通解
⑥ 完毕
下面我再给出一个书上的复杂点的例子，以及用上面的方法求解过程。 表构造说明：第一行表示第几项，第二行𝓆就是我们计算过程中得到的商序列𝓆k，第三行规律为𝓅0=1，𝓅1=𝓆1，𝓹𝐤=𝓺𝐤𝓹𝐤−𝟏+𝓹𝐤−𝟐 ，形象描述就是𝓅从𝓅2开始，等于沿着表中红色箭头方向第一项加上后两项的乘积。第四行规律为ℚ0=0，ℚ1=1，ℚ𝐤=𝓺𝐤ℚ𝐤−𝟏+ℚ𝐤−𝟐 绿色箭头方向。 题目：求𝟏𝟏𝟏𝔁−𝟑𝟐𝟏𝔂=𝟕𝟓的一切整数解。
解：
① 判断是否有解
(𝟏𝟏𝟏,−𝟑𝟐𝟏)=𝟑 而 𝟑|𝟕𝟓所以该不定方程有解
② 变形处理
等式两端同时除以(𝟏𝟏𝟏,−𝟑𝟐𝟏) 得到𝟑𝟕𝔁−𝟏𝟎𝟕𝔂=𝟐𝟓
③ 求特解
我们先求解𝟑𝟕𝔁−𝟏𝟎𝟕𝔂=𝟏，为了计算方便，我们进行绝对值处理，以及变量换名字，我们变成求解𝟏𝟎𝟕𝔁+𝟑𝟕𝔂=𝟏，辗转除107与37，过程如下：
𝓪=𝟏𝟎𝟕除以𝓫=𝟑𝟕，商𝓺𝟏为𝟐，余数为𝟑𝟑
𝓪=𝟑𝟕除以𝓫=𝟑𝟑，商𝓺𝟐为𝟏，余数为𝟒
𝓪=𝟑𝟑除以𝓫=𝟒，商𝓺𝟑为𝟖，余数为𝟏
余数为1，停止计算
我们将𝓺𝟏=𝟐 ,𝓺𝟐=𝟏 ,𝓺𝟑=𝟖带入表 1，得到：
0 1 2 3
𝓆 2 1 8
𝓅 1 2 𝓅2 𝓅3
ℚ 0 1 ℚ2 ℚ3
根据𝓹𝐤=𝓺𝐤𝓹𝐤−𝟏+𝓹𝐤−𝟐我们得到𝓹𝟐=𝓺𝟐𝓹𝟏+𝓹𝟎=𝟏×𝟐+𝟏=𝟑
根据ℚ𝐤=𝓺𝐤ℚ𝐤−𝟏+ℚ𝐤−𝟐我们得到ℚ𝟐=𝓺𝟐ℚ𝟏+ℚ𝟎=𝟏×𝟏+𝟎=𝟏
继而求得：
𝓹𝟑=𝓺𝟑𝓹𝟐+𝓹𝟏=𝟖×𝟑+𝟐=𝟐𝟔
ℚ𝟑=𝓺𝟑ℚ𝟐+ℚ𝟏=𝟖×𝟏+𝟏=𝟗
根据公式 1，得到𝟏𝟎𝟕𝔁+𝟑𝟕𝔂=𝟏的特解为𝔁=(−𝟏)𝟑−𝟏𝟗=𝟗 ,𝔂=(−𝟏)𝟑𝟐𝟔=−𝟐𝟔
所以𝟑𝟕𝔁−𝟏𝟎𝟕𝔂=𝟏的特解为𝔁=−𝟐𝟔 ,𝔂=−𝟗
④ 求𝟑𝟕𝔁−𝟏𝟎𝟕𝔂=𝟐𝟓的特解
将𝟑𝟕𝔁−𝟏𝟎𝟕𝔂=𝟏的特解放大25倍，得到𝟑𝟕𝔁−𝟏𝟎𝟕𝔂=𝟐𝟓的特解𝔁=−𝟔𝟓𝟎 ,𝔂=−𝟐𝟐𝟓
⑤ 求𝟏𝟏𝟏𝔁−𝟑𝟐𝟏𝔂=𝟕𝟓的通解
根据定理 1，得到𝟑𝟕𝔁−𝟏𝟎𝟕𝔂=𝟐𝟓的通解为
𝔁=−𝟔𝟓𝟎+𝟏𝟎𝟕𝓽 ,𝔂=−𝟐𝟐𝟓+𝟑𝟕𝓽 ,𝓽=𝟎,±𝟏,±𝟐,…
或者为了好看，处理小一点，表达成：
𝔁=−𝟖+𝟏𝟎𝟕𝓽 ,𝔂=−𝟑+𝟑𝟕𝓽 ,𝓽=𝟎,±𝟏,±𝟐,…
这也就是题目𝟏𝟏𝟏𝔁−𝟑𝟐𝟏𝔂=𝟕𝟓的通解。
完毕。
辗转相除法是我国古代很早前就发明的算法，为我们的祖先感到骄傲。
希望看到这篇文章的朋友能了解辗转相除法，能够很轻松的解二元一次不定方程，那样我就很满足了。如果朋友您从这里学会了二元一次不定方程的解法，不妨留下脚印，如果还有什么不理解的地方欢迎给我留言。
Winxos 2009年8月27日14:01:05
