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

ilikenba

解释一下这个的原理，用欧几里德算法求二元一次方程的最小整数解：
11x-49y=1，求x
" P+ G$ ?: |6 f( D  G（a） 11 x - 49 y = 1    49%11=5 ->
2 C" G, M8 G6 e( q. a（b） 11 x -  5 y = 1    11%5 =1 ->
5 E- R1 H) ~( Y（c）    x -  5 y = 1
; }( k. I. [! a/ K令y=0 代入（c）得x=1
, J  ~6 {2 W5 Q0 r) N7 m令x=1 代入（b）得y=2
令y=2 代入（a）得x=9

wqysk07250731

切记非负的条件

fup

有道理，是这样的

wslzlf2008

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

风雨同行

至于找通解的方法

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

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

风雨同行

以下是引用ilikenba在2004-6-15 22:11:48的发言： ( T Q4 T# `! g" V1 {9 V2 B U解释一下这个的原理，用欧几里德算法求二元一次方程的最小整数解： ; r5 r9 e/ d. S3 ~& }, n11x-49y=1，求x / ^9 Z! P: X. C' ?（a） 11 x - 49 y = 1 49%11=5 -> （b） 11 x - 5 y = 1 11%5 =1 -> 6 M% c& W8 ?9 U7 s; e# g A（c） x - 5 y = 1 7 Q( e V ~- F2 l) K令y=0 代入（c）得x=1 0 n! D& F3 a9 E! }: |* g! Z令x=1 代入（b）得y=2 8 b2 a" H5 W+ ~. I令y=2 代入（a）得x=9 7 b' U" v, z/ u$ T8 l% H- b

4 {( j6 Y. n1 j0 K9 E

加个非负条件吧

这个解法倒着看就不难理解了 5 L8 ^ U& A6 x

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

11x－49y＝1的通解是 / M- z o5 Y: a: `

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

取t＝0得到最小非负解