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

ilikenba

解释一下这个的原理，用欧几里德算法求二元一次方程的最小整数解：
11x-49y=1，求x
（a） 11 x - 49 y = 1    49%11=5 ->
（b） 11 x -  5 y = 1    11%5 =1 ->
: A' @( [" J$ N" A" N（c）    x -  5 y = 1
令y=0 代入（c）得x=1
% @' w  s- B/ S7 g3 S" B令x=1 代入（b）得y=2
1 v1 {' ~  R$ v3 ?1 |3 v( ~% e! U令y=2 代入（a）得x=9

wqysk07250731

切记非负的条件

fup

有道理，是这样的

wslzlf2008

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

风雨同行

至于找通解的方法

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

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

风雨同行

以下是引用ilikenba在2004-6-15 22:11:48的发言： 解释一下这个的原理，用欧几里德算法求二元一次方程的最小整数解： / C8 I2 @# Q: [. W11x-49y=1，求x ! ]+ t4 {* `" U/ f0 l8 T7 a* B（a） 11 x - 49 y = 1 49%11=5 -> （b） 11 x - 5 y = 1 11%5 =1 -> 2 L/ c6 ~, ?2 m9 T5 K! l（c） x - 5 y = 1 $ o) b N( F% Z- C; c; J. V ]令y=0 代入（c）得x=1 令x=1 代入（b）得y=2 令y=2 代入（a）得x=9 1 U* @5 z0 N4 j( r

加个非负条件吧 + ] }& j( H5 b( _

这个解法倒着看就不难理解了 + X8 U3 N' r- J2 A: p9 n

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

11x－49y＝1的通解是 3 K: a( D8 `; l: y

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

取t＝0得到最小非负解