輾轉相除法應用的前提是（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
這樣去解。
