奧數(shù)講義-數(shù)論-綜合-師

第十二講數(shù)論

一、基本知識

在數(shù)論中，整數(shù)得整除問題占有重要的地位，在各級數(shù)學(xué)競賽中經(jīng)常出現(xiàn)這一類的問

題.我們把有關(guān)整除的必要的基礎(chǔ)知識整理如下：

對于整數(shù)a(本講字母均表示整數(shù))和不為零的整數(shù)b,我們有帶余除法：a=bq+r,

(05<b).其中q稱為商，r稱為余數(shù).特別地，若r=0,即a=bq,則稱a被b整除或

稱b整除a,記為b|a；若rWO,則稱b不整除a,記為bGa.若b|a,我們也稱a是b的倍

數(shù)，b是a的約數(shù)(或因數(shù)).

整除有下面的基本性質(zhì)：

(1)若a|b,b|c,則a|c；

(2)若a|b,k為整數(shù)，則a|kb；

(3)若a|bc,且a與c互質(zhì)，則a|b；特別地，若質(zhì)數(shù)p|bc,則必有p|b或p|c；

(4)若a|b,a|c?則a|(b±c)；

(5)若b|a,c|a,且b與c互質(zhì)，則bc|a.

能被某些數(shù)整除的整數(shù)的一些特征：

(1)被2整除的數(shù)：個位數(shù)字是偶數(shù)；

(2)被5整數(shù)的數(shù)：個位數(shù)字是0或5；

(3)被4整除的數(shù)：末兩位組成的兩位數(shù)被4整除；

被25整除的數(shù)：末兩位組成的兩位數(shù)被25整除；

(4)被8整除的數(shù)：末三位組成的三位數(shù)被8整除；

被125整除的數(shù)：末三位組成的三位數(shù)被125整除；

(5)被3整除的數(shù)：數(shù)字和被3整除；

(6)被9整除的數(shù)：數(shù)字和被9整除；

(7)被11整除的數(shù)：奇數(shù)位數(shù)字和與偶數(shù)位數(shù)字和的差被11整除.

一個大于1的整數(shù)，如果它的約數(shù)只有兩個，即1與它本身，我們稱這樣的整數(shù)為質(zhì)數(shù);

如果它的約數(shù)的個數(shù)超過兩個，即它有不同于1與它本身的約數(shù)，我們稱這樣的整數(shù)為合

'質(zhì)數(shù)

數(shù).正整數(shù)可分為質(zhì)數(shù)、合數(shù)和1三類，即正整數(shù)|合數(shù)

應(yīng)注意：1既不是質(zhì)數(shù)，也不是合數(shù)，它是異于質(zhì)數(shù)與合數(shù)的一類.我們也稱它為單位.

質(zhì)數(shù)與合數(shù)有下面常用的性質(zhì)：

(1)質(zhì)數(shù)有無數(shù)多個.

(2)2是惟一的既是質(zhì)數(shù)，又是偶數(shù)的整數(shù)，即是惟一的偶質(zhì)數(shù).大于2的質(zhì)數(shù)必為

奇數(shù).

(3)若質(zhì)數(shù)p|a?b,則必有p|a或p|b.

(4)若正整數(shù)a、b的積是質(zhì)數(shù)p,則必有a=p或b=p.

(5)惟一分解定理：任何整數(shù)n(n>l)可以惟一地分解為：n=pfprpF，其中

P\<P2<<P?是質(zhì)數(shù)，叫，。2，%是正整數(shù).

例題

例1：證明：形如出?ca兒的六位數(shù)一定被7,11,13整除.

證明：abcabc=aX105+bX104+cX103+aX102+bX10+c

=aX(105+102)+bX(104+10)+cX(103+l)

=102aX(l^+l)+10bX(103+l)+cX(103+l)

=(103+l)X(102a+10b+c)

=1001X(WOa+lOb+c)

=7XHX13X(lOOa+lOb+c)

由此可見，abcabc7,11,13整除.

例2：寫出都是合數(shù)的13個連續(xù)自然數(shù).

解：方法一直接尋找

從2開始，在自然數(shù)2,3,4,5,6…中把質(zhì)數(shù)全部劃去，若劃去的兩個質(zhì)數(shù)之間的自然數(shù)

個數(shù)不小于13個，則從中取13個連續(xù)的自然數(shù)，就是符合要求的一組解，例如：自然數(shù)

114,115,116,…126就是符合題意的一組解.

方法二構(gòu)造法

我們知道，若一個自然數(shù)a是2的倍數(shù)，則a+2也是2的倍數(shù)，若a是3的倍數(shù)，則a+3

也是3的倍數(shù)，……若a是14的倍數(shù)，則a+14也是14的倍數(shù)，所以只要取a為2,3,…

14的倍數(shù),則a+2,a+3,…，a+14分別為2,3,……,14的倍數(shù),從而它們是13個

連續(xù)的自然數(shù).

所以，取a=2X3X4X…X14,則a+2,a+3,…，a+14必為13個都是合數(shù)的連續(xù)

的自然數(shù).

說明方法二可以推廣，同學(xué)們不妨自己一試.

例3：設(shè)%,a2,6999是L2,…，1999的任意一個排列，試證明：(/—1)((z2—

2)…(4999—1999)必為偶數(shù).

證明：1,2,…，1999中奇數(shù)比偶數(shù)多1個，因此q,生，…，即)99中奇數(shù)也比偶數(shù)多

1個.這樣，在4,%,…，4999這些數(shù)中至少有1個奇數(shù)，相應(yīng)的差%—1，”3—3,…，

?！本樢?999中至少有1個是奇數(shù)減去奇數(shù)，因而這差是偶數(shù).從而(%—1)(%—2)…

(6999—1999)是偶數(shù).

練習(xí)：能否找到a,b《N,使得：。2=2002+〃

例4：若n為正整數(shù)，n+3與n+7都是質(zhì)數(shù)，求n除以3所得的余數(shù).

解：我們知道，n除以3所得的余數(shù)只可能為0、1、2三種.

若余數(shù)為0，即n=3k(k是一個非負(fù)整數(shù)，下同)，則n+3=3k+3=3(k+1),

所以3|n+3,又3Wn+3,故n+3不是質(zhì)數(shù)，與題設(shè)矛盾.

若余數(shù)為2,即n=3k+2,則n+7=3k+2+7=3(k+3),

故3|n+7,n+7不是質(zhì)數(shù)，與題設(shè)矛盾.

所以，n除以3所得的余數(shù)只能為1.

如果nGZ+,n+3和n+7均為質(zhì)數(shù)，求n除以3所得余數(shù).

例5：設(shè)々與的是任意兩個大于3的質(zhì)數(shù)，2=〃：一1,%=而一1,乂與乂的最大公

約數(shù)至少為多少？

解：因為々是大于3的質(zhì)數(shù)，所以為不是3的倍數(shù)且々是奇數(shù)，因為々不是3的倍數(shù)，

所以〃I=3k+l或〃?=3k+2(k為正整數(shù)).

當(dāng)々=3k+l時，nj2-l=(3k+l)2—l=9k2+6k+l-l=3(3k2+2k),故3|〃；一1.

當(dāng)〃i=3k+2時,-l=(3k+2)2-l=9k2+12k+4-l=3(3k2+4k+l),故

又因為勺是奇數(shù)，所以"]=2k+l.從而〃；一1=(2k+l)2—l=4k?+4k+l—l=4k(k+l)

又因為k與k+l是連續(xù)的整數(shù)，所以21k(k+1),814k(k+1)即8|〃；-1

由于3與8互質(zhì)，故24|〃；一1.

同理24|〃；-1.

另外，取”1=5,則〃：-1=24.

綜上所述，M與的最大公約數(shù)至少為24.

說明從上述例題中，我們得到兩個有用的結(jié)論：

(1)若n不是3的倍數(shù)，則〃2除以3的余數(shù)為1.

(2)若n是奇數(shù)，則”2除以8的余數(shù)為1.

設(shè)々與〃2是任意兩個大于3的質(zhì)數(shù)，乂=〃；-1,愀=〃；一1,M與愀的最大公約數(shù)

至少為多少？

例6：設(shè)自然數(shù)%>%，且有〃；一延=79,試求々與〃2的值?

解：由題意：一〃;=(/+%)(%—%)=79.

因為々，九2是整數(shù)，故勺+生與々一公都是整數(shù)，而79是一個質(zhì)數(shù)，由質(zhì)數(shù)的性質(zhì)，且

%+2=79

注意到々+%>%—〃2，有〈，不難解得％=40,n1=39.

"一%二]

設(shè)可>〃2，且%，且有>=79,試求分與〃2的值,

例7：p>2,p是質(zhì)數(shù)，若l+'+」H------1-----------F—--=—,證明：p\a.

23p-2p-\b

證明:1H-------------------------

pT

因此，1+工1111

+—+??,+-+???+-----------1-----------

23p-2p-\

)

=r^+需巧+T目;運

2''2'

=P，M,

1-2-3."-2)(。一1)

其中M=2?3(p—2)+1-3-4(p—3)(p—1)+…+1?2?…23)(-"；)...(p—]).

因為p>2,p為質(zhì)數(shù)，所以p與1、2、…、p—1都互質(zhì)，從而與分母1,2,3…?(p—1)互質(zhì).

因此約分后的分子中仍有因數(shù)P，亦即p|a.

說明本例仿照了高斯求和的辦法，將一頭一尾兩兩搭配，分組運算.方法非常巧妙.

另外，我們也常記1X2X3X…Xn為n!,因而上面的1X2X3X…X(p—1)也可記為(p-1)!,

由上面的證明過程，我們有：當(dāng)p為質(zhì)數(shù)時，p不能整除(p—l)!,從而p與6—1)!互質(zhì).

例8：99個連續(xù)自然數(shù)之和等于abed,若a、b、c、d皆為質(zhì)數(shù)，則a+b+c+d的最小值等

于多少？

解不妨設(shè)最小自然數(shù)為x,則有

x+(x+1)H------F(x+98)=abcd

99x+(1+2H------1-98)=abcd

99x+99X49=abed

99(x+49)=abcd

3X3XllX(x+49)=abcd

：a、b、c、d為質(zhì)數(shù)，

?*.x4-49也為質(zhì)數(shù)，貝ijx=4.

即a+b+c+d=3+3+ll+53=70.

99個連續(xù)自然數(shù)之和等于abed,若a、b、c、d皆為質(zhì)數(shù)，則a+b+c+d的最小值等于多

少？

例%設(shè)n是滿足下列條件的最小正整數(shù)，它們是75的倍數(shù)且恰有75個正整數(shù)因子(包括1

和本身)，求2.(美國第八屆數(shù)學(xué)邀請賽試題)

75

解：由條件知，n=75k=3X5?k(k為正整數(shù)).

欲使n盡可能小，可設(shè)『Z-Qy(Y》2,8為)，且有(a+1)(B+1)(丫+1)=75.

由奇偶性質(zhì)得a+1,B+l,Y+1都為奇數(shù)，所以a、B、丫都是偶數(shù)，故丫=2.

由(a+D(6+1)(Y+1)=75得

(a+1)(6+1)=25

1)a+1=5,P+1=5,a=4,B=4,

An=24-34-52

2)a+1=1,B+1=25,，a=0,0=24

.,.n=2°-324-52

由上可得最小的正整數(shù)n是24,34?52.

例10：甲、乙、丙三個數(shù)分別是312,270,211.用自然數(shù)A分別去除這三個數(shù)，除

甲所得余數(shù)是乙所得余數(shù)的2倍，除乙所得余數(shù)是除丙所得余數(shù)的2倍，求這個自然數(shù)A

(99年天津市初二數(shù)學(xué)決賽題)

分析：若設(shè)丙的余數(shù)為r,商分別為a,b,c,則可得方程組，再利用整數(shù)性質(zhì)即可求出A.

①

‘312==A-d!+4r

②

解：依題意有＜270=二A?/7+2r

③

211==A-c+r

2X②一①得：2X270—312=A(2b-a)=228=22X3X19

2X③一②得：2X211—270=A(2c-b)=23X19=152

：A是228、152的公因數(shù)，

，A=2,4,19,38,76.

經(jīng)檢驗19合乎題意，即A=19.

例11：若p或p+2都是大于3的質(zhì)數(shù)，求證：6|(p+1).(第五屆“希望杯”賽題)

解題關(guān)鍵：注意到p,p+1,p+2是連續(xù)的整數(shù)，利用連續(xù)整數(shù)乘積法.

解：因p,p+1,p+2為三個連續(xù)整數(shù)，

所以1X2X3|p(p+l)(p+2).

又因p,p+2為大于3的質(zhì)數(shù)，

所以2Op,20(p+2),3dp,3。(p+2).

故2|(p+l),3|(p+l).

又(2,3)=1,

因此2X3|(p+1),即6|(p+1).

練習(xí)：已知p是大于3的質(zhì)數(shù)，求證：24|(p2-1).

解題關(guān)鍵：要證明24|(p2-1),轉(zhuǎn)化為證明3|(p2-1),且8|(p2-1).今p是大于3

的質(zhì)數(shù)，則p一定是奇數(shù).將質(zhì)數(shù)p分類進行討論.

證明：因p為大于3的質(zhì)數(shù)，故p為奇數(shù).

設(shè)p=2n+l(n為大于1的整數(shù))，則

p_11—(p+1)(p—1)—(2n+2)12n=4n(n+1).

又21n(n+1),故814n(n+1).

下面證明3|(p2-1).

因p為整數(shù)，故可按被3除的余數(shù)進行分類，寫成3m,3m+l,3m+2(m為正整數(shù))三

種形式.

又p為大于3的質(zhì)數(shù)，所以p=3m+1或3m+2.

當(dāng)p=