数的整除性最大公因数

1、初 等 数 论 （4）（第一章 数的整除性 第四节 最大公因数（1）定义1 整数a1，a2，L，ak的公共因数称为a1，a2，L，ak的公因数。不全为零的整数a1，a2，L，ak的公因数中最大的一个叫做a1，a2，L，ak的最大公因数，记为（a1，a2，L，ak）。由于每个非零整数的因数的个数是有限的，所以最大公因数是存在的，并且是正整数。如果（a1，a2，L，ak） = 1，则称a1，a2，L，ak是互质的；如果 （ai , a j） = 1，1 £ i £ k，1 £ j £ k， i ¹ j，则称a1，a2，L，ak是两两互质的。显然，由

2、a1，a2，L，ak两两互质可以推出（a1，a2，L，ak） = 1，反之则不然，例如（2，6，15） = 1，但（2，6）= 2。定理1 下面的等式成立：（） （a1，a2，L，ak） =（|a1|， |a2|，L，|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，L，ak与|a1|， |a2|，L，|ak|的公因数相同。设d是a1，a2，L，ak 任一公因数，由定义

3、d½ ai ，i = 1，2，n。 因而d½| ai | ，i = 1，2，n。故d是|a1|， |a2|，L，|ak|的一个公因数,同样的方法可证|a1|， |a2|，L，|ak|的任一个公因数都是a1，a2，L，ak的一个公因数.即a1，a2，L，ak与|a1|， |a2|，L，|ak|的公因数相同。由此可直接得（a1，a2，L，ak） =（|a1|， |a2|，L，|ak|）；（）、（）、（）显然。（）如果d½a，d½b，则有d½r = a - bq，反之，若d½b，d½r，则d½a = bq + r。因此a

4、与b的全体公因数的集合就是b与r的全体公因数的集合，这两个集合中的最大正数当然相等，即（a，b） = （b，r）。由定理1可知，在讨论（a1，a2，L，ak）时，不妨假设a1，a2，L，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。以上步骤可以写为下面的式子例2 大厦公司销售某种货物，去

5、年总收入为36963元，今年某种货物的售价（单价）不变，总收入59570元。如果单价（以元为单位）是大于1的整数，问今年与去年各售这种货物多少件？解 单价是36963与59570的公约数，由辗转相除得（33963，59570）=37因为37只有约数1与本身，所以单价为37元。例3 证明：若n是正整数，则是既约分数。证明 由定理1得到（21n + 4，14n + 3） = （7n + 1，14n + 3） = （7n + 1, 1）= 1。定理2 设a1, a2, L, akÎZ，记A = y½y = a1x1 + L + akxk，xiÎZ，1 £ i

6、£ k 。如果y0是集合A中最小的正数，则y0 = （a1，a2,，L，ak）。证明 设d是a1，a2，L，ak的一个公因数，则d½y0= a1x1 + L + akxk，所以d £ y0。另一方面，由第二节例1知，y0也是a1，a2，L，ak的公因数。因此y0是a1，a2，L，ak的公因数中的最大者，即y0 = （a1，a2，L，ak）。证毕。例如 a1=18， a2=12， a3=10则18 x1+12 x2+10 x3中最小的正数是2。（此时x1=1， x2 = 2， x3= - 4）推论1 设d是a1，a2，L，ak的一个公因数，则d½（a1，a

7、2，L，ak）。这个推论对最大公因数的性质做了更深的刻划：最大公因数不但是公因数中的最大的，而且是所有公因数的倍数。推论2 （ma1，ma2，L，mak） = |m|（a1，a2，L，ak）。证明 记A = y½y = a1x1 + L + akxk，xiÎZ，1 £ i £ k 。中最小的正数是y0，则= y½y = m(a1x1 + L + akxk)， xiÎZ，1 £ i £ k 。中最小的正数是|m|y0，由定理2可得 （ma1，ma2，L，mak） = |m|（a1，a2，L，ak）。推论3 记d =（

8、a1，a2，L，ak），则特别地， 。定理3 （a1，a2，L，ak） = 1的充要条件是存在整数x1, x2, L, xk，使得a1x1 + a2x2 + L + akxk = 1。 （1） 证明 必要性 如果（a1，a2，L，ak） = 1，由定理2知y0 =1，所以，存在整数x1，x2，L，xk，使得a1x1 + a2x2 + L + akxk = 1。 充分性 若（1）式成立，如果（a1，a2，L，ak）= d > 1，那么由d½ai（1 £ i £ k）推出d½a1x1 + a2x2 + L + akxk = 1，这是不可能的。所以有（a

9、1，a2，L，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

10、。 这就证明了课本的裴蜀恒等式。我们通过具体的例子看如何求x1，x2。例如 （213，60）=3，求x1，x2使213 x1+60 x2=3213=3×60+3360=1×33+2733=1×27+627=4×6+33=274×6=274×（3327）=5×274×33=5×（6033）4×33 =5×609×33=5×609×（2133×60）=32×609×213即x1= 9，x2=32记x1= u， x2= v，则3 =

11、 213×u + 60×v。例1 两个容器，一个为27L，另一个为15L，如何利用它们从一桶油中倒出6L油来？解 由例2可知（27，15）=3，且27=1×15+1215=1×12+3从而3=15-1×12=15-1×（27-1×15）即3=2×15- 27 于是6 = 4×15- 2× 27例2 已知一个角的度数为，其中n是不能被3整除的正整数，证明这个角可以用圆规和直尺三等分。解 因为n与3互质，因此有1 = un - 3v其中u、v均为正整数，从而这表明先作角等于（60º角可以用

12、尺规作出），然后再减去，（是已知角），就产生了的角。具体给出n即可求u、v。例3 已知ad - bc = 1，证明：是既约分数。证明 由于a×( c+d ) - c×( a+b ) = ad- bc = 1于是c + d与a + b互质。例如3×5-2×7=1，则3+2与5+7互质。例7 证明：对于每个自然数n，为既约分数。证明 由于（14n + 3）-2(7n + 1)=1所以14n + 3与7n + 1互质，结论成立。例8 证明：存在一个有理数，其中0 < d <100，能使 对于k=1，2，99均成立，证明 首先注意到73与100互质，

13、因此有c、 d存在，使73 d - 100 c = 1我们证明对于任一k1，2，99 ，都成立。事实上，设，由于k < 100，所以 0 < <得<由 得< n + 1 = 所以<£ = n + 1， 说明 因为，且k、c、d均为正整数，所以£。从而 。练 习 题用辗转相除法求（125，85），以及u、v，使得125x + 85y = （125，85）。初 等 数 论 （6）（第一章 数的整除性 第六节 最大公因数（3）定理4 对于任意的整数a，b，c，下面的结论成立：（） 由b½ac及（a，b）= 1可以推出b½c；

14、例如 5½22×10，（22，5）=1可推出5½10。证明 （） 若（a，b）= 1，由定理2，存在整数x与y，使得ax + by = 1。因此acx + bcy = c。 （1）由上式及b½ac得到b½c。 （） 由b½c，a½c及（a，b） = 1可以推出ab½c。例如 3½60，5½60及（3，5） = 1可以推出3×5½60。证明 （） 若（a，b） = 1，则存在整数x，y使得ax + by =1成立，即acx + bcy = c （2）成立。由b½c与a

15、½c得到ab½ac，ab½bc，再由（2）式得到ab½c。推论1 若p是质数，则下述结论成立：（） p½ab Þ p½a或p½b；即p½ab，若p½a，则结论成立，若p不能整除a，（p，a）=1，由定理4（）知p½b。例如 7½35×51，7½35×49（） p½a2 Þ p½a。推论2 若 （a，b） = 1，则（a，bc）=（a，c）。证明 设d是a与bc的一个公因数，则d½a，d½bc，由a

16、cx + bcy = c 得到，d½c, 即d是a与c的公因数。另一方面，若d是a与c的公因数，则它也是a与bc的公因数。因此，a与c的公因数的集合，就是a与bc的公因数的集合，所以 （a，bc）=（a，c）。证毕。定理5 对于任意的n个整数a1, a2, L, an，记（a1，a2） = d2， （d2，a3）= d3， L，（dn - 2，an - 1）= dn - 1，（dn - 1，an） = dn， 则dn =（a1，a2，L，an）。我们以3个整数a1，a2，a3 为例,记（a1，a2） = d2， （d2，a3） = d3，则d3 =（a1，a2，a3）。证明 先证明d

17、3是a1，a2，a3的一个公因数，我们有d3 =（d2，a3） Þ d3½a3，d3½d2，d2 =（a1，a2） Þ d2½a1，d2½a2Þ d3½a1，d3½a2即d3是a1，a2，a3的一个公因数。再证明对于a1，a2，a3的任何公因数d，有d½d3d½a1，d½a2 Þ d½d2，（a1，a2）= d2d½d2，d½a3 Þ d½d3，因此d3是a1，a2，a3 的公因数中的最大者，即d3 =（a1，a2，

18、a3 ）。例1 求（353430，530145，165186）解 （353430，530145，165186）=（353430，530145），165186）=（353430，176715），165186）=（0，176715），165186）=（176715，165186）=（11529，165186）=（11529，3780）=（189，3780）= 189（353430，530145，165186）= 189例2 证明：121n2 + 2n + 12，nÎZ。证明 由于121 = 112，n2 + 2n + 12 =（n + 1）2 + 11，所以，若112½（n +

19、 1）2 + 11， （3）11½（n + 1） 2 + 11则11½（n + 1） 2，因此，由定理4的推论1得到 11½n + 1，112½（n + 1）2。再由（3）式得到 112½11，这是不可能的。所以（3）式不能成立。例3 设a，b是整数，且9½a2 + ab + b2， （4）则3½（a，b）。证明 由（4）式得到9½（a - b）2 + 3ab Þ 3½（a - b） 2 + 3abÞ 3½（a - b）2 Þ 3½a - bÞ

20、9½（a- b） 2。再由（4）式得到9½3ab Þ 3½ab。 因此，由定理4的推论1，得到3½a或3½b。若3½a，由3½a- b得到3½b；若3½b，由上式也得到3½a。因此，总有3½a且3½b。所以3½（a，b）。例4 设a和b是正整数，b > 2，则2b - 12a + 1。证明 （） 若a < b，且2b - 1½2a + 1。 （5） 成立，则2b - 1 £ 2a + 1 Þ 2b - 2a

21、63; 2 Þ 2a（2b - a - 1）£ 2，于是a = 1，b - a = 1，即b = 2，这是不可能的，所以（5）式不成立。（） 若a = b，且（5）式成立，则由（5）式得到2a - 1½（2a - 1） + 2 Þ 2a - 1½2 Þ 2a - 1 £ 2 Þ 2a £ 3，于是b = a = 1，这是不可能的，所以（5）式不成立。（） 若a > b，记a = kb + r，0 £ r < b，其中k是正整数，此时2kb - 1 = （2b - 1）（2(k - 1

22、)b + 2(k - 2)b + L+ 1） = （2b - 1）Q，其中Q是整数。所以2a + 1= 2kb + r + 1 = 2r（2kb - 1 + 1） + 1= 2r（2b - 1）Q + 1 + 1 = （2b - 1）Q ¢ +（2r + 1），其中Q¢是整数。因此2b - 1½2a + 1 Þ 2b - 1½2r + 1，在（）中已经证明这是不可能的，所以（5）式不能成立。综上证得2b - 12a + 1。 练 习 题 1 设x，yÎZ，17½（2x + 3y），证明：17½（9x + 5y）。

23、2 设a，b，cÎN，c无平方因子，a2½b2c，证明：a½b。 初 等 数 论 （7）（第一章 数的整除性 第七节 最小公倍数）内容提要：最小公倍数的概念、性质，求最小公倍数的方法。定义1 整数a1，a2，L，ak的公共倍数称为a1，a2，L，ak的公倍数。 a1，a2，L，ak的正公倍数中的最小的一个叫做a1，a2，L，ak的最小公倍数，记为a1，a2，L，ak。定理1 下面的等式成立：（） a，1 = |a|，a，a = |a|； 例如 5，1 = 5 = |5|，-5，1 =5=|-5|（） a，b = b，a；（）和（）显然； （） a1，a2，L，ak

24、 = |a1|， |a2|， L，|ak| ；（） 证明 我们只要证明a1，a2，L, ak的公倍数集合和|a1|，|a2|，L，|ak|的公倍数集合相等就可以了。设m1是a1，a2，L，ak的公倍数，则ai½m1，可推出|ai|½m1，所以m1是|a1|，|a2|，L，|ak|的公倍数。同理若m2是|a1|，|a2|，L，|ak|的公倍数，则m2是a1，a2，L，ak的公倍数。即a1，a2，L，ak的公倍数集合与 |a1|，|a2|，L，|ak|的公倍数集合相等，所以a1，a2，L，ak = |a1|， |a2|，L，|ak| 。例如 15，-26，22 = 15，26，

25、22 =2145() 若a½b，则a，b = |b|。() 证明 显然a½|b|，b½|b|，即|b|是a，b的公倍数，又若有a½m¢，b½m¢，m¢ > 0，则|b| £ m¢，即a，b的任一正的公倍数都大于或等于|b|，故有|b|是a，b的最小公倍数，即a，b = |b|。例如 3½-15， 3，15 = 15 = |-15|由定理1中的结论（）可知，在讨论a1，a2，L，ak的最小公倍数时，不妨假定它们都是正整数。以下假定a1，a2，L，ak都是正整数。最小公倍数和最大公约

26、数之间有一个很重要的关系，即下面的定理。定理2 对任意的正整数a，b，有证明 设m是a和b的一个公倍数，那么存在整数k1，k2，使得m = ak1，m = bk2， ak1 = bk2 。 （1） （1）式两边同除以（a，b）得。由于，即互质，而整除，所以，即，其中t是某个整数。将上式代入m =ak1 = bk2 （1）式得到 （2）也就是a，b的任一公倍数m可以表示为上式；另一方面，对于任意的整数t，由（2）式所确定的m显然是a与b的公倍数，因此a与b的公倍数必是（2）式中的形式，其中t是整数。当t = 1时，得到最小公倍数。例如 （335，134） = 67推论1 两个整数的任何公倍数可以

27、被它们的最小公倍数整除。证明 由（2）式可得证。 这个推论说明：两个整数的最小公倍数不但是最小的正倍数，而且是另外的公倍数的约数。例如 15，36 =180，则15和36的正的公倍数为180，360，540等。推论2 设m，a，b是正整数，则ma, mb = ma，b。证明 由定理2 得到 例如 60，75 = 15×4，15×5 = 15×4，5 =15×20=300定理3 对于任意的n个整数a1，a2，L，an，记a1，a2 = m2，m2，a3 = m3，L，mn-2，an-1 = mn-1，mn-1，an= mn则a1，a2，L，an = mn。

28、推论 若m是整数a1，a2，L，an的公倍数，则a1，a2，L，an½m 。我们以n=4为例说明先证明m4是a1，a2，a3，a4的一个公倍数，m4= m3，a4 Þ m3½m4，a4½m4，m3=m2，a3 Þ m2½m3½m4，a4½m4，a3½m3½m4， m2 = a1，a2 Þ a1½m2½m3½m4，a2½m2½m3½m4，a4½m4，a3½m3½m4，即m4是a1，a2，a3，a4的

29、一个公倍数。另一方面，对于a1，a2，a3，a4的任何公倍数m应是a1，a2的公倍数，由定理2的推论1及a1，a2 = m2知m2½m，所以m是m2，a3的公倍数，又m2，a3 = m3，即m3是m2，a3的最小公倍数，所以m3可以整除m2，a3的公倍数m，m3½m，所以m是m3，a4的公倍数，而由m4 = m3，a4知m4½m，即m4可以整除a1，a2，a3，a4的任何公倍数m，所以m4是a1，a2，a3，a4的最小公倍数。定理4 整数a1，a2，L，an两两互质，即(ai，aj) = 1，1 £ i £ n，1 £ j £ n，i ¹ j的充要条件是a1，a2，L，an = a1a2Lan 。 这个定理我们分开叙述为：整数a1，a2，L，an两两互质，则a1，a2，L，an = a1a2Lan。例如 3，5，11，23，=3×5×11