輾轉相除法求不定方程的通解
來源:魅力女性吧 1.64W
輾轉相除法應用的前提是(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
這樣去解。