在网上看到的问题，一时找不到原理在哪，大家看看！

ilikenba

解释一下这个的原理，用欧几里德算法求二元一次方程的最小整数解：
  E; V! z' n' C: B11x-49y=1，求x
（a） 11 x - 49 y = 1    49%11=5 ->
( n$ N! K0 p6 n" |$ y( |（b） 11 x -  5 y = 1    11%5 =1 ->
（c）    x -  5 y = 1
令y=0 代入（c）得x=1
令x=1 代入（b）得y=2
$ W$ K4 \9 d) M, R/ K' W( w令y=2 代入（a）得x=9

wqysk07250731

切记非负的条件

fup

有道理，是这样的

wslzlf2008

这个不就是辗转相除的最简单的一个例子！！

风雨同行

至于找通解的方法

大家想想线性方程组的通解是怎么找的就知道了

只不过这里的这个“线性方程组”只有一个方程罢了

风雨同行

以下是引用ilikenba在2004-6-15 22:11:48的发言： 解释一下这个的原理，用欧几里德算法求二元一次方程的最小整数解： ( q/ p) C: G( h- w d11x-49y=1，求x 3 P* _, a* X+ ` S5 H（a） 11 x - 49 y = 1 49%11=5 -> （b） 11 x - 5 y = 1 11%5 =1 -> 7 ?3 A- N# m s# n8 A& |（c） x - 5 y = 1 8 Z; Y# @1 k; n, H8 r9 R令y=0 代入（c）得x=1 令x=1 代入（b）得y=2 ) p4 F: M( J1 D9 F( Z令y=2 代入（a）得x=9

+ f3 i! H9 ?, E& i9 r

加个非负条件吧 # q) S) d3 Y2 h9 ?

这个解法倒着看就不难理解了

这个问题实际上可以先找通解，就很容易得到最小非负解了 " }- b, T7 `* A; L7 S) Y

11x－49y＝1的通解是 " O! [' j7 c: R) @$ w Z! @ l

x＝9＋49t，y＝2＋11t （t是整数） # x8 j) J5 s- D! X& K& p* q

取t＝0得到最小非负解