§1.2最大公因数和最小公倍数 定义1设aa…是n个整数。如果整数d是它们中 每一个数的因数,那么就称d为a1a2…an的一个公因 数。当a,a,不全为零时,称它们的所有公因数中 最大的一个正整数为整数a,a,…a的最大公因数,记 作(a,a2…a),即 (a,an2…,a)=max{ld|an,da2…;dla} 特别地,当(a,a32…;an)=时,称a1,a12…a互素。 由定义可以看出对任意非零整数a,有(a,0)=al。 定义2设a,a,…a是n个整数。如果整数m是它们中 每一个数的倍数,那么就称m为a1,a2…a的一个公倍 数。当a,an…a都不为零时,称它们的所有公倍数中 最小的一个正整数为整数a,a2…a的最小公倍数,记 作[a,an,…,a],即 [a,a2…a]=min{m>0a|m,a1m,…an|m 由最大公因数和最小公倍数的定义,很容易发现他们 具有如下性质 性质1(i)(an,an,…;an)=(a| a.a a. a (i)设a,b,c是三个不全为零的整数,如果 a=bq+c,其中q是整数,则 (a,b)=(b,c)
§1.2 最大公因数和最小公倍数 定义 1 设 a a a n , , 1 2 是 n 个整数。如果整数 d 是它们中 每一个数的因数，那么就称 d 为 a a a n , , 1 2 的一个公因 数。当 a a a n , , 1 2 不全为零时，称它们的所有公因数中 最大的一个正整数为整数 a a a n , , 1 2 的最大公因数，记 作 ( ) a a a n , , , 1 2 ，即 (a1 ,a2 , ,a n ) = maxd d | a1 ,d | a2 , ,d | a n 特别地，当 (a1 ,a2 , ,a n ) =1 时，称 a a a n , , 1 2 互素。 由定义可以看出对任意非零整数 a ，有 (a,0) =| a |。 定义 2 设 a a a n , , 1 2 是 n 个整数。如果整数 m 是它们中 每一个数的倍数，那么就称 m 为 a a a n , , 1 2 的一个公倍 数。当 a a a n , , 1 2 都不为零时，称它们的所有公倍数中 最小的一个正整数为整数 a a a n , , 1 2 的最小公倍数，记 作 [ , , , ] a1 a2 a n ，即 [a1 ,a2 , ,a n ] = minm 0 a1 | m,a2 | m, ,a n | m 由最大公因数和最小公倍数的定义，很容易发现他们 具有如下性质 性质 1 （ⅰ） ( , , , ) (| |,| |, ,| |) a1 a2 a n = a1 a2 a n ； , , | |,| |, ,| | a1 a2 a n = a1 a2 a n （ⅱ）设 a,b,c 是三个不全为零的整数，如果 a = bq + c ，其中 q 是整数，则 (a,b) = (b,c) ；
(ii)对任意整数s,t,必有(a,b)(sa+tb); 例1设p是一个素数,a为整数。如果pa,则p与a 互素。 从上面例题可以看出若p是一个素数,则对于任意整 数a,(p,a)=p或者(p,a)=1 由性质1(ⅱ)可由下述辗转相除法具体求出两个整 数的最大公因数(a,b)=F a=be 0≤r<b b=ra.+r, 0≤r<r; F=F2a2+n3, 0≤r<F; r-a- +IN 0 NN-=ln 因为r,r…,r是一个单调有界非负序列,所以必然存 在有限步达到上述最后一个等式。 例2(1)设a=-793,b=2769,计算(a,b); (2)设a=1435,b=3371,计算(a,b)。 上面计算过程可以总结为如下算法: 求任意两个整数a和b最大公因数算法: 算法1.2.1(1)如果a<0,则a=-a,如果b<0,则 6=-b (2)如果a+b=0,则输出“整数a和b无 最大公因数”,结束程序;
（ⅲ）对任意整数 s,t ，必有 (a,b)| (sa + tb) ； 例 1 设 p 是一个素数， a 为整数。如果 p | a ，则 p 与 a 互素。 从上面例题可以看出若 p 是一个素数，则对于任意整 数 a ， ( p,a) = p 或者 ( p,a) =1 由性质 1（ⅱ）可由下述辗转相除法具体求出两个整 数的最大公因数 N (a,b) = r ： 0 1 a = ba + r ， 0 r1 b ； 1 1 2 b = ra + r ， 0 2 1 r r ； 1 2 2 3 r = r a + r ， 0 3 2 r r ； N N N N r = r a + r −2 −1 −1 ， 0 N N−1 r r ； N N aN r = r −1 ， 因为 N r,r , ,r 1 2 是一个单调有界非负序列，所以必然存 在有限步达到上述最后一个等式。 例 2 （1）设 a = −793,b = 2769 ，计算 (a,b) ； （2）设 a =1435,b = 3371 ，计算 (a,b)。 上面计算过程可以总结为如下算法： 求任意两个整数 a 和 b 最大公因数算法： 算法 1.2.1 （1）如果 a 0 ，则 a = −a ，如果 b 0 ，则 b = −b ； （2）如果 a + b = 0 ，则输出“整数 a 和 b 无 最大公因数”，结束程序；
(3)令x=a,x=b,i=0; (4)i=t+1,x+1=x-1%0.x (5)如果x>0,返回到第(4)步 (6)(a,b)=x。 上述算法被称为广义欧几里得除法。 由性质1(i)和(i)我们知道,在步骤(4)中可 以使用绝对值最小余数,这种方法在a和b都比较大 时,算法的复杂性会降低。我们可以看看例2(2)使 用绝对值最小余数的另一种解法:此解法的运算次数 比算法1.2.1少了3次 在辗转相除法具体求两个整数的最大公因数(a,b)=F 的过程中,从倒数第二个式子开始把所有的等式移项 后可得 rd 73=F1-2a 厂2=b-ra1, 7=a b 逐次消除r,F3,…r,r,则可以找到整数s,使得 sa+tb=(a, b=r 例3运用上述方法求整数s,t,使得s+tb=(a,b)
（3）令 x0 = a, x1 = b ， i = 0 ； （4） i = i +1 ， i i i x x %x +1 = −1 ； （5）如果 xi+1 0 ，返回到第（4）步； （6） i (a,b) = x 。 上述算法被称为广义欧几里得除法。 由性质 1（ⅰ）和（ⅱ）我们知道，在步骤（4）中可 以使用绝对值最小余数，这种方法在 a和b 都比较大 时，算法的复杂性会降低。我们可以看看例 2（2）使 用绝对值最小余数的另一种解法：此解法的运算次数 比算法 1.2.1 少了 3 次。 在辗转相除法具体求两个整数的最大公因数 N (a,b) = r 的过程中，从倒数第二个式子开始把所有的等式移项 后可得 N = N−2 − N−1aN−1 r r r N−1 = N−3 − N−2 aN−2 r r r …… 3 1 2 a2 r = r − r ， 2 1a1 r = b − r ， 1 a ba0 r = − 逐次消除 1 2 2 1 r ,r , r ,r N− N− ，则可以找到整数 s,t 使得 N sa + tb = (a,b) = r 例 3 运用上述方法求整数 s,t ，使得 sa + tb = (a,b)
(1)a=1435.b=3371 (2)a=4247b=193874 上述求解过程可以归结为如下定理。 定理1设a,b是任意两个整数,则存在s,t,使得 sa+tb=(a,b) 这里,t由下面等式递归得到 乙人 s-a. S 2,3, =0.1=1t 其中a为(1)式中的不完全商。 如果记r=a,r=b,注意到r=(a,b),则我们只需要 用数学归纳法证明等式 sattb=r 成立即可。由上述定理可知,求整数t,使得 sa+tb=(a,b)可以归结为如下算法 算法122 令r=a,r=b S1=0,=0,t1=1,t=1; (2)如果r=0,则令S=S3,t=t,结束程序 (3)令a LS t =t -at (4)i=i+1,返回到(2); 关于定理1,我们需要注意以下三点 满足等式s+b=(a,b)成立的整数s,t不惟一,例
（1） a =1435,b = 3371 （2） a = 4247,b =193874 上述求解过程可以归结为如下定理。 定理 1 设 a,b 是任意两个整数，则存在 n n s ,t ，使得 s a t b (a,b) n + n = 这里 n n s ,t 由下面等式递归得到 j n t t t t a t s s s s a s j j j j j j j j 2,3, , 0, 1, , 1, 0, , 0 1 2 1 1 0 1 2 1 1 = = = = − = = = − − − − − − − 其中 j a 为（1）式中的不完全商。 如果记 r0 = a,r1 = b ，注意到 r (a,b) N = ，则我们只需要 用数学归纳法证明等式 j j j s a + t b = r 成立即可。由上述定理可知，求整数 s,t ，使得 sa + tb = (a,b) 可以归结为如下算法： 算 法 1.2.2 （ 1 ） 令 r0 = a,r1 = b ， s0 =1,s1 = 0,t 0 = 0,t 1 =1 ， i =1 ； （2）如果 r i = 0 ，则令 1 1 , = i− = i− s s t t ，结束程序； （ 3 ） 令 = − i i i r r a 1 ， i i i i r = r − a r +1 −1 ， i i i i s = s − a s +1 −1 ， i i i i t = t − a t +1 −1 ； （4） i = i +1 ，返回到（2）； 关于定理 1，我们需要注意以下三点： 1. 满足等式 sa + tb = (a,b) 成立的整数 s,t 不惟一，例
如,若有整数s,t,使得sa+b=(a,b),则整数 s=s+b,t=t-a同样可以满足条件; 2.(a,b)=1存在整数s,t,使得s+tb=1,必要性由 定理 直接可得,充分性由式子 (a,b)|a+b=1→(a,b)=1可得; 3.若ab是正整数,则(a,b)=1(2-12-1)=1。首 先注意到如果a被b除的最小正余数是r,则2°-1被 2°-1除的最小正余数是2-1,所以由广义的欧几里得 除法知(2”-12-=2)-1 由定理1我们很容易得到最大公约数和最小公倍数具 有如下性质 性质2(iv)若d|a,d|b,则d|(a,b); (ⅴ)设a,b,c是三个整数,且b,c不同时为 零。如果(a,c)=1,则 (ab, c)=(b,c) 进一步,若c≠0,(an,c)=1,cab,则 cb 若c>0,、(a,b)=d,[a,b] 则 (ac, bc)=cd, ac, bc]=cm; 若c>0,c|d,则 a b d (ⅶi)若a|n,b|n,则[a,b|n;
如，若有整数 s,t ，使得 sa + tb = (a,b) ，则整数 s' = s + b,t' = t − a 同样可以满足条件； 2. (a,b) =1 存在整数 s,t ，使得 sa + tb =1 ，必要性由 定 理 1 直 接 可 得 ， 充 分 性 由 式 子 (a,b) | sa + tb =1 (a,b) =1 可得； 3. 若 a,b 是正整数，则 (a,b) =1 (2 −1,2 −1) =1 a b 。首 先注意到如果 a 被 b 除的最小正余数是 r ，则 2 −1 a 被 2 −1 b 除的最小正余数是 2 −1 r ，所以由广义的欧几里得 除法知 (2 1,2 1) 2 1 ( , ) − − = − a b a b 。 由定理 1 我们很容易得到最大公约数和最小公倍数具 有如下性质： 性质 2 （ⅳ）若 d | a,d | b ，则 d | (a,b) ； （ⅴ）设 a,b,c 是三个整数，且 b,c 不同时为 零。如果 (a,c) =1 ，则 (ab,c) = (b,c)。 进一步，若 c 0 ， (a,c) =1,c | ab ，则 c | b ； （ⅵ）若 c 0,(a,b) = d ， [a,b] = m ， 则 (ac,bc) = cd ， [ac,bc] = cm ； 若 c 0,c | d ，则 c d c b c a = , ； （ⅶ）若 a | n,b | n ，则 [a,b]| n ；
(ⅶ)若(a,b)=1,则[a,b]=ab| ab (a,b) 例4设a,b是两个整数,p是素数,若p|ab,则 p|a或p|b 上述性质对于我们研究整数的性质很有帮助。由性质 2(ⅸx)我们可以得到 求任意两个整数a和b最小公倍数算法: 算法12.3(1)若a=0或b=0,则整数a和b无最小 公倍数; (2)按照求任意两个整数a和b最大公因数 算法计算出(a,b); lab (3)计算[ab=1b° 例5证明:如果整数a,b满足(a,b)=1,那么 (a+b,a-b)=1或者2。 对于k个整数a,a,…a的最大公约数和最小公倍数, 我们有如下递归方法: 定理2设k≥3,a,a2…a是k个整数,则 (a12…,a12a12a)=(a12…,a1-2,(au12a1); 上述定理可以归结为如下算法:
（ⅷ）若 (a,b) =1 ，则 [a,b] =| ab | ； （ⅸ） ( , ) | | [ , ] a b ab a b = 。 例 4 设 a,b 是两个整数， p 是素数，若 p | ab ，则 p | a或p | b。 上述性质对于我们研究整数的性质很有帮助。由性质 2（ⅸ）我们可以得到 求任意两个整数 a 和 b 最小公倍数算法： 算法 1.2.3 （1）若 a = 0 或 b = 0 ，则整数 a 和 b 无最小 公倍数； （2）按照求任意两个整数 a 和 b 最大公因数 算法计算出 (a,b) ； （3）计算 ( , ) | | [ , ] a b ab a b = 。 例 5 证明：如果整数 a,b 满足 (a,b) =1 ，那么 (a + b,a − b) =1 或者 2。 对于 k 个整数 a a ak , , 1 2 的最大公约数和最小公倍数， 我们有如下递归方法： 定理 2 设 k 3 ， a a ak , , 1 2 是 k 个整数，则 ( , , , , ) ( , , ,( , )) a1 ak −2 ak −1 ak = a1 ak −2 ak −1 ak ； [ , , , , ] [ , , ,[ , ]] a1 ak−2 ak−1 ak = a1 ak −2 ak −1 ak 。 上述定理可以归结为如下算法：
求n个整数a,an……a的最大公因数算法 算法1.2.4(1)按照求任意两个整数最大公因数算法 计算(a,a,)=d,令 (2)i=1+1,(d,2a) (3)如果i<n,返回到第(2)步: C.. 求n个整数a,a,2a的最小公倍数算法 算法1.2.5(1)按照求任意两个整数最小公倍数算法 计算[a,a1]=m,令i (2)i=i+1,[m2a,] (3)如果ⅸ<n,返回到第(2)步; (4)[ 利用整除理论,我们很容易判断不定方程ax+b=c (其中a,b,c是整数且ab≠0)是否有解? 定理3不定方程ax+b=c(其中a,b,c是整数且 ab≠0)有解的充分必要条件是(a,b)|c。如果 x=x2y=y是该不定方程的一组解,那么它所有的解 为 k6 (a b ka 其中k=0,±1,+2, y=yo t 6)
求 n 个整数 a a a n , , 1 2 的最大公因数算法 算法 1.2.4 （1）按照求任意两个整数最大公因数算法 计算 1 2 2 (a ,a ) = d ，令 i =1 ； （2） i = i +1 ， 1 1 ( , ) di ai+ = di+ ； （3）如果 i n ，返回到第（2）步； （4） a a a n = d n ( , , , ) 1 2 。 求 n 个整数 a a a n , , 1 2 的最小公倍数算法 算法 1.2.5 （1）按照求任意两个整数最小公倍数算法 计算 1 2 2 [a ,a ] = m ，令 i =1 ； （2） i = i +1 ， 1 1 [ , ] mi ai+ = mi+ ； （3）如果 i n ，返回到第（2）步； （4） a a a n = m n [ , , , ] 1 2 。 利用整除理论，我们很容易判断不定方程 ax + by = c （其中 a,b,c 是整数且 ab 0 ）是否有解？ 定理 3 不定方程 ax + by = c （其中 a,b,c 是整数且 ab 0 ）有解的充分必要条件是 (a,b) | c 。如果 0 0 x = x , y = y 是该不定方程的一组解，那么它所有的解 为 = + = − ( , ) ( , ) 0 0 a b ka y y a b kb x x 其中 k = 0,1,2,
当不定方程有解时,求出其全部解的关键是寻找某 组特解,定理1保证了这样的特解总是可以找到的。 求不定方程ax+b=c(其中a,b,c是整数且ab≠0) 的整数解的算法 算法1.26(1)按照求任意两个整数a和b最大公因 数算法计算出(a,b) (2)判断(a,b)是否整除c?如果(a,b)kc,则不 定方程无解,结束程序; (3)按照算法1.22计算整数s和t,使得 as+bt=(a, b); (4)不定方程的一切解可以表示为 dr= sc kb ,其中k=0,±1,+2 tc (a, b(a,b
当不定方程有解时，求出其全部解的关键是寻找某一 组特解，定理 1 保证了这样的特解总是可以找到的。 求不定方程 ax + by = c （其中 a,b,c 是整数且 ab 0 ） 的整数解的算法 算法 1.2.6 （1）按照求任意两个整数 a 和 b 最大公因 数算法计算出 (a,b) ； （2）判断 (a,b) 是否整除 c ？如果 (a,b) | c ，则不 定方程无解，结束程序； （3）按照算法 1.2.2 计算整数 s 和 t ，使得 as + bt = (a,b) ； （4）不定方程的一切解可以表示为 = + = − ( , ) ( , ) ( , ) ( , ) a b ka a b tc y a b kb a b sc x ，其中 k = 0,1,2,
