[数论] [科普]二元一次不定方程的整数解(9楼-10楼）

isee

1. 快速找出一组整数解。

如何快速找出二元一次不定方程的一组整数解？如$$9x+4y=6.\label{ep01}\tag{*}$$
PS:不定方程$9x+4y=6$有实际问题，就是：有9L和4L的两个桶，怎么能打到6L的水呢?

又如$$243x+551y=1.\label{ep02}\tag{**}$$


楼下 realnumber，abababa 给出了平时我们处理这类问题的常见方案，观察法和辗转相除法！其中辗转相除法是极为实用，易行的。具体见三、四、五楼。

我们换一种看上去不太像辗转相除的写法。

我们先来讨论不定方程\eqref{ep01}如何得到一组整数解。先看——

\begin{align}
9\times 1+4\times 0&=9\label{01}\\
9\times 0 +4\times 1&=4\label{02}
\end{align}
$\eqref{01}-2\times \eqref{02}$
\begin{align}
9\times 1-4\times 2&=1\label{03}
\end{align}
$6\times \eqref{03}$
\begin{align}
9\times 6-4\times 12&=6\label{04}
\end{align}
即
\begin{align}
9\times 2-4\times 3&=6\label{05}
\end{align}

这样由\eqref{05}就知道\eqref{ep01}的另一组整数解是$(2,-3)$.
这组整数组对“有9L和4L的两个桶，怎么能打到6L的水呢?”更好些：

这就是说从井里（或者池塘里等等，水源）打水，大桶打2次，每次大桶装满后就向小桶里倒，小桶满了就倒井里，这样，在小桶第3次装满时，大桶里剩余的水就是6L。






---


现在亦如此手法 对不定方程\eqref{ep02}有：

\begin{align}
243\times 1+551\times 0&=243\label{06}\\
243\times 0 +551\times 1&=551\label{07}
\end{align}

$\eqref{07}-2\times \eqref{06}$
\begin{align}
243\times (-2)+551\times 1&=65\label{08}
\end{align}

$\eqref{06}-3\times \eqref{08}$
\begin{align}
243\times 7+551\times (-3)&=48\label{09}
\end{align}

$\eqref{08}-\eqref{09}$
\begin{align}
243\times (-9)+551\times 4&=17\label{10}
\end{align}

$\eqref{09}-2\times \eqref{10}$
\begin{align}
243\times 25+551\times (-11)&=14\label{11}
\end{align}

$\eqref{10}-\eqref{11}$
\begin{align}
243\times (-34)+551\times 15&=3\label{12}
\end{align}

$\eqref{11}-4\times \eqref{12}$
\begin{align}
243\times 161+551\times (-71)&=2\label{13}
\end{align}

$\eqref{12}-\eqref{13}$
\begin{align}
243\times (-195)+551\times 86&=1\label{14}
\end{align}

这样由\eqref{14}就知道\eqref{ep02}的一组整数解是$(-195,86)$.









---


是的，9楼，tommywong，习惯变行，矩阵写法——

$\begin{pmatrix} 1 & 0 & 243\\0 & 1 & 551
\end{pmatrix}
\rightarrow
\begin{pmatrix}
1 & 0 & 243\\-2 & 1 & 65  
\end{pmatrix}
\rightarrow
\begin{pmatrix}
1 & 0 & 243\\7 & -3 & 48
\end{pmatrix}
\rightarrow
\begin{pmatrix}
-9 & 4 & 17\\7 & -3 & 48
\end{pmatrix}
\rightarrow
\begin{pmatrix}
-9 & 4 & 17\\25 & -11& 14
\end{pmatrix}
\rightarrow
\begin{pmatrix}
-34 & 15 & 3\\25 & -11& 14
\end{pmatrix}
\rightarrow
\begin{pmatrix}
-34 & 15 & 3\\161 & -71& 2
\end{pmatrix}
\rightarrow
\begin{pmatrix}
-195 & 86 & \color{red}{1}\\161 & -71& 2
\end{pmatrix}$

realnumber

搬个板凳坐好，$9x+4y=6$,打算y=0,1,2,3,..,8去尝试.或注意到(9,6)=3
那么y=0,3,6去尝试.
第2个不晓得怎么办了.

abababa

回复 1# isee
就用辗转相除法吧，像下面这样：
243,551
243,551=243*2+65
243,65
243=65*3+48,65
48,65
48,65=48+17
48,17
48=17*2+14,17
14,17
14,17=14+3
14,3
14=3*4+2,3
2,3
2,3=2+1
2,1

然后倒推回去，上面最后一步是用2除3，商1余1
1=3-2*1=3-(14-3*4)=(17-14)-(14-(17-14)*4)
=(17-(48-17*2))-((48-17*2)-(17-(48-17*2))*4)
=((65-48)-(48-(65-48)*2))-((48-(65-48)*2)-((65-48)-(48-(65-48)*2))*4)
=((65-(243-65*3))-((243-65*3)-(65-(243-65*3))*2))-(((243-65*3)-(65-(243-65*3))*2)-((65-(243-65*3))-((243-65*3)-(65-(243-65*3))*2))*4)
=(((551-243*2)-(243-(551-243*2)*3))-((243-(551-243*2)*3)-((551-243*2)-(243-(551-243*2)*3))*2))-(((243-(551-243*2)*3)-((551-243*2)-(243-(551-243*2)*3))*2)-(((551-243*2)-(243-(551-243*2)*3))-((243-(551-243*2)*3)-((551-243*2)-(243-(551-243*2)*3))*2))*4)
=(((x-y*2)-(y-(x-y*2)*3))-((y-(x-y*2)*3)-((x-y*2)-(y-(x-y*2)*3))*2))-(((y-(x-y*2)*3)-((x-y*2)-(y-(x-y*2)*3))*2)-(((x-y*2)-(y-(x-y*2)*3))-((y-(x-y*2)*3)-((x-y*2)-(y-(x-y*2)*3))*2))*4)
=86x-195y
其中x代表551，y代表243

isee

回复 2# realnumber

数据比较小的时候，就是猜，或者叫观察法。



回复 3# abababa

结果完全正确.


的确如此，二元一次不定方程一组整数解的方法，就是，辗转相除！

虽思维清晰，实用，可行，可略微繁琐。

事实上，就是每一步都把余数“换”掉，第一步都先得化简话，看上去，式子就不会那么长了。如 陈景润 的过程：

abababa

回复 4# isee

要是把那个关系式正着写过来，就是
$\begin{cases}
c_0=1\\
c_1=q_1\\
c_k=q_k\cdot c_{k-1}+c_{k-2}
\end{cases}$
其中$q_k$表示每次辗转相除得到的商，令$n$表示辗转相除过程中非零余数的个数，最后有一个解就是$t=(-1)^nc_n$，在本题中$q_k$是$2,3,1,2,1,4,1$，并且$n=7$，然后递推出来：
$c_0=1$
$c_1=q_1=2$
$c_2=q_2\cdot c_1+c_0=7$
$c_3=q_3\cdot c_2+c_1=9$
$c_4=q_4\cdot c_3+c_2=25$
$c_5=q_5\cdot c_4+c_3=34$
$c_6=q_6\cdot c_5+c_4=161$
$c_7=q_7\cdot c_6+c_5=195$
最后就是$x=(-1)^{n} \cdot c_7=-195$，代入就能求出$y$。

isee

回复  isee

要是把那个关系式正着写过来，就是
$\begin{cases}
c_0=1\\
c_1=q_1\\
c_k=q_k\cdot c_{k-1}+ ...
abababa 发表于 2016-5-27 13:30

吔~抛砖引到玉了~~~

abababa

回复 6# isee
好像是叫大衍求一术吧，很早之前网友以前教过我，是算那个三三数之剩几的题时学到的。

isee

回复  isee
好像是叫大衍求一术吧，很早之前网友以前教过我，是算那个三三数之剩几的题时学到的。 ...
abababa 发表于 2016-5-27 13:47

    是这样！所以，标题中 加了 科普

tommywong

$
\begin{pmatrix}
551 & 243\\1 & 0\\0 & 1
\end{pmatrix}
\rightarrow
\begin{pmatrix}
65 & 243\\1 & 0\\-2 & 1
\end{pmatrix}
\rightarrow
\begin{pmatrix}
65 & 48\\1 & -3\\-2 & 7
\end{pmatrix}
\rightarrow
\begin{pmatrix}
17 & 48\\4 & -3\\-9 & 7
\end{pmatrix}
$
$
\rightarrow
\begin{pmatrix}
17 & 14\\4 & -11\\-9 & 25
\end{pmatrix}
\rightarrow
\begin{pmatrix}
3 & 14\\15 & -11\\-34 & 25
\end{pmatrix}
\rightarrow
\begin{pmatrix}
3 & 2\\15 & -71\\-34 & 161
\end{pmatrix}
\rightarrow
\begin{pmatrix}
1 & 2\\86 & -71\\-195 & 161
\end{pmatrix}
$

http://www.fungarwai.icoc.cc/nd.jsp?id=16&_np=2_318

isee

回复 9# tommywong


    转置了下，放顶楼了，THX。