1.7正整數(shù)地正約數(shù)個數(shù)與總和

1、§ 1.7 正整數(shù)的正約數(shù)個數(shù)與總和一、正整數(shù)的正約數(shù)個數(shù)我們先看一個有趣的問題 :在一間房子里有編號為 1 100的100盞電燈 ,每盞都配有一 個開關(guān)，開始燈全滅著現(xiàn)在有100個人依次進入房間，第k個人把編號是的k倍數(shù)的燈的開 關(guān)各拉一次 , 這樣操作完之后 , 哪些編號的燈亮著 ?解決這個問題 ， 需要討論各盞燈編號的約數(shù)個數(shù)的奇偶性 . 如何求一個正整數(shù)的約數(shù)的 個數(shù)呢 ?下面我們討論這個問題 .設(shè)為n正整數(shù)，的n正約數(shù)最小為1,最大為，n因此的n正約數(shù)的個數(shù)有限.為了敘述更方便，我們把 正整數(shù)的 n 正約數(shù)個數(shù)記作 d(n) .例如 ， d(1) 1， d(2) 2， d(

2、5) 5， d(8) 4， d(12) 6.從理論上講 ， 求 d(n) 只要把 n 的正約數(shù)全部找出來數(shù)一數(shù)就可以了 ， 但這種方法并不適 合求數(shù)值較大的數(shù)的正約數(shù)的個數(shù) ,例如d(360) , d(450 000).下面我們以求d(360)為例, 介紹可行的方法 .由于 360 23, 其正約數(shù)比形如 n 23 3, 其中 可取 03四個數(shù)之一, 可取 0 2 三個數(shù)之一 , 可取 0,1兩個數(shù)之一 ., 各選定一個允許值 , 構(gòu)成一個組合，代入n即可得到360的正約數(shù)個數(shù)是 24,故d (360)4 3 224.同理由 1444 3 , 可知 d(144) (4 1)(2 1) 15 .

3、定理1設(shè)正整數(shù)n的標準分解式為n pi 1 p2 2術(shù)m，則d(n) (11)( 21)(m 1).證明：n的正約數(shù)必形如 kP1 1 P2 2Pm m，其中1可取0至1中任意一個，共有11種取法；2可取0至2中任意一個，共有21種取法；m可取0至m中任意一個 ， 共有m 1 種取法 ， 那么d(n) (11)(21)(m1).例1求 d(300000) .解：因為 3000002555 ， 所以d(300000)(51)(1 1)(5 1) 72 .例2若n p q ,其中p ， q 為不同質(zhì)數(shù) ，. 且 n2 有 個正約數(shù) ， 求d(n7).解：由n2 p2 q2 ,得d(n2)(2)(2

4、1)153 5.不失一般性設(shè) ，則,2 ,解得 ，故n pq2,則n7 p7q14,所以d(n7)(7 1)(14 1) 8 15120.例3 有一個小于2 000的四位數(shù)，它恰有 個正約數(shù)，其中有一個制約數(shù)的末尾數(shù)字是1,求這個四位數(shù).(1984年初中賽題)解：設(shè)n為所求,則d( n) 14 17 2.若 d(n)14 1,則n p13,而1113 2 000,故此時無解.若 d( n)7 2,則n p q,其中p , q為不同質(zhì)數(shù).為質(zhì)數(shù)p , q選取適當?shù)闹?，使其滿足p , q之一的末位數(shù)是1 ,且000 n 2 000.易知只有當p 2, q 31時，n 26 31 1984符合題意.

5、定理2正整數(shù)n為完全平方數(shù)的充要條件是d(n)為奇數(shù).證明：必要性設(shè) n ( P1 1 P2 2 Pmm )2 (其中p11 p2 2pm m為、n的標準分解式)則12mnP1P2Pm ，故 d(n) (2 1)(221)(2 m1).因為2 1,2 21, 2 m 1均為奇數(shù)，所以 d(n) (2 1)(2 21)(2 m 1).為奇數(shù).充分性設(shè)np1 1p2 2 - pm m為n的標準分解式，則d(n) ( 1)( 21)(m 1).因為d(n)為奇數(shù),所以1 ， 2 1，m 1均為奇數(shù):,從而1 ,2，,m均為偶數(shù)設(shè) 11 ,22 ,mm ,則npi 1P2 2 -Pm m ( P1 1

6、 P2 2 -m2'pm )，所以n為完全平方數(shù).該定理可以用來分析解決本節(jié)開頭提出的“拉燈”問題 ：各盞燈的開關(guān)被拉幾次取決于 其編號的正約數(shù)的個數(shù)，而燈是否被拉亮取決于其開關(guān)被拉次數(shù)的奇偶性 (奇數(shù)則被拉亮) 由定理2可知,亮燈的編號必為完全平方數(shù),即第12,22,32,，102號的燈亮著.當然,該定理的價值遠不止于此，它主要用來判斷一個數(shù)是否是完全平方數(shù)，進而解決其它有關(guān)問題.例4 求證:正整數(shù)n的所有正約數(shù)之積等于.nd(ny .證明： 設(shè)n的所有正約數(shù)為山，n2,nd(n).因為nk n ,所以存在mk ,使 n g(k 1,2, - d(n),從而mk n,即mik是n的正

7、約數(shù)，所以mik是m, n?,，nd(n)之 一 (1 k d( n).故mi, m2,md(n)是ni, n 2,nd(n)重新排序的一個結(jié)果，所以n n nng nd(n)mim2 md(n)-ni n?nd(n)d( n)=n厲吐nd(n)則(nm nd(n)2nd(n),所以 ng )- nd(n).即正整數(shù)n的所有不同正約數(shù)之積等于.n7.由例4自然聯(lián)想，正整數(shù)n的所有正約數(shù)之和等于多少呢？二、正整數(shù)n的所有正約數(shù)之和正整數(shù)n的所有正約數(shù)之和記作S(n),下面我們按n含有的質(zhì)約數(shù)的個數(shù)來討論.1 .當n只含一個質(zhì)約數(shù)時例如，9的正約數(shù)有1 , 3, 32,其和為233 1S(9)1

8、3 32；3 1234532的正約數(shù)有1,2,2 ,2 ,2 ,2 ,其和為2 iS(32)12 2223 24 252 1般地,若n pm ,則m 1 A2m p1S(n) 1 p p pP 11S(n) (1 pPm)(1qk)例如，722332,其正約數(shù)排列如下：1223333 23 392933333則S(72)(1222232 3222332 3232 22 32 23)(122223)(13 32)2413312131 '2.當n含有兩個質(zhì)約數(shù)時m,k為正整數(shù))p,q是互異質(zhì)數(shù)，,則(般地,若npmqkPm1 1 p 1由上述過程不難猜想P1P2 2m /Pm(p1, p2

9、,，Pm是互異質(zhì)數(shù),1,2,，m為正整數(shù)),則1S(n) (1 P1P1 J(11P2P2 2)(11pmmpm ).下面試證這個結(jié)論.從式中每個括號任取一項相乘,積必形如P1 1P2 2 Pm "(其中 0 kk , k 1,2，m),項，共有這樣的積共有多少個呢？在第k個括號任取一項，有k 1種取法，故在m個括號各任取一1) d(n)種取法，即有d(n)個這樣的積.由§ 1.4中算術(shù)基本定理的推論可知.每個這樣的積都是 n的一個正約數(shù)，且n的任一正約數(shù)必是這樣的積S(n),即1(1 P1P 1)(1 P22P2)(1 PmPmm) S(n)這說明我們的猜想是正確的,從而

10、得到了如下的定理定理3 設(shè)正整數(shù)n P1P22mPm,(Pi, P2,，Pm是互異質(zhì)數(shù),中的一個，故所有這樣的積作成的和就是n的所有正約數(shù)之和正整數(shù)),則1S(n) (1 P1Pi 1)(11P2P22)(1Pm1m、Pm)1 1P 1P1 12 1P21P2 1Pm m 11Pm 1求 S(n)360.因為3602332 5,所以432.213151S(360)1170.2 13 15 1求形如2k3m的正整數(shù)，且使其所有正約數(shù)之和為 403.由題意可得S(2k3m) 2213m 111 40313 31 ,故可得下面四個方程組111,1121213m 11403;3m 1131312k11

11、13,2k1121213m 1131；3m 113131403,1；31,上述四種情況只有最后一組有正整數(shù)解4,2.故只有24 32144的所有正約數(shù)之和為 403.例7 求1998的所有正約數(shù)的倒數(shù)之和解： 因為19982 33 37 ,所以d(1998)(1 1)(3 1)(1 1) 16,S(1998)(1 2)(1 3 3233)(1 37)4560 .設(shè)1998的16個正約數(shù)分別為x1,x2, -, x16可按乘積等于1998分為8組，不妨設(shè)X1X2X3X4X5X6X7X8X9X10X11X12X13X14 X15X161998,則111X1X2X16“11、/ 1 1、“ 11、(

12、-)( )()X1X2X3X4X15X16X1X2X3X4X15X16為X2X3X4X15X16x1 x2 . x164560 76019981998 333.如果S(n) 2n,則稱n為完全數(shù),如6,28,496,8128,.截止1996年11月，共發(fā)現(xiàn)了 34個完全數(shù).在兩個正整數(shù)中，若一個數(shù)的所有正約數(shù)之和恰好等于另一個數(shù)，則稱這兩個數(shù)為一對親和數(shù)，如1184與， 與 ，.對完全數(shù)與親和數(shù)感興趣的讀者，以閱讀教育1998年1月版談祥柏譯美阿爾伯特?H?貝勒著數(shù)論妙趣.例8能被30整除，且恰有30個不同正約數(shù)的自然數(shù)共有多少個？(98年市初中數(shù)學(xué)競賽題)解：設(shè)正整數(shù)p分解質(zhì)因數(shù)為p2“ P

13、n"，則它的約數(shù)個數(shù)為佝 1)(32 1)(an 1).因為題中要求的數(shù)能被 30整除，以必然含有質(zhì)因數(shù) 2,3,5,設(shè)此數(shù)為2a1 3a2 5a3, 則它的約數(shù)的個數(shù)為佝1)(a21)(a3 1),因為3 5 ,所以d(p) d(30) 佝 1)(a2 1)(a3 1)3 5,所以p沒有除 3,5之外的質(zhì)因數(shù)，所以a1 1,a2 1,a3 1只能是 3,5或者 或 或 或 或，共6個.例 9 證明對任意一個正整數(shù) ,其正約數(shù)中末位為 1 或 9 的的個數(shù)不小于末位為 3 或 7 的數(shù) 的個數(shù) .證明：設(shè)正整數(shù)約數(shù)中末尾為有m個，7的有n個.設(shè)其為Xi,X2，Xm, yi,y2,，y

14、n(從小到大排列)當 m 0，n0 顯然正確 .n 1時, 1是 n 的正約數(shù) ,n 2時，y2,yi w,，yi yn,互不相同，共n個m 0, 同理可證 .m,n 時，yiy3,，yi yn,共 n 1 個x, X2,Xi Xm共 m 1.Xi yi 末尾為 i,又有1為n的正約數(shù)，至少min 1 1 1 m n個綜上 ,得證 例 10求出最小的正整數(shù) n,使其恰有144個正約數(shù)，并且其中有十個是連續(xù)的整數(shù)例 11(1) 所有的正約數(shù)的和等于 15 的最小自然數(shù)是多少？ 8(2) 所有正約數(shù)的積等于 64 的最小自然數(shù)是多少？ 8(3) 有沒有這樣的自然數(shù) , 其所有正的真約數(shù)之積等于它本

15、身？ 21例12只有 13 個正約數(shù)的最小正整數(shù)是？解： d(n) 13 (12 1)n 最小取 2，所以 212 4096 例 13用 d(n) 表示 正 整 數(shù) n 的 正 約 數(shù) 的 個 數(shù) ,證 明 ： 存在 無 窮多 個 正 整 數(shù) n ,使 得d(n) d(n 1) 1是 3的倍數(shù) 證明 ： 可知當 n 為質(zhì)數(shù)時 d(n) 2則當 n 1的約數(shù)個數(shù)為 3 時d(n) d(n 1) 1 6是 3 的倍數(shù)又可知當n為質(zhì)數(shù)，n 1的約數(shù)為3有無數(shù)組所以存在無窮多個正整數(shù) n,使得d(n) d(n 1) 1是3的倍數(shù).例 14在 30300 的所有正整數(shù)中，有幾個數(shù)恰有三個正約數(shù)？解: 三

16、個正約數(shù)就是： 1 ,x ,其本身,且本身/ x x,推得這個數(shù)等于x2, x是個質(zhì)數(shù).25 5236 62172 2892182 324可知,x是在6到17間的質(zhì)數(shù)：7、11、13、17。這樣的數(shù)可以是：49、 121、 169、 289.所以這樣的 4 個數(shù).例 15求四個不超過 70000 的正整數(shù)，每一個正整數(shù)的約數(shù)的個數(shù)多于 100 個.5040055440604806552069300例 1623 個不同正整數(shù)之和為 4845，問著 23 個數(shù)的最大公約數(shù)可能達到的最大值是多少？ 解:不妨令這23個數(shù)分別為at, bt, ct, dt wt ,其中t是他們的公約數(shù) 要想使t最大無非

17、是a+b+c+d+w 最小由題意可知 23個數(shù)是 不同”的 正整數(shù)”則a+b+c+d+e+w>=1+2+3+23=276 所以說a+b+c+w最小值為27623不同正整數(shù)之和為 4845隨意(a+b+c+w)*t=4845所以t<=4845/276=17.55所以t從17往下數(shù) 而且能被4845整除一個一個試剛好 4845/17=285 所以最大公約數(shù)為 17例 17在 1-200 的 200 個正整數(shù)中，所有只有 3 個約數(shù)的正整數(shù)的和為多少？解：只有3個約數(shù)的正整數(shù)也就是形如N2(N為質(zhì)數(shù))的數(shù)14人2=<200,15人2=225>200 14 以的質(zhì)數(shù)有 2、3、5、7、11、1322+32+52+72+112+132=4+9+25+49+121+169=377在1-200的200個正整數(shù)中，所有只有3個約數(shù)的正整數(shù)的和為 377例 18m 為正整數(shù) m=12n,m 約數(shù)的個數(shù)的兩倍符合條件的最小 n 是幾位數(shù)？解: 2假設(shè) n=2Aa1X3Aa2Xk3Aa3X.kpAap則 n 的約數(shù)個數(shù)為 (1+a1)(1+a2)(1+a3).(1+ap)m=nX2A2X3, 則 m 約數(shù)個數(shù)為( 3+a1)(2+a2)(1+a3).(1+ap)所以 (3+a1)(2+a2)=2(1+a1)(1+a2)化簡得a2(a1-1)=4;則a2=