輾轉相除法求不定方程的通解

輾轉相除法應用的前提是（x，y）＝z

所以z整除mx＋ny （m，n∈Z）

x/y＝a…b 既x—ay＝b

因為z整除x—ay

所以z整除b

也就是説照兩個特別大的數的最小公約數就互除就可以了，除到兩個非常小的數找它們的最小公約數，和兩個大數是一樣的，它們互質兩個大數也互質。

更相減損法也是一樣的，只不過更特殊一點，就是上頭的m，n分別都是1的情況，但是原理是一樣的。

舉個例子。

542x＋245y＝1

（542，245）＝（52，245）＝（52，37）＝（15，37）＝（15，7）＝1

反過來寫1＝15-2*7

=15-2*（37-2*15）=15*5-2*37

=5*（52-37）-2*37

=5*52-7*（245-4*52）=33*52-7*245

=33*（542-2*245）-7*245

=33*542-73*245

得到一組解

33和—73

所有解就是

x＝33＋245t

y＝—73—542t

不過解ax＋by＝c有整數解重要條件是（a

b）整除c，不然還得約。

比如143x—77y＝187

就等價於13x—7y＝17

這樣去解。