轉(zhuǎn)：

http://www.mscenter.edu.cn/blog/jeffrey/articles/5994.html
http://hi.baidu.com/xknuth/blog/item/491bf9198e26227adab4bded.html
http://www.faq-it.org/archives/structure/0f0aeab192b1e0bdbd84d19d4ab80a28.php

有等式ax+by=c,已知a、b、c,求x和y。 ?(a、b、c、x、y都是整數(shù)) ?
uml_practice ?
--------------------------------------------------------------- ?
?
解不定方程ax ?+ ?by ?= ?n的步驟如下: ?
?
(1)計(jì)算gcd(a, ?b). ?若gcd(a, ?b)不能整除n，則方程無(wú)整數(shù)解；否則，在方程的兩邊同除以gcd(a, ?b)，得到新的不定方程a'x ?+ ?b'y ?= ?n'，此時(shí)gcd(a', ?b') ?= ?1 ?
?
(2)求出不定方程a'x ?+ ?b'y ?= ?1的一組整數(shù)解x0, ?y0，則n'x0，n'y0是方程a'x ?+ ?b'y ?= ?n'的一組整數(shù)解。 ?
?
(3)根據(jù)&@^%W#&定理，可得方程a'x ?+ ?b'y ?= ?n'的所有整數(shù)解為： ?
x ?= ?n'x0 ?+ ?b't ?
y ?= ?n'y0 ?- ?a't ?
(t為整數(shù)) ?
這也就是方程ax ?+ ?by ?= ?n的所有整數(shù)解 ?
?
利用擴(kuò)展的歐幾里德算法，計(jì)算(a, ?b)和滿足d ?= ?(a, ?b) ?= ?ax0 ?+ ?by0的x0和y0，也就是求出了滿足a'x0 ?+ ?b'y0 ?= ?1的一組整數(shù)解。因此可得： ?
x ?= ?n/d ?* ?x0 ?+ ?b/d ?* ?t ?
y ?= ?n/d ?* ?y0 ?- ?a/d ?* ?t ?
(t是整數(shù))??