2017/1/7 14:20
第二节 最大公因数与辗转相除法
1、定义 设a1 , a2 , , an是n(n 2)个整数，若整数d 是 它们之中每一个的因数，那么d就叫作a1 , a2 , , an的一个 公因数。所有公因数中最大的一个叫最大公因数，记作 （a1 , a2 , , an），若（a1 , a2 , , an） =1，则说a1 , a2 , , an互质 或互素。
rn 1 rn qn 1 +rn 1,
定理4
rn 1 0。
若a, b是任意两个正整数，则(a, b) rn ，
rn是上式中最后一个不等于零的余数。
证明: 由于 |b|＞r1＞r2＞…＞rn＞0, 故欧 几里德算法中的带余除法必在有限步内得 到一个余数是零的等式, 即rn+1=0. 根据前面定理可知： (a,b)=(b,r1)=…=(rn-1,rn)= (rn,0)=rn. 欧几里德算法也称辗转相除法.
推论2.1
若b是任一非零整数，则(0, b) b
4、定理3 设a,b,c是三个不全为零的整数，且
a=bq+c 其中q是非零整数，则a,b与b,c有相同的公因数， 因而(a,b)=(b,c)
5、下面要介绍一个计算最大公约数的算法——辗转 相除法，又称Euclid算法。它是数论中的一个重要 方法，在其他数学分支中也有广泛的应用。 定义 下面的一组带余数除法，称为辗转相除法。
带余数除法的第二种表示 定理4 若a, b是两个整数，其中b 0，则存在着两个整数 q及r，使得 a bq r， 0r b 成立，而且q及r是唯一的。
证明分析：作整数序列 ，-3 b ,-2 b ,- b ,0,b ,2 b ,3 b , 则a必满足q b a<(q+1) b , 其中q Z , 令a q b r可得到a b q r , 分b 0和 b 0来讨论q, 进一步证明q, r的唯一性。
推论4.1
说明：
a, b的公因数与(a, b)的因数相同。
（1）利用辗转相除法可以求两个整数的最大公因数
（2）辗转相除法中所包含的等式个数, 即所要做的带余数除法的次数估计为 2 log b n log 2
例1、a 1859, b 1573, 求(1859,1573)
6、最大公因数的两个性质
对于两个以上整数的最大公因数问题，不妨设
a1 , a2 ,, an是任意n个正整数，令 (a1 , a2 ) d 2 , (d 2 , a3 ) d3 ,, (d n1 , an ) d n . 于是我们有
定理6 a1 , a2 ,, an是n个正整数，则 (a1 , a2 ,, an ) dn .
a 3q r , 0 r 3，
证明：a Z , 而
(3q r )2 3n 1,
0 r 3.
例2、任意给出的5个整数中，必有3个数之 和被3整除。
证：设这5个数为ai , i 1,,5，记 ai 3qi ri， 0 ri 3, i 1,,5。 分别考虑以下两种情形：
成立，而且q及r是唯一的。 ()式中的q及r分别叫a被b除所得的不完全商和余数。
证明分析：作整数序列 ，-3b,-2b,-b,0,b,2b,3b, 则a必满足qb a<(q+1)b, 的唯一性。 其中q Z , 令a qb r可得到a bq r , 进一步证明q, r
第一章 整数的可除性
一、整除的概念、带余数除法
二、最大公因数与辗转相除法 三、整除的进一步性质 四、质数、算术基本定理 五、取整函数及其在数论中的一个应用
第一节 整除的概念、带余数除法
定义 设a, b是任意两个整数，其中b 0，如果 存在一个整数q使得等式 a qb 成立，就说b整除a或a被b整除，记作b a， 此时把b 叫作a的因数，把a叫作b的倍数.
如果不存在整数q使得a bq成立，则称a不被b整除， 记为b † a。
1、下面的结论成立：
(ⅰ) a|b (-a)|b a|(-b) (-a)|(-b) |a|||b|； (ⅱ) ab，bc ac； (ⅲ) ab, ac 对任意 x、y , 有abx+cy ,一般地， abi，i = 1, 2, , k ab1x1 b2x2 bkxk， 此处xi（i = 1, 2, , k）是任意的整数； (ⅳ ) a b acbc，c是任意的非零整数； (ⅴ ) a b且 b a a= b； (ⅵ) ab，b 0 |a| ≤|b|；ab且|b| < |a| b = 0.
2、任意整数的最大公因数可转化为正整数来讨论
定理1
若a1 , a2 , , an是任意n个不全为零的整数，
则 （i ) a1 , a2 , , an 与 a1 , a2 ,, an 的公因数相同； (ii)(a1 , a2 , , an ) ( a1 , a2 ,, an ).
3、下面先讨论两个非负整数的最大公因数 定理2、设b是任一正整数，则（i)0与b的公因数就是 b的因数，反之， b的因数也就是0与b的公因数。 (ii)(0,b)=b
定理1 、若a, b是任意两个正整数，则
k 1 Qk a P b ( 1) rk , k 1, , n; k
其中 P 0 1, P 1 q1 , P k qk P k 1 P k 2 , Q0 0, Q1 1, Qk qk Qk 1 Qk 2 , k 2, 3, , n
唯一性
假设有两对整数q 、r 与q 、r 都使得式 () 成立，
即
a = q b r = q b r ，0 ≤ r , r < |b|，则
(q q )b = r r ，|r r | < |b|， 因此 r r = 0，r = r ，再由式(1)得出 q = q ，唯一性得证. 证毕. (1)
(i)若在r1 , , r5中数0， 1，都出现，不妨设 2 r1 0, r2 1, r3 2， a1 a2 a3 3(q1 q2 q3 ) 3 可以被3整除。 此时
(ii )若在r1 , , r5中数0， 1，至少有一个不出现， 2 这样至少有3个ri要取相同的值，不妨设 r1 r2 r3 r(r 0,1或2）， a1 a2 a3 3(q1 q2 q3 ) 3r 可以被3整除。 此时
定理5 设 a, b, 是任意两个不全为零的整数， (am, bm) ( a, b) m a b a, b (ii )若 是a, b的任一公因数，则 , ， a b 特别 , 1 ( a, b) ( a, b) (i )m是任一正整数，则
例 当a 5, b 2时，可有
q及r，使得
a bq r，
r
b
5 （ 2） （ 3 ） （ 1 ），即q 3, r 1; 或5 （ 2） （ 2） 1 ，即q 2, r 1
带余数除法的应用举例
例1 证明形如3n-1的数不是平方数。
一般地有 设a与b是两个整数，b 0，设d是一给定 的整数. 那么，一定存在唯一的两个整数 q1和r1，使得 a = bq1 r1，d ≤ r1<|b| +d (4)
带余数除法的第三种表示（课后习题） 定理4 若a, b是两个整数，其中b 0，则存在着两个整数 2 成立，而且当b是奇数时，q及r是唯一的；当b是偶数时，q及r 有可能是不唯一的。
设a, b是整数，b 0，依次做带余数除法
a bq1 r1，0 r1 b，
b r1q2 r2，0 r2 r1，

rk 1 rk qk 1 rk 1， 0 rk 1 rk ，

rn 2 rn 1qn rn， 0 rn rn 1，
即当a与b是正整数时，只要使用被2除的除法运算和 减法运算就可以计算出(a,b) 例1、求（12345,678）
解： （12345,678）=（12345，339）
=（12006,339）=（6003,339） =（5664,339） =（177,339） =（177,162） =（177，81） =（96,81） =（3,81）=3
例3、设a 1为奇数，证明： 存在正整数d a 1, 使得a 2 1
d
证：考虑下面的a个数： 20 , 21 ,, 2a 1，显然a不整除2 j (0 j a)，
由带余除法，对每个2 (0 j a)，
j
2 j q j a rj , (0 rj a )
因而a个余数r0 , r1 , , ra 1仅可能取a 1个值， 因此其中必有两个相等。
设为ri，rk，不妨设0 i k a，因而有 a(qk qi ) 2 2 2 (2
k i i k i
1)
则有 a2
k i
1，取d k i a 1，则d 就满足要求。
定理8 下面的等式成立：
(ⅰ) （a1 , a2)=(a2 , a1)=(-a1 , a2) ；一般地 (a1 , a2 , , ai , , ak) = (ai , a2 , , a1 , , ak) = (-a1 , a2 , , ak)=(|a1| , |a2| , , |ak|)； (ⅱ) 若a1|aj , j = 2, , k,则（a1 , a2)=(a1 , a2, , ak) =(a1)=|a1| (ⅲ) 对任意整数x ，(a1 , a2)=(a1 , a2 , a1x) (a1 , , ak)=(a1 , , ak , a1x)； (ⅳ)对任意整数x ,（a1 , a2)=(a1 , a2+a1x) (a1 , a2 , a3 , , ak)=(a1 , a2+a1x , a3 , , ak) ； (ⅴ)若p是素数, 则(p , a) = 1或pa；一般地 （p , a1 , , ak)=1或p.