最大公因数辗转相除法简介

本节建立最大公因数的一些基本事实，同时阐述求任意两整数最大公因数的最基本方法——辗转相除法.先考虑两个整数的最大公因数.

定义1.2.1　设a，b，c∈Z.若c|a，c|b.称c是a，b的公因数.若a，b不全为零，则称a，b的公因数之最大者为a，b的最大公因数.规定0与0的最大公因数为0.两整数a，b的最大公因数记为（a，b）.若（a，b）=1，则称a，b互素.由定义容易看出，两个不全为零的整数的最大公因数必为正整数.

例1.2.2　用最大公因数的定义求24和45的最大公因数.

解　容易验证，24的因数有

±1，±2，±3，±4，±6，±8，±12，±24，

而45的因数有

±1，±3，±5，±9，±15，±45.

故24和45的公因数有±1，±3，从而最大公因数是3，即（24，45）=3.解毕.

例1.2.3　设m是正奇数，n是正整数，则（2m-1，2n+1）=1.

证明　设d=（2m-1，2n+1），则存在s，t∈Z，使得2m=ds+1，2n=dt-1.于是

（ds+1）n=（dt-1）m.

注意到m是奇数，由牛顿二项式定理，存在u，v∈Z，使得

du+1=dv-1.

这表明d|2.但2m-1和2n+1均为奇数，故d=1.证毕.

下面的结论是显然的.

命题1.2.4　设a，b∈Z.则

（1）a，b与|a|，|b|有完全相同的公因数.

（2）（a，b）=（|a|，|b|）=（b，a）.

（3）（a，1）=1，（a，0）=|a|.

（4）若a|b，则（a，b）=|a|.

从上述命题1.2.4可以看出，考虑两个整数的最大公因数最终可归结为考虑两个正整数的最大公因数.下面介绍求任意两整数的最大公因数的方法.先看下面的基本事实.

命题1.2.5　设a，b，q，r∈Z且a=qb+r，则（a，b）=（b，r）.

证明　若u|a，u|b，则u|b且u|a-qb=r.反之，若u|b，u|r，则u|b且u|qb+r=a.这表明a，b与b，r的公因数完全相同，从而最大公因数相同，即（a，b）=（b，r）.证毕.

定理1.2.6（辗转相除法）设a，b∈Z，b＞0.又设

记

则以下各款成立：

（1）（a，b）=rn.

（2）对任意k=1，2，3，…，n，有

（3）对任意k=1，2，3，…，n，有

（4）n≤2log2b.

证明　　　（1）据命题1.2.4和1.2.5，有

（a，b）=（b，r1）=（r1，r2）=…=（rn-1，rn）=（rn，rn+1）=（rn，0）=rn.

（2）当k=1时，结论显然成立.设结论对k=t-1成立，即

则当k=t时，有

由归纳法原理，结论成立.

（3）当k=1时，结论显然成立.设结论对k＜t的情况成立，则有

故

由归纳法原理，结论成立.(www.xing528.com)

（4）证明留作习题.证毕.

据命题1.2.4（2）及定理1.2.6之条款（1）和（3），下述结论是显然的.

推论1.2.7　设a，b∈Z，则存在s，t∈Z使得（a，b）=as+bt.

例1.2.8　求s，t∈Z使得（2346，1081）=2346s+1081t.

解　注意到

2346=2×1081+184，1081=5×184+161，

184=1×161+23，161=7×23+0，

据定理1.2.6之证明过程，有（2346，1081）=23且

其中

于是取s=6，t=-13即可.解毕.

命题1.2.9　设a，b，c∈Z.

（1）（a，b）=1当且仅当存在s，t∈Z，使得as+bt=1.

（2）若c|a，c|b，则c|（a，b）.

（3）若（a，c）=1，则（ab，c）=（b，c）.

（4）若（a，c）=1，c|ab，则c|b.

（5）若（a，c）=（b，c）=1，则（ab，c）=1.

（6）若（a，b）=1，a|c，b|c，则ab|c.

证明　　　（1）必要性由推论1.2.7可得.反之，若x|a，x|b，则x|as+bt=1.这表明x只能为±1，于是a，b的公因数只有±1，故（a，b）=1.

（2）据推论1.2.7知存在s，t∈Z，使得（a，b）=as+bt.于是由c|a，c|b可知

c|as+bt=（a，b）.

（3）显然，b，c的公因数均为ab，c的公因数.另一方面，由（a，c）=1及条款（1）知存在s，t∈Z，使得as+ct=1.于是b=abs+bct.这导致ab，c的公因数均为b，c的公因数.故b，c和ab，c有完全相同的公因数，从而有相同的最大公因数，即（ab，c）=（b，c）.

（4）由（a，c）=1及条款（1）知存在s，t∈Z，使得as+ct=1.由c|ab知c|abs+bct=b.

（5）由（a，c）=（b，c）=1及条款（1）知存在s，t，u，v∈Z，使得as+ct=1=bu+cv.于是

（as+ct）（bu+cv）=ab（su）+c（asv+but+ctv）=1.

再次据条款（1），有（ab，c）=1.

（6）由条款（1）及（a，b）=1知存在s，t∈Z，使得as+bt=1.由a|c，b|c可得ab|bc，ab|ac.故ab|acs+bct=c.证毕.

命题1.2.10　设a，b是不全为零的整数，m是正整数.则

（am，bm）=（a，b）m.

证明　记d=（am，bm）.由命题1.2.9（2）及（a，b）m|am，（a，b）m|bm知（a，b）m|d.另一方面，据推论1.2.7知存在s，t∈Z，使得（a，b）m=ams+bmt，而由d|am，d|bm知d|（a，b）m.这表明（am，bm）=（a，b）m.证毕.

推论1.2.11　设a，b是不全为零的整数，m是正整数.若m|a，m|b，则特别的，

类似于两个整数的情形，可以考虑多个整数的最大公因数.

定义1.2.12　设a1，a2，…，ak∈Z（k≥2），d∈Z.称d是a1，a2，…，ak的公因数，若d|ai，i=1，2，…，k.对不全为零的整数a1，a2，…，ak，称它们的公因数之最大者为a1，a2，…，ak的最大公因数，记作（a1，a2，…，ak）.对于a1，a2，…，ak全为0的情况，规定其最大公因数为0.若（a1，a2，…，ak）=1，则称a1，a2，…，ak互素.若a1，a2，…，ak中任意两个数均互素，则称a1，a2，…，ak两两互素.显然，两两互素必互素，但反之未必.

下述命题将求多个整数的最大公因数的问题归结为求两个整数的最大公因数的问题，其证明留作习题.

命题1.2.13　设a1，a2，…，an∈Z（n≥2）.记

d1=a1，（dj-1，aj）=dj，j=2，3，…，n.

则（a1，a2，…，an）=dn且存在s1，s2，…，sn∈Z，使得a1s1+a2s2+…+ansn=dn.