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

ilikenba

解释一下这个的原理，用欧几里德算法求二元一次方程的最小整数解：
( X; l# l' _; s: A* X) l5 D11x-49y=1，求x
2 m9 ~- O7 K, g1 y9 t# b  X1 y（a） 11 x - 49 y = 1    49%11=5 ->
（b） 11 x -  5 y = 1    11%5 =1 ->
8 u3 Z+ a- J4 `7 P（c）    x -  5 y = 1
令y=0 代入（c）得x=1
令x=1 代入（b）得y=2
1 a( Q2 y' ~2 L  H. `令y=2 代入（a）得x=9

风雨同行

以下是引用ilikenba在2004-6-15 22:11:48的发言： - j% y! K% ]3 z9 a$ I解释一下这个的原理，用欧几里德算法求二元一次方程的最小整数解： ) |' z1 c: D3 E: Q( h11x-49y=1，求x ( n6 e4 _: \. B' n（a） 11 x - 49 y = 1 49%11=5 -> - B$ v `, b8 Q* L0 Q（b） 11 x - 5 y = 1 11%5 =1 -> （c） x - 5 y = 1 令y=0 代入（c）得x=1 令x=1 代入（b）得y=2 * y6 Q5 ?: }6 j0 w0 p( o令y=2 代入（a）得x=9

7 X8 }' a5 i& T, m0 F, b, u- z

加个非负条件吧 0 r4 y6 B a$ m/ D8 P

这个解法倒着看就不难理解了 9 d) i2 I5 Y+ X

这个问题实际上可以先找通解，就很容易得到最小非负解了 6 x/ `! m- M/ e& B- Y

11x－49y＝1的通解是 ' N& ~6 d2 D% [ L% e( F, C% K O

x＝9＋49t，y＝2＋11t （t是整数）

取t＝0得到最小非负解

风雨同行

至于找通解的方法

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

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

wslzlf2008

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

fup

有道理，是这样的

wqysk07250731

切记非负的条件