最大公约数原理(转)

源地址:http://blog.sina.com.cn/s/blog_67e046d10100reqb.html
1、最大公约数原理
设d = gcd(A1, A2, …, An),则必然可以找到或正或负的整数Xi, 使
A1X1 + A2X2 + … + AnXn = d
证明:回想一下多个数求gcd的方法,可知gcd(A1, A2, …, An) = gcd(A1, gcd(A2, A3, …, An))。对序列(A1, A2, …, An)进行如下操作:从i = 1开始,设j = i + 1,若gcd(Ai, Aj) = k > 1,则将Aj修改为k,注意k是可以由Ai*p + Aj*q得到的。操作一直进行到最后,若全部修改完后,左边必为gcd(A1, A2, …, An),而右边必可写成A1X1 + A2X2 + … + AnXn,得证!
2、A1X1 + A2X2 + … + AnXn = 1有解的充要条件是d = gcd(A1, A2, …, An) = 1
证明:
①、方程左边必整除d,故方程右边必整除d,因而方程有解 => d = 1。
②、若d = 1,则由最大公约数原理可知,必存在一系列或正或负整数Xi,使A1X1 + A2X2 + … + AnXn = d = 1。
统合①、②,命题得证!

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>