若a=9.g,≤≤.≤g,则 p1B.pn=44.qm (2) 因此p|g.,|pp.p由推论21，有p,g,使得 p|g,p但g,Pps都是质数，故p=g,g=n又p≥p,g ≥4，故 9=p1≤pk=4,因而p=9=4. 由(2)式乃.p,=.g,同法可得p=依此类推，最后即得 n=m,p=9,i=1,2,.,n 证完 由定理3立刻得到 推论31任一大于1的整数a能够惟一地写成 a=p1.pi,q>0,i=1,.,k, (3) 其中p<乃(i<). (3)叫做α的标准分解式在应用中，为方便计，有时我们插 进若干质数的零次幂而把a表成下面的形式： a=pp2.p,a,≥0，i=1,2,.,1 推论32设a是一个大于1的整数，且 a=pp2.p,a>0,i=1,2,.,k, 则a的正因数d可以表成 d=pip.pi,a,≥B,≥0，i=l,2,.,k 的形式，而且当d可以表成上述形式时，d是a的正因数 证若da,则a=dg,由推论3.1知a的标准分解式是惟 一的，故d的标准分解式中出现的质数都在(j=1,2,k)中 出现，且B在d的标准分解式中出现的指数？牛4，亦即B,≤g 反过来当B≤a时，d显然整除a. 证完 我们应用推论32可以得到下面的推论，这是中学教科书中 求最大公因数及最小公倍数的根据 推论33设a,b是任意两个正整数，且 a=piph2.pk,a,≥0，i=1,2,.,k, ·16·
若 a = q1 q2. qm , q1≤ q2≤.≤ qm , 则 p1 p2. pn = q1 q2. qm . ( 2) 因此 p1 | q1 q2 . qm , q1 | p1 p2 . pn .由 推 论 2 .1 , 有 pk , qj , 使 得 p1 | qj , q1 | pk .但 qj , pk 都是质数,故 p1 = qj , q1 = pk .又 pk≥ p1 , qj ≥ q1 , 故 qj = p1 ≤ pk = q1 , 因而 p1 = qj = q1 . 由(2 )式 p2 . pn = q2 . qm , 同法可得 p2 = q2 .依此类推,最后即得 n = m , pi = qi , i = 1 ,2 ,., n . 证完 由定理 3 立刻得到 推论 3 .1 任一大于 1 的整数 a 能够惟一地写成 i a = p α1 1 . p αk k ,αi > 0, i = 1, ., k , ( 3) 其中 pi < pj ( i < j) . (3 ) 叫做 a 的标准分解式 .在应用中, 为方便计, 有时我们插 进若干质数的零次幂而把 a 表成下面的形式: a = p α1 1 p α2 2 . p αl l ,αi ≥ 0, i = 1 ,2 ,., l . 推论 3 .2 设 a 是一个大于 1 的整数, 且 a = p α1 1 p α2 2 . p αk k ,αi > 0, i = 1, 2, ., k , 则 a 的正因数 d 可以表成 d = p β 1 1 p β 2 2 . p βk k ,αi ≥ βi ≥ 0 , i = 1, 2, ., k 的形式,而且当 d 可以表成上述形式时, d 是 a 的正因数 . 证 若 d | a,则 a = dq, 由推论 3 .1 知 a 的标准分解式是惟 一的,故 d 的标准分解式中出现的质数都在 pj ( j = 1 , 2, ., k ) 中 出现,且 pj 在 d 的标准分解式中出现的指数βj ≯αj , 亦即 βj≤αj . 反过来当 βj≤αj 时, d 显然整除 a . 证完 我们应用推论 3 .2 可以得到下面的推论, 这是中学教科书中 求最大公因数及最小公倍数的根据 . 推论 3 .3 设 a, b 是任意两个正整数, 且 a = p α1 1 p α2 2 . p αk k ,αi ≥ 0, i = 1, 2, ., k , · 16 ·
b=pp.p,B,≥0，i=1,2,.,k, (a,b)=pp2.p, [a,b]=pip2.pk, (4) 其中Y=min(4,B,),8=max(a,B),i=l,2,.,k(证明留给读 者)，min(a,B,)表示a,B,中较小的数，max(a,B)表示a,B中 较大的数 上面我们从理论上证明了任意一个正整数有惟一的标准分解 式但在实际计算中我们还没有简易可行的方法去判断哪些正整 数是质数，也没有简易可行的方法去求出一个正整数的标准分解 式这中间主要的原因是由于质数在正整数列中的分布情形是很 不规则的（这一点还要加以介绍）但在另一方面，我们根据质数的 定义及其性质，可以造出质数表来以供应用. 任给一个正整数N,可以按照下述方法求出一切不超过N的 质数：把不超过N的一切正整数按大小关系排成一串 1,2,3,4,.,N. 首先划去1，第一个留下的是2，它是一个质数： 1,2,3,4,5,6,7,8,9,10,.,N 其次，从2起每隔一位划去一数，这样就划去了2的一切倍数 1,2,3,4,5,6,7,8,9,10,.,N. 第一个留下未划去的是3，它不是2的倍数，因此是一个质数然 后从3起每隔两位划去一数，所划去的数就是3+3m(m=1, 2,.),它们是3的一切倍数(3本身除外)： 1,2,3,4,5,6,7,8,9,10,.,N 第一个留下未划去的是5，它不是小于它的质数(2及3)的倍数， 因此它是质数然后，从5起每隔5·1=4位划去一数，所划去的 数是5+5m(m=1,2,),也就是5的一切倍数(5本身除外)： 1,2,3,4,5,6,7,8,9,10,11,.,N ·17·
b = p β 1 1 p β 2 2 . p βk k ,βi ≥ 0 , i = 1, 2, ., k , 则 ( a, b) = p γ1 1 p γ2 2 . p γk k , [ a, b] = p δ 1 1 p δ 2 2 . p δ k k , ( 4) 其中 γi = min(αi ,βi ) ,δi = max(αi ,βi ) , i = 1, 2 , ., k (证明留给读 者) , min(αi ,βi )表示 αi ,βi 中较小的数, max(αi ,βi ) 表示 αi ,βi 中 较大的数 . 上面我们从理论上证明了任意一个正整数有惟一的标准分解 式 .但在实际计算中我们还没有简易可行的方法去判断哪些正整 数是质数,也没有简易可行的方法去求出一个正整数的标准分解 式 .这中间主要的原因是由于质数在正整数列中的分布情形是很 不规则的(这一点还要加以介绍) .但在另一方面, 我们根据质数的 定义及其性质,可以造出质数表来以供应用 . 任给一个正整数 N ,可以按照下述方法求出一切不超过 N 的 质数:把不超过 N 的一切正整数按大小关系排成一串 1, 2, 3, 4, ., N . 首先划去 1,第一个留下的是 2 ,它是一个质数: 1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,10, ., N . 其次,从 2 起每隔一位划去一数, 这样就划去了 2 的一切倍数, 1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,10, ., N . 第一个留下未划去的是 3, 它不是 2 的倍数, 因此是一个质数 .然 后从 3 起每隔两位划去一数, 所划去的 数就是 3 + 3 m ( m = 1, 2, .) , 它们是 3 的一切倍数(3 本身除外 ) : 1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,10, ., N . 第一个留下未划去的是 5 , 它不是小于它的质数 ( 2 及 3 )的倍数, 因此它是质数 .然后, 从 5 起每隔 5 - 1 = 4 位划去一数, 所划去的 数是 5 + 5 m ( m = 1, 2, .) , 也就是 5 的一切倍数(5 本身除外 ) : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ., N . · 17 ·
如此继续进行，所划去的都是合数，第一个留下的都不是比它小的 质数的倍数，因此总是一个质数用这种方法可以逐一地把质数求 出来这种方法是希腊时代幼拉脱斯展纳(Eratosthenes)发明的， 它好像用筛子筛出质数一样，所以称为幼拉脱斯展纳筛法 要求出不超过N的一切质数，根据定理1，只需把不超过N 的质数的倍数划去就行了，这是因为不超过N的合数的最小质因 数总是不超过N的 为了更清楚地了解质数表的造法，我们举N=30为例，此时 30<6. 故不超过30的质数是2,3,5,7,11,13,17,19,23,29. 上述造质数表的方法并不能在有限步以内把正整数中的一切 质数都找出来，因为我们有 定理4质数的个数是无穷的。 证我们用反证法来证明定理.假定正整数中只有有限个质 数，设为p,Ph,.,p令pnp.A+1=N,则N>1.由定理1， N有一质因数p这里p≠pn,i=1,2,.,k,否则p|pm.pm, pN,因此p1,而与p是质数矛盾故p是上面k个质数以外的 质数，因此定理获证 证完 从这一章可以看出判断一个整数是合数还是质数以及如何具 体地进行因数分解涉及很多运算而且现代的加密技术需要判断 和找出大的质数，例如，50位或者更高位数的质数，解密技术需要 分解大数虽然我们上面说过“幼拉脱斯展纳筛法可以逐一地把质 数求出来”，但是实际上即使动用超级计算机，要想求出一个大的 ·18·
如此继续进行,所划去的都是合数, 第一个留下的都不是比它小的 质数的倍数,因此总是一个质数 .用这种方法可以逐一地把质数求 出来 .这种方法是希腊时代幼拉脱斯展纳 ( Eratosthenes) 发明的, 它好像用筛子筛出质数一样,所以称为幼拉脱斯展纳筛法 . 要求出不超过 N 的一切质数,根据定理 1,只需把不超过 N 的质数的倍数划去就行了,这是因为不超过 N 的合数的最小质因 数总是不超过 N的 . 为了更清楚地了解质数表的造法, 我们举 N = 30 为例, 此时 30 < 6 . 故不超过 30 的质数是 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 . 上述造质数表的方法并不能在有限步以内把正整数中的一切 质数都找出来,因为我们有 定理 4 质数的个数是无穷的 . 证 我们用反证法来证明定理 .假定正整数中只有有限个质 数,设为 p1 , p2 ,., pk .令 p1 p2 . pk + 1 = N, 则 N > 1 .由定理 1, N 有一质因数 p .这里 p≠ pi , i = 1, 2, ., k, 否则 p | p1 p2 . pk , p | N ,因此 p | 1,而与 p 是质数矛盾 .故 p 是上面 k 个质数以外的 质数,因此定理获证 . 证完 从这一章可以看出判断一个整数是合数还是质数以及如何具 体地进行因数分解涉及很多运算 .而且现代的加密技术需要判断 和找出大的质数,例如, 50 位或者更高位数的质数; 解密技术需要 分解大数 .虽然我们上面说过“幼拉脱斯展纳筛法可以逐一地把质 数求出来”, 但是实际上即使动用超级计算机, 要想求出一个大的 · 18 ·
质数，例如100位以上的质数，也是非常困难的，分解大数就更为 困难，这些将在第三章加以介绍现在介绍一些与此有关的经典问 题例如，通常称形如Fm=2+1(m=1,2,.)的数为费马数费 马自己知道从F到F都是质数，然后他猜想所有的F都是质 数后来欧拉发现F不是质数，它有一个真因数641，直到上世纪 末数学家用他们创造的各种方法，经过超级计算机的计算得知，从 F到F,都是合数，还不知道F4是合数还是质数现在许多数学 家认为：F:之后的费马数都是合数，但是这只是一个猜想费马数 与下列尺规作图问题有关：正n边形可尺规作图的充要条件是n ≥3且n的最大单因数是不同的费马质数的乘积另一个有趣的 问题是关于梅森(Mersenne)数形如M.=2”-1(n=1,2,.)的 素数称为梅森数易见：只有当n为质数时，Mn才可能是质数当 n=2,3,5,7时，相应的Mn确为质数，但对于大于11的质数n M中既有质数，又有合数截至1994年底，已知的最大梅森数为 M5943:是否有无穷多个梅森数是一个未解决的难题梅森数与完 全数（即一切正因数的和等于该数的二倍）有关，即数a是双完全 数的充要条件是它能表成2"'Mn(Mn为梅森数)的形式(《数论 导引》第一章§9) 习题 1.试造不超过100的质数表. 2.求82798848及81057226635000的标准分解式 3.证明推论3.3并推广到n个正整数的情形 4.应用推论3.3证明s3的定理4(. 5.若2"+1是质数(n>1),则n是2的方幂 §5函数[x],{x及其在数论中的一个应用 在上一节里面我们讨论了把任意一个正整数分解成标准分解 ·19
质数,例如 100 位以上的质数, 也是非常困难的, 分解大数就更为 困难,这些将在第三章加以介绍 .现在介绍一些与此有关的经典问 题 .例如, 通常称形如 Fm = 2 2 m + 1 ( m = 1 ,2 , .) 的数为费马数 .费 马自己知道从 F0 到 F4 都是质数, 然后他猜想所有的 Fm 都是质 数 .后来欧拉发现 F5 不是质数, 它有一个真因数 641, 直到上世纪 末数学家用他们创造的各种方法,经过超级计算机的计算得知, 从 F5 到 F2 3都是合数,还不知道 F24是合数还是质数 .现在许多数学 家认为: F4 之后的费马数都是合数,但是这只是一个猜想 .费马数 与下列尺规作图问题有关: 正 n 边形可尺规作图的充要条件是 n ≥3 且 n 的最大单因数是不同的费马质数的乘积 .另一个有趣的 问题是关于梅森 ( Mersenne) 数 .形如 Mn = 2 n - 1 ( n = 1, 2, . ) 的 素数称为梅森数 .易见: 只有当 n 为质数时, Mn 才可能是质数 .当 n = 2, 3, 5, 7 时,相应的 Mn 确为质数, 但对于大于 11 的质数 n, Mn 中既有质数, 又有合数 .截至 1994 年底, 已知的最大梅森数为 M85 943 3 .是否有无穷多个梅森数是一个未解决的难题 .梅森数与完 全数(即一切正因数的和等于该数的二倍 )有关, 即数 a 是双完全 数的充要条件是它能表成 2 n - 1 Mn ( Mn 为梅森数 ) 的形式 (《数论 导引》第一章§9 ) . 习 题 1. 试造不超过 100 的质数表 . 2. 求 82 798 848 及 81 057 226 635 000 的标准分解式 . 3. 证明推论 3.3 并推广到 n 个正整数的情形 . 4. 应用推论 3.3 证明§3 的定理 4(ii) . 5. 若 2 n + 1 是质数 ( n > 1 ) ,则 n 是 2 的方幂 . §5 函数[ x] , {x}及其在数论中的一个应用 在上一节里面我们讨论了把任意一个正整数分解成标准分解 · 19 ·
式的问题现在我们就给出n！的标准分解式的一个公式，为了达 到这个目的，我们先介绍两个在数学中常常用到的函数：[x]与 {x} 定义函数[x]与{x}是对于一切实数都有定义的函数，函数 [x]的值等于不大于x的最大整数；函数{x}的值是x-[x]我 们把[x]叫做x的整数部分，{x}叫做x的小数部分. 例[因=3，=2，则=4，号=0，·号=1 子=号，=0.14159.，{2y=0.414 {-}=1-0.14159.=0.95840. 由定义可以立刻得出下列简单性质： Ix=[x]+{x}. Ⅱ[x]≤x<[x]+1,x-1<[x]≤x,0≤{x}<1 Ⅲ[n+x)=n+[x],n是整数. V[x]+[y≤[x+y],{x}+{y≥{x+y v小：风'自 Ⅵ（带余数除法）若a,b是两个整数，b>0,则 a=b号+b分，0≤b号≤b-1 I若a,b是任意两个正整数，则不大于a而为b的倍数的 正整数的个数是号 证a<b时显然设m是任一不大于a而为b的倍数的正 整数，则 0<m=bm≤a, 0<m≤号 (1) 故满足以上条件的m的个数等于满足(1)的m:的个数，因而等 ·20·
式的问题 .现在我们就给出 n ! 的标准分解式的一个公式,为了达 到这个目的, 我们先介绍两个在数学中常常用到的函数: [ x ] 与 { x} . 定义 函数[ x ] 与{ x}是对于一切实数都有定义的函数,函数 [ x ] 的值等于不大于 x 的最大整数; 函数{ x}的值是 x - [ x ] .我 们把[ x ] 叫做 x 的整数部分, { x}叫做 x 的小数部分 . 例 [π] = 3, [ e ] = 2, [ - π] = - 4, 2 3 = 0, - 3 5 = - 1 ; - 3 5 = 2 5 , {π} = 0.141 59., { 2} = 0.414., { - π} = 1 - 0.141 59. = 0.958 40. . 由定义可以立刻得出下列简单性质: Ⅰ x = [ x ] + { x} . Ⅱ [ x ] ≤ x < [ x ] + 1 , x - 1 < [ x ]≤ x , 0≤{ x} < 1 . Ⅲ [ n + x ] = n + [ x ] , n 是整数 . Ⅳ [ x ] + [ y ]≤[ x + y ] , { x} + { y}≥{ x + y} . Ⅴ [ - x ] = - [ x ] - 1,当 x 不是整数时, - [ x ] , 当 x 是整数时 . Ⅵ (带余数除法) 若 a, b 是两个整数, b > 0, 则 a = b a b + b a b , 0 ≤ b a b ≤ b - 1 . Ⅶ 若 a, b 是任意两个正整数, 则不大于 a 而为 b 的倍数的 正整数的个数是 a b . 证 a < b 时显然 .设 m 是任一不大于 a 而为 b 的倍数的正 整数,则 0 < m = bm1≤ a, 0 < m1≤ a b . ( 1) 故满足以上条件的 m 的个数等于满足 ( 1 ) 的 m1 的个数, 因而等 · 20 ·