轉：
http://www.mscenter.edu.cn/blog/jeffrey/articles/5994.htmlhttp://hi.baidu.com/xknuth/blog/item/491bf9198e26227adab4bded.htmlhttp://www.faq-it.org/archives/structure/0f0aeab192b1e0bdbd84d19d4ab80a28.php有等式ax+by=c,已知a、b、c,求x和y。 ?(a、b、c、x、y都是整數) ?
uml_practice ?
--------------------------------------------------------------- ?
?
解不定方程ax ?+ ?by ?= ?n的步驟如下: ?
?
(1)計算gcd(a, ?b). ?若gcd(a, ?b)不能整除n，則方程無整數解；否則，在方程的兩邊同除以gcd(a, ?b)，得到新的不定方程a'x ?+ ?b'y ?= ?n'，此時gcd(a', ?b') ?= ?1 ?
?
(2)求出不定方程a'x ?+ ?b'y ?= ?1的一組整數解x0, ?y0，則n'x0，n'y0是方程a'x ?+ ?b'y ?= ?n'的一組整數解。 ?
?
(3)根據&@^%W#&定理，可得方程a'x ?+ ?b'y ?= ?n'的所有整數解為： ?
x ?= ?n'x0 ?+ ?b't ?
y ?= ?n'y0 ?- ?a't ?
(t為整數) ?
這也就是方程ax ?+ ?by ?= ?n的所有整數解 ?
?
利用擴展的歐幾里德算法，計算(a, ?b)和滿足d ?= ?(a, ?b) ?= ?ax0 ?+ ?by0的x0和y0，也就是求出了滿足a'x0 ?+ ?b'y0 ?= ?1的一組整數解。因此可得： ?
x ?= ?n/d ?* ?x0 ?+ ?b/d ?* ?t ?
y ?= ?n/d ?* ?y0 ?- ?a/d ?* ?t ?
(t是整數)??