第一章 数的整除性 第四节 最大公因数1

初 等 数 论 （4）

（第一章 数的整除性 第四节 最大公因数（1）） 定义1 整数a1，a2，?，ak的公共因数称为a1，a2，?，ak的公因数。不全为零的整数a1，a2，?，ak的公因数中最大的一个叫做a1，a2，?，ak的最大公因数，记为（a1，a2，?，ak）。

由于每个非零整数的因数的个数是有限的，所以最大公因数是存在的，并且是正整数。

如果（a1，a2，?，ak） = 1，则称a1，a2，?，ak是互质的； 如果 （ai , a j） = 1，1 ? i ? k，1 ? j ? k， i ? j，则称a1，a2，?，ak是两两互质的。

显然，由a1，a2，?，ak两两互质可以推出（a1，a2，?，ak） = 1，反之则不然，例如（2，6，15） = 1，但（2，6）= 2。

定理1 下面的等式成立：

（ⅰ） （a1，a2，?，ak） =（|a1|， |a2|，?，|ak|）； （ⅱ） （a，1） = 1，（a，0） = |a|，（a，a） = |a|； （ⅲ） （a，b） = （b，a）；

（ⅳ） 若p是质数，a是整数，则（p，a） = 1或p?a； （ⅴ） 若a = bq ? r，则（a，b） =（b，r）。

证明（ⅰ） 我们先证明a1，a2，?，ak与|a1|， |a2|，?，|ak|的公因数相同。设d是a1，a2，?，ak 任一公因数，由定义d? ai ，i = 1，2，……，n。 因而d?| ai | ，i = 1，2，……，n。故d是|a1|， |a2|，?，|ak|的一个公因数,同样的方法可证|a1|， |a2|，?，|ak|的任一个公因数都是a1，a2，?，ak的一个公因数.即a1，a2，?，ak与|a1|， |a2|，?，|ak|的公因数相同。

由此可直接得（a1，a2，?，ak） =（|a1|， |a2|，?，|ak|）；（ⅱ）、（ⅲ）、（ⅳ）显然。

（ⅴ）如果d?a，d?b，则有d?r = a ? bq，反之，若d?b，d?r，则d?a = bq ? r。因此a与b的全体公因数的集合就是b与r的全体公因数的集合，这两个集合中的最大正数当然相等，即（a，b） = （b，r）。由定理1可知，在讨论（a1，a2，?，ak）时，不妨假设a1，a2，

1

?，ak是正整数，以后我们就维持这一假设。

例1 求 （27，15）

解 27 = 1×15 ? 12 （27，15）=（15，12）

15 =1×12 ? 3 （15，12）=（12，3） 12 = 4×3 （12，3）=（3，0）

其中a = 27，b = 15， q1 = 1，r1 = 12，q2 = 1，r2 = 3，q3 = 4。 以上步骤可以写为下面的式子

271512121141512 3例2 大厦公司销售某种货物，去年总收入为36963元，今年某种货物的售价（单价）不变，总收入59570元。如果单价（以元为单位）是大于1的整数，问今年与去年各售这种货物多少件？

解 单价是36963与59570的公约数，由辗转相除得 （33963，59570）=37

因为37只有约数1与本身，所以单价为37元。

33963226071435682516105429218131665148148111112152459570369632260714356825161052146181333329637

21n?4例3 证明：若n是正整数，则是既约分数。

14n?3证明 由定理1得到

2

（21n ? 4，14n ? 3） = （7n ? 1，14n ? 3）

= （7n ? 1, 1）= 1。

定理2 设a1, a2, ?, ak?Z，记

A = { y?y = a1x1 ? ? ? akxk，xi?Z，? ? i ? k }。

如果y0是集合A中最小的正数，则y0 = （a1，a2,，?，ak）。

证明 设d是a1，a2，?，ak的一个公因数，则d?y0= a1x1 ? ? ? akxk，所以d ? y0。另一方面，由第二节例1知，y0也是a1，a2，?，ak的公因数。因此y0是a1，a2，?，ak的公因数中的最大者，即y0 = （a1，a2，?，ak）。证毕。

例如 a1=18， a2=12， a3=10

则18 x1+12 x2+10 x3中最小的正数是2。 （此时x1=1， x2 = 2， x3= ? 4）

推论1 设d是a1，a2，?，ak的一个公因数，则 d?（a1，a2，?，ak）。

这个推论对最大公因数的性质做了更深的刻划：最大公因数不但是公因数中的最大的，而且是所有公因数的倍数。

推论2 （ma1，ma2，?，mak） = |m|（a1，a2，?，ak）。 证明 记A = { y?y = a1x1 ? ? ? akxk，xi?Z，? ? i ? k }。 中最小的正数是y0，则

A/= { y?y = m(a1x1 ? ? ? akxk)， xi?Z，? ? i ? k }。

中最小的正数是|m|y0，由定理2可得

（ma1，ma2，?，mak） = |m|（a1，a2，?，ak）。 推论3 记? =（a1，a2，?，ak），则

(aa1a2，，??k)?1

???特别地， (ab，)?1。

(a,b)(a,b)定理3 （a1，a2，?，ak） = 1的充要条件是存在整数x1, x2, ?,

3

xk，使得

a1x1 ? a2x2 ? ? ? akxk = 1。 （1）

证明 必要性 如果（a1，a2，?，ak） = 1，由定理2知y0 =1，所以，存在整数x1，x2，?，xk，使得

a1x1 ? a2x2 ? ? ? akxk = 1。

充分性 若（1）式成立，如果（a1，a2，?，ak）= d > 1，那么由d?ai（1 ? i ? k）推出d?a1x1 ? a2x2 ? ? ? akxk = 1，这是不可能的。所以有（a1，a2，?，ak） = 1。

练 习 题

1．求（5767，4453）

初 等 数 论 （5）

（第一章 数的整除性 第五节 最大公因数（2）） 裴蜀恒等式：

我们将定理2、定理3中的k取2，再考虑（a1，a2）=d的一般情形即得

定理2 设a1，a2?Z，记

A = { y?y = a1x1 +a2x2，x1，x2?Z，}。

如果y0是集合A中最小的正数，则y0 =（a1，a2）。

定理3 （a1，a2）= d,则存在整数x1, x2，使得 a1x1 ? a2x2 =d。

证明 如果（a1，a2）= d，由定理2知y0= d，所以，存在整数x1, x2, 使得

a1x1 ? a2x2 = d。 这就证明了课本1.2.3的裴蜀恒等式。 我们通过具体的例子看如何求x1，x2。 例如 （213，60）=3，求x1，x2使 213 x1+60 x2=3 213=3×60+33

4