设d是ab与c的任一公因数.由上式及§1定理3，d|b,因 而d是b,c的一个公因数反之b,c的任一公因数显然是ab,c 的一个公因数，故()获证 (ii)因为b,c不全为零，故(b,c)是存在的，因而由(i)即知 (ab,c)存在，且 (ab,c)=(b,c) 证完 推论21若(a,c)=1,cab,则cb 证由定理2及§2定理2,3得 |c|=(ab,c)=(b,c), 故|c|b,因而cb. 证完 推论22设a,.,a及b,b,.,bm是任意两组整数 若前一组中任一整数与后一组中任一整数互质，则a.a与 bb.bm互质 证由定理2，我们知道 (ai.aa,)=(aa.ab) =.=(am,b）=1,j=1,2,.,m 再用定理2， (ai.an,bb2.bm）=(a.an,b2b3.bm） =.=（a1h.an,bm）=1.证完 下面我们应用刚才得到的关于整除的性质来研究公倍数与最 小公倍数. 定义设a,a,.,a,是n(n≥2)个整数若d是这n个数 的倍数，则d就叫作这n个数的一个公倍数又在a,a,.,a 的一切公倍数中的最小正数叫作最小公倍数，记作[，.， a. 由于任何正数都不是0的倍数，故讨论整数的最小公倍数时， ·概假定这些整数都不是零· 定理3【a,a,.,a]=[|al,la,.,|a门（证明留给
设 d 是 ab 与 c 的任一公因数 .由上式及§1 定理 3, d | b, 因 而 d 是 b, c 的一个公因数 .反之 b, c 的任一公因数显然是 ab, c 的一个公因数,故( i)获证 . (ii) 因为 b, c 不全为零, 故 ( b, c) 是存在的, 因而由 (i) 即知 ( ab, c)存在, 且 ( ab, c) = ( b, c) 证完 推论 2 .1 若( a, c) = 1, c| ab, 则 c| b . 证 由定理 2 及§2 定理 2, 3 得 | c | = ( ab, c) = ( b, c) , 故 | c| | b,因而 c| b . 证完 推论 2 .2 设 a1 , a2 ,., an 及 b1 , b2 ,., bm 是任意两组整数 . 若前一组中任一整数与后一组中任一整数互质, 则 a1 a2 . an 与 b1 b2. bm 互质 . 证 由定理 2,我们知道 ( a1 a2 . an , bj ) = ( a2 a3. an bj ) = . = ( an , bj ) = 1, j = 1 ,2 ,., m . 再用定理 2, ( a1 a2. an , b1 b2 . bm ) = ( a1 a2. an , b2 b3. bm ) = . = ( a1 a2. an , bm ) = 1 . 证完 下面我们应用刚才得到的关于整除的性质来研究公倍数与最 小公倍数 . 定义 设 a1 , a2 ,., an 是 n ( n≥2) 个整数 .若 d 是这 n 个数 的倍数,则 d 就叫作这 n 个数的一个公倍数 .又在 a1 , a2 , ., an 的一切公倍数 中的最小正数叫作 最小公倍数, 记作 [ a1 , a2 , ., an ] . 由于任何正数都不是 0 的倍数,故讨论整数的最小公倍数时, 一概假定这些整数都不是零 . 定理 3 [ a1 , a2 ,., an ] = [ | a1 | , | a2 | , ., | an | ] .(证明留给 · 11 ·
读者) 同最大公因数的情形一样，我们先研究两个整数的最小公倍 数 定理4设a,b是任意两个正整数，则(i)a,b的所有公倍数 就是[a,b]的所有倍数；(ii)a,b的最小公倍数等于以它们的最大 公因数除它们的乘积所得的商，即[。，1=特别地，若 (a,b)=1,则[a,b]=ab. 证设m是a,b的任一公倍数.由定义可设 m'=ak=bk'. 令a=a(a,b),b=b(a,b),由上式即得 a k=bk'. 但由§2定理5，(4，b)=1,故由推论21，b|k.因此 m=k=2 (6) 其中1满足等式k=61反过来，当1为任一整数时，(！为 a,b的一个公倍数，故(6)可以表示a,b的一切公倍数.令t=1 即得到最小的正数，故 [a,b1=(a,b) ab 即()获证又由(6)，()亦获证. 证完 现在讨论两个以上整数的最小公倍数设a,a,.,a,是n 个正整数，令 [a,a]=2,[m2,a]=m3,.,[ma-1,an]=mm.(7) 我们就有 定理5若a,.,a是n(n≥2)个正整数，则 [a,a2,.,aa]=ma 证由(7)，m|m*1,i=2,3,.,n-1,且a|m,a|m, ·12·
读者) 同最大公因数的情形一样,我们先研究两个整数的最小公倍 数 . 定理 4 设 a, b 是任意两个正整数, 则(i) a, b 的所有公倍数 就是[ a, b] 的所有倍数; (ii) a, b 的最小公倍数等于以它们的最大 公因数除它们的乘 积所 得的商, 即 [ a, b] = ab ( a, b) .特别 地, 若 ( a, b) = 1, 则[ a, b] = a·b . 证 设 m′是 a, b 的任一公倍数 .由定义可设 m′= ak = bk′. 令 a = a1 ( a, b) , b = b1 ( a, b) ,由上式即得 a1 k = b1 k′. 但由§2 定理 5, ( a1 , b1 ) = 1,故由推论 2 .1 , b1 | k .因此 m′= ak = ab1 t = ab ( a, b) t , ( 6) 其中 t 满足等式 k = b1 t .反过来, 当 t 为任一整数时, ab ( a, b) t 为 a, b 的一个公倍数, 故 ( 6 ) 可以表示 a, b 的一切公倍数 .令 t = 1 即得到最小的正数,故 [ a, b] = ab ( a, b) . 即(ii) 获证 .又由( 6) , (i)亦获证 . 证完 现在讨论两个以上整数的最小公倍数 .设 a1 , a2 , ., an 是 n 个正整数,令 [ a1 , a2 ] = m2 , [ m2 , a3 ] = m3 ,., [ mn - 1 , an ] = mn . ( 7) 我们就有 定理 5 若 a1 , a2 ,., an 是 n ( n≥2 )个正整数,则 [ a1 , a2 ,., an ] = mn . 证 由 ( 7 ) , mi | mi + 1 , i = 2, 3, ., n - 1, 且 a1 | m2 , ai | mi , · 12 ·
i=2,3,.,n,故m是a,.,a的一个公倍数.反之，设m 是a,.,a的任一公倍数，则a|m,|m,故由定理4(i) m|m又a|m,同样由定理4(i)得m|m.依此类推，最后得 mn|m因此mn≤|ml故 mn=[a,.,an] 证完 由于最大公因数可以实际地求出来，因此定理3,4,5给出了 最小公倍数的求法 注：对于多项式来说，带余式除法也可如下稍作改变证明其成 立：我们知道形如 P(x)=ax+a1x1+.+ax+a,a,≠0，(8) 其中n为正整数，a,a,.,a。为实数（或某一数域的元素），被称 为n次多项式.于是多项式的带余式除法就可以叙述为： 设P(x),M(x)是任意两个多项式，P(x)的次数大于 M(x),则存在两个多项式Q(x),R(x)使得 P(x)=e(x)M(x)+R(x), (9) 其中R(x)的次数小于M(x)的次数，并且Q(x)和R(x)是惟一 的 它的证法作如下的改变：设 M(x)=bmx"+.+bx+b,bn≠0， 则P(x)~是x“M(x)(记为P(x)为一多项式，次数最多是 n1,因而P(x)=会x“Mx)+P()依照同样的办法考察 P(x),M(x),可得一次数更低的多项式，如此类推，最后即得多 项式的带余式除法(9) 至于本章所讨论的概念、算法、整数的整除性、因数、倍数的各 种性质以及下一节的算术基本定理都可以不困难地用类似的手法 对多项式证明成立第三、四章也有很多性质对多项式也相应成 ·13·
i = 2 ,3 ,., n, 故 mn 是 a1 , a2 , ., an 的一个公倍数 .反之, 设 m 是 a1 , a2 , ., an 的任一公倍数, 则 a1 | m , a2 | m , 故由定理 4 ( i) , m2 | m .又 a3 | m , 同样由定理 4 ( i) 得 m3 | m .依此类推, 最后 得 mn | m .因此 mn≤ | m | .故 mn = [ a1 , a2 , ., an ] . 证完 由于最大公因数可以实际地求出来, 因此定理 3, 4, 5 给出了 最小公倍数的求法 . 注:对于多项式来说, 带余式除法也可如下稍作改变证明其成 立:我们知道形如 P( x ) = an x n + an - 1 x n - 1 + . + a1 x + a0 , an ≠ 0, ( 8) 其中 n 为正整数, a0 , a1 ,., an 为实数 (或某一数域的元素) ,被称 为 n 次多项式 .于是多项式的带余式除法就可以叙述为: 设 P ( x ) , M ( x ) 是 任 意 两 个 多 项 式, P ( x ) 的 次 数 大 于 M( x ) ,则存在两个多项式 Q( x ) , R( x )使得 P( x ) = Q( x ) M( x ) + R( x ) , ( 9) 其中 R( x )的次数小于 M ( x )的次数, 并且 Q( x ) 和 R( x ) 是惟一 的 . 它的证法作如下的改变:设 M( x ) = bm x m + . + b1 x + b0 , bm ≠ 0, 则 P( x ) - an bm x n - m M ( x ) ( 记为 P1 ( x ) ) 为一多项式, 次数最多是 n - 1, 因而 P( x ) = an bm x n - m M ( x ) + P1 ( x ) .依照同样的办法考察 P1 ( x ) , M( x ) ,可得一次数更低的多项式, 如此类推, 最后即得多 项式的带余式除法(9 ) . 至于本章所讨论的概念、算法、整数的整除性、因数、倍数的各 种性质以及下一节的算术基本定理都可以不困难地用类似的手法 对多项式证明成立 .第三、四章也有很多性质对多项式也相应成 · 13 ·
立，如果读者学习过多项式的基本性质，不妨作为复习重新演练一 遍，进一步理解整数的整除性与多项式的整除性的联系，如果没有 学过，则不妨逐一考察其成立与否，肯定会大有好处的 习 题 1证明两整数a,b互质的充分与必要条件是：存在两个整数5,1满足 条件 as+bt=1. 2证明定理3 3设 anx”+an.1x-1+.+a1x+6 (10) 是一个整数系数多项式且，an都不是零，则(1)的有理根只能是以a的因 数作分子以4的因数作分母的既约分数，并由此推出2不是有理数： §4质数·算术基本定理 在正整数里，1的正因数就只有它本身，因此在整数中间1占 有特殊的地位任一个大于1的整数，都至少有两个正因数，即1 同它本身，我们把这些数再加以分类，就得到下面的 定义一个大于1的整数，如果它的正因数只有1及它本身， 就叫作质数（或素数）；否则就叫作合数 质数在研究整数的过程中占有一个很重要的地位，本节的主 要目的就是要证明任何一个大于1的整数，如果不论次序，能惟一 地表成质数的乘积我们先证明每一个大于1的整数有一质因数， 即 定理1设a是任一大于1的整数，则a的除1外最小正因 数g是一质数，并且当a是合数时，g≤a 证假定9不是质数，由定义，9除1及本身外还有一正因数 ,因而1<<q但gla,所以g|a,这与q是a的除1外的最 ·14
立,如果读者学习过多项式的基本性质, 不妨作为复习重新演练一 遍,进一步理解整数的整除性与多项式的整除性的联系; 如果没有 学过,则不妨逐一考察其成立与否, 肯定会大有好处的 . 习 题 1 .证明两整数 a, b 互质的充分与必要条件是: 存在两个整数 s, t 满足 条件 as + bt = 1 . 2 .证明定理 3 . 3 .设 an x n + an - 1 x n - 1 + . + a1 x + a0 (10) 是一个整数系数多项式且 a0 , an 都不是零 ,则 (1 )的有理根只能是以 a0 的因 数作分子以 an 的因数作分母的既约分数 ,并由此推出 2不是有理数 . §4 质数·算术基本定理 在正整数里,1 的正因数就只有它本身, 因此在整数中间 1 占 有特殊的地位 .任一个大于 1 的整数, 都至少有两个正因数, 即 1 同它本身,我们把这些数再加以分类, 就得到下面的 定义 一个大于 1 的整数,如果它的正因数只有 1 及它本身, 就叫作质数(或素数) ;否则就叫作合数 . 质数在研究整数的过程中占有一个很重要的地位, 本节的主 要目的就是要证明任何一个大于 1 的整数,如果不论次序, 能惟一 地表成质数的乘积 .我们先证明每一个大于 1 的整数有一质因数, 即 定理 1 设 a 是任一大于 1 的整数, 则 a 的除 1 外最小正因 数 q 是一质数,并且当 a 是合数时, q≤ a . 证 假定 q 不是质数,由定义, q 除 1 及本身外还有一正因数 q1 , 因而 1 < q1 < q .但 q | a, 所以 q1 | a, 这与 q 是 a 的除 1 外的最 · 14 ·
小正因数矛盾，故g是质数 当a是合数时，则a=aq,且a>1,否则a是质数由于q 是a的除1外的最小正因数，所以q≤a,q≤qa=a,故q≤a 证完 定理2若p是一质数，a是任一整数，则a能被p整除或p 与a互质. 证因为(p,a)川p,(p,a)>0,由质数的定义，(p,a)=1,或 (p,a)=p即(p,a)=1或pla, 证完 推论2.1设a,&,.,a,是n个整数，p是质数.若 paa.a,则p一定能整除某一a 证假定a,2,.,a都不能被p整除，则由定理2 (p,a)=1,i=1,2,.,n. 因此由§3推论22，（p,aa.a)=1,这与plaa.a矛盾， 故推论获证 证完 定理3（算术基本定理）任一大于1的整数能表成质数的乘 积，即任一大于1的整数 a=pip.pm,pi≤p≤.≤pn, (1) 其中p,pm,.,p是质数，并且若 a=94.9,9≤g≤.≤g, 其中4，.，9m是质数，则m=n,g=p,i=1,2,.,n. 证我们用数学归纳法先证明(1)式成立当a=2时，(1)式 显然成立假定对一切小于a的正整数(1)式都成立，此时若a是 质数，则(1)式对a成立；若a是合数，则有两正整数bc满足条件 a=bc,1 b<a,1 c<a 由假定 b=plp.pi,c=pi+1p1+2.pm 于是 a=pip.ppi+1.pa. 将p,的次序适当调动后即得(1)式，故(1)式对a成立.由归纳法 即知对任一大于1的正整数，(1)式成立 ·15·
小正因数矛盾,故 q 是质数 . 当 a 是合数时, 则 a = a1 q, 且 a1 > 1, 否则 a 是质数 .由于 q 是 a 的除 1 外的最小正因数, 所以 q≤ a1 , q 2≤ qa1 = a,故 q≤ a . 证完 定理 2 若 p 是一质数, a 是任一整数, 则 a 能被 p 整除或 p 与 a 互质 . 证 因为( p, a) | p, ( p, a ) > 0, 由质数的定义, ( p, a ) = 1, 或 ( p, a) = p .即( p, a) = 1 或 p | a . 证完 推论 2 .1 设 a1 , a2 , ., an 是 n 个 整 数, p 是 质 数 .若 p | a1 a2. an ,则 p 一定能整除某一 ak . 证 假定 a1 , a2 ,., an 都不能被 p 整除,则由定理 2 ( p, ai ) = 1, i = 1, 2, ., n . 因此由§3 推论 2 .2, ( p, a1 a2 . an ) = 1, 这与 p | a1 a2 . an 矛盾, 故推论获证 . 证完 定理 3(算术基本定理 ) 任一大于 1 的整数能表成质数的乘 积,即任一大于 1 的整数 a = p1 p2. pn , p1 ≤ p2 ≤ . ≤ pn , ( 1) 其中 p1 , p2 , ., pn 是质数, 并且若 a = q1 q2. qm , q1 ≤ q2 ≤ . ≤ qm , 其中 q1 , q2 ,., qm 是质数, 则 m = n, qi = pi , i = 1, 2, ., n . 证 我们用数学归纳法先证明( 1 )式成立 .当 a = 2 时, (1 ) 式 显然成立 .假定对一切小于 a 的正整数(1 ) 式都成立, 此时若 a 是 质数,则( 1) 式对 a 成立; 若 a 是合数, 则有两正整数 bc 满足条件 a = bc, 1 < b < a, 1 < c < a . 由假定 b = p′ 1 p′ 2. p′ l , c = p′ l + 1 p′ l + 2. p′n , 于是 a = p′ 1 p′ 2. p′ l p′ l + 1. p′n . 将 p′ i的次序适当调动后即得( 1 )式, 故( 1 ) 式对 a 成立 .由归纳法 即知对任一大于 1 的正整数, ( 1) 式成立 . · 15 ·