第六章:线性方程与最大公因数(1)

线性方程定理

形如ax+by的最小正整数等于gcd(a,b)
我们利用欧几里得算法来构造出适当的xy,换句话说,将描述求方程ax + by= gcd(a,b)整数解xy的方法。由于每个数ax+bygcd(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

现将值166代入下一个等式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 协议》,转载必须注明作者和本文链接
Hacking
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!