第六章:线性方程与最大公因数(1)
线性方程定理
形如ax+by的最小正整数等于gcd(a,b)
我们利用欧几里得算法来构造出适当的x与y,换句话说,将描述求方程ax + by= gcd(a,b)整数解x与y的方法。由于每个数ax+by被gcd(a,b)整除,ax + by的最小正整数值恰好是gcd(a,b)
用欧几里得算法来解方程ax+by=gcd(a,b)
例如:试解22x+60y=gcd(22,60)
第一步,应用欧几里得算法计算最大公因数,我们求得
60 = 2·22 +16 22 = 1·16 +6 16=2·6+4 6=1·4+2 4=2·2+0
这表明gcd(22,60)=2,这是一个无需求助欧几里得算法的显而易见的事实。然而,用欧几里得算法计算很重要,因为我们利用中间商和余数来解方程。首先,将第一个等式改写成
16=a-2b,其中,a=60,b=22
下面,用这个值替换第二个等式中的16,得
b=1·16+6=1·(a-2b)+6
重新整理这个等式把6移到一边,得
6=b-(a-2b)=-a+3b
现将值16与6代入下一个等式16=2·6+4
a-2b=16=2·6+4=2(-a+3b)+4
移项得
4=(a-2b)-2(-a+3b)=3a-8b
最后,使用等式6=1·4+2得
-a+3b=6=1·4+2=1·(3a-8b)+2
重排这个等式得所希望的解
-4a+11b=2
本作品采用《CC 协议》,转载必须注明作者和本文链接