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

ilikenba

解释一下这个的原理，用欧几里德算法求二元一次方程的最小整数解：
11x-49y=1，求x
（a） 11 x - 49 y = 1    49%11=5 ->
; D5 D/ o, W/ l: n4 t1 y（b） 11 x -  5 y = 1    11%5 =1 ->
! i1 x  b# W) D: S, V8 n7 U（c）    x -  5 y = 1
令y=0 代入（c）得x=1
: g- ~0 A7 ]/ N- ]: U令x=1 代入（b）得y=2
令y=2 代入（a）得x=9

风雨同行

以下是引用ilikenba在2004-6-15 22:11:48的发言： 9 m5 a: _; h' ?1 p, Y: F: i解释一下这个的原理，用欧几里德算法求二元一次方程的最小整数解： 11x-49y=1，求x （a） 11 x - 49 y = 1 49%11=5 -> （b） 11 x - 5 y = 1 11%5 =1 -> （c） x - 5 y = 1 * l0 y1 c- v | f+ o1 Q3 J; z0 x令y=0 代入（c）得x=1 % y0 m) M U: [; X* [0 p9 F. J令x=1 代入（b）得y=2 3 E" i; L& L/ m/ f令y=2 代入（a）得x=9 1 E$ H) S0 B0 K+ f1 s9 c1 |

8 t/ C1 h, {- H( A( x/ J' x+ m

加个非负条件吧 7 `& L- v* k6 G3 u0 `

这个解法倒着看就不难理解了 0 Z( [6 _3 p; W

这个问题实际上可以先找通解，就很容易得到最小非负解了

11x－49y＝1的通解是 * C4 f- `& u ~7 j) P8 `

x＝9＋49t，y＝2＋11t （t是整数） 5 k9 R" g! S0 A l

取t＝0得到最小非负解

风雨同行

至于找通解的方法

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

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

wslzlf2008

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

fup

有道理，是这样的

wqysk07250731

切记非负的条件