第十一講高中數(shù)學(xué)競(jìng)賽考點(diǎn)初等數(shù)論

第十一講高中數(shù)學(xué)競(jìng)賽考點(diǎn)初等數(shù)論

前言

數(shù)論是關(guān)于數(shù)的學(xué)問，主要研究整數(shù)，重點(diǎn)對(duì)象是正整數(shù)，對(duì)中學(xué)生可以說，數(shù)論是研

究正整數(shù)的一個(gè)數(shù)學(xué)分支.

數(shù)論素有“數(shù)學(xué)皇后”的美稱。由于其形式簡(jiǎn)單，意義明確，所用知識(shí)不多而富于技巧

性，千姿百態(tài)，靈活多樣。有人曾說：“用以發(fā)現(xiàn)數(shù)學(xué)天才，在初等數(shù)學(xué)中再也沒有比數(shù)論

更好的課程了?！币虼嗽趪?guó)內(nèi)外數(shù)學(xué)競(jìng)賽中，幾乎都離不開數(shù)論問題，使之成為競(jìng)賽數(shù)學(xué)的

一大重要內(nèi)容。

事實(shí)上，數(shù)論是博大精深的，數(shù)論題也是層出不窮的。在各種層次的競(jìng)賽中，數(shù)論題的

難度設(shè)置也不相同，因全國(guó)聯(lián)賽的規(guī)模最大，也是國(guó)內(nèi)最為正式的數(shù)學(xué)競(jìng)賽之一，所以我主

要以全國(guó)聯(lián)賽的要求作以下整理和分析。

一、考試說明考情解讀

1.考試說明

在高中數(shù)學(xué)全國(guó)聯(lián)賽的考試大綱中，對(duì)全國(guó)聯(lián)賽中數(shù)論所列的數(shù)論基礎(chǔ)知識(shí)有：整數(shù),

整除，同余，素?cái)?shù)，合數(shù)，完全剩余類，高斯函數(shù)，不定方程，p進(jìn)制進(jìn)位制，Pell方程;

重要定理有：算術(shù)基本定理，費(fèi)馬小定理，歐拉定理，拉格朗日定理，威爾遜定理，裴蜀定

理，中國(guó)剩余定理。

整除，同余是數(shù)論的基礎(chǔ)，定理是解題的重要工具，全國(guó)聯(lián)賽的數(shù)論題往往需要靈活的

運(yùn)用定理來解決。

2.考情解讀

對(duì)2010-2017年全國(guó)數(shù)學(xué)聯(lián)賽試題進(jìn)行統(tǒng)計(jì)分析，全國(guó)聯(lián)賽中一般會(huì)出現(xiàn)一道填空題

和一道解答題，從近三年的試題設(shè)置來看，數(shù)論不管是填空題還是二試解答題都出現(xiàn)在最后

一題，以壓軸題的身份出現(xiàn)，并且難度也在加大，所以在全國(guó)聯(lián)賽中要取得好成績(jī)，數(shù)論是

學(xué)習(xí)的重點(diǎn)。

在近8年的全國(guó)聯(lián)賽中出現(xiàn)的題型主要有7類：約數(shù)與倍數(shù)、素?cái)?shù)與合數(shù)：平方數(shù)；

整除；同余；不定方程；數(shù)論函數(shù)、［x］高斯函數(shù)、°(〃)歐拉函數(shù)；進(jìn)位制(十進(jìn)制、二

進(jìn)制).我制作統(tǒng)計(jì)表如下:

題型約數(shù)與倍數(shù)、平方數(shù)整除不定方程數(shù)論函數(shù)進(jìn)位制同余

素?cái)?shù)與合數(shù)

大、小題填解J真解填解填解填解填解填解

2010

2011V

2012

2013

2014

2015

2016V

2017V

從上表可以看出，每年考試的著點(diǎn)都在變化，規(guī)律性很小，但每年著重考察的點(diǎn)都比較

專注。所以要在全國(guó)聯(lián)賽中解答數(shù)論問題，還需要我們對(duì)數(shù)論的全盤的學(xué)習(xí)到位。

二、考試目標(biāo)考點(diǎn)解析

重視數(shù)學(xué)能力的數(shù)學(xué)競(jìng)賽，已經(jīng)廣泛采用數(shù)論題目，是數(shù)學(xué)競(jìng)賽四大支柱之一，四大柱

是：代數(shù)，幾何，初等數(shù)論，組合初步(俗稱代數(shù)題、幾何題、算術(shù)題和智力題).高中競(jìng)

賽加試四道題正好是四大模塊各一題，分別是幾何題、代數(shù)題、數(shù)論題、組合題，一試中也

會(huì)有數(shù)論題.數(shù)論受到數(shù)學(xué)競(jìng)賽的青睞可能還有一個(gè)技術(shù)上的原因，就是它能方便地提供從

小學(xué)到大學(xué)各個(gè)層面的、新鮮而有趣的題目.

數(shù)學(xué)競(jìng)賽中常常出現(xiàn)初等數(shù)論問題。這類問題，利用極少的知識(shí)，生出無窮的變化，千

姿百態(tài)，靈活多樣。下面從六個(gè)方面來了解初等數(shù)論。

目標(biāo)一基礎(chǔ)知識(shí)

競(jìng)賽大綱中數(shù)論的基礎(chǔ)知識(shí)點(diǎn)有：整數(shù)，整除，同余，素?cái)?shù)，合數(shù)，完全剩余類，高

斯函數(shù)，不定方程，p進(jìn)制進(jìn)位制，Pell方程。其中整數(shù)，整除，同余，素?cái)?shù)，合數(shù)，高

斯函數(shù)在省預(yù)賽、高中聯(lián)賽常出現(xiàn)在小題即填空題中，而完全剩余類、不定方程、p進(jìn)制進(jìn)

位制的問題如果出現(xiàn)在填空題中往往會(huì)在最后兩題，至于Pell方程基本上是出現(xiàn)在二試中，

而且Pell方程的出現(xiàn)，一般難度比較大，Pell方程屬于比較偏的知識(shí)點(diǎn)。

例L(16全國(guó)高中數(shù)學(xué)聯(lián)賽江西省預(yù)賽)

等差數(shù)列2,5,8,…,2015與4,9,14,…,2014的公共項(xiàng)(具有相同數(shù)值的項(xiàng))的個(gè)數(shù)是.答

案：134.

解：將兩個(gè)數(shù)列中的各項(xiàng)都加1,則問題等價(jià)于求

等差數(shù)列3,6,9,…,2016與等差數(shù)列5,10,15,…,2015

的公共項(xiàng)個(gè)數(shù)；前者是M={1,2,3,…,2016}

中的全體能被3整除的數(shù)，

后者是〃中的全體能被5整除的數(shù)，

故公共項(xiàng)是M中的全體能被15整除的數(shù)，

這種數(shù)有—=134個(gè).

L15J

【點(diǎn)評(píng)】在全國(guó)聯(lián)賽一試小題中數(shù)論題目常常出現(xiàn)，難度不大，往往會(huì)對(duì)題目進(jìn)

行偽裝，需要一些技巧把問題的本質(zhì)呈現(xiàn)出來。對(duì)于考察的內(nèi)容有，整數(shù)的一些

基本性質(zhì)：整除、公約數(shù)、公倍數(shù)……。對(duì)于本題而言，需要觀察到兩個(gè)數(shù)列的

特性，運(yùn)用整除的性質(zhì)和高斯函數(shù)即可得到解決。

例2.(15國(guó)高中數(shù)學(xué)聯(lián)賽江西省預(yù)賽)

將1,2,3,4,5,6,7,8的每一個(gè)全排列皆看成一個(gè)八位數(shù)，則其中是11倍數(shù)的八位數(shù)的個(gè)數(shù)為

解：對(duì)于每個(gè)這樣的八位數(shù)4%…@,記A={q,a3M5，/}，3={42，。4，。6，4}，

而S(A),S(B)表示其數(shù)字和,先設(shè)S(A)25(B),則S(A)+S(B)=36,故S(A),S(B)

同奇偶，且S(A)+S(B)與S(A)-5(B)同奇偶，因此S(A)-S(B)為偶數(shù),且是11的倍數(shù);

如果S(A)-S(B)=22,則S(5)=7,這不可能(因最小四數(shù)之和不小于10)；于是

S(A)—S(B)=0,即有S(A)=S(3)=18,考慮9所在的組，另三數(shù)只有三種情況：

{6,2,1},{5,3,1}與{4,3,2},當(dāng)一組數(shù)確定后，另一組數(shù)隨之唯一確定.再考慮9在奇

數(shù)數(shù)位或偶數(shù)數(shù)位情況，于是得到2x3x4!x4!=3456個(gè)這種八位數(shù).

【點(diǎn)評(píng)】當(dāng)然數(shù)論小題不是都簡(jiǎn)單，比如這道題，雖然考察的內(nèi)容是基本的。如果直接用組

合計(jì)數(shù)解決，討論的情況會(huì)比較復(fù)雜，而且討論的方向并不凸顯，這樣解決此題就比較困難；

如果運(yùn)用數(shù)論中數(shù)的進(jìn)制和整除的知識(shí)，進(jìn)而轉(zhuǎn)化為奇偶數(shù)的討論，對(duì)各數(shù)位上數(shù)字進(jìn)行分

類求和討論，這樣把所要討論的情況大大縮小，并且解決此題的路徑就清晰呈現(xiàn)出來，而后

對(duì)所有可能的情況依次討論就可解決問題。

目標(biāo)二基本技能

對(duì)于數(shù)論的學(xué)習(xí)中，基本技能是指對(duì)奇數(shù)、偶數(shù)、素?cái)?shù)、合數(shù)、平方數(shù)的性質(zhì)有比較深刻的

理解。通過運(yùn)用不等式估計(jì)法、數(shù)學(xué)實(shí)驗(yàn)等方法減小所要研究的數(shù)的范圍，從而得到所求結(jié)

果。

例3.求所有的3<x<200(xeZ),使得%2+(%+1)2為完全平方數(shù).

解：設(shè)f+(x+i)2=y2.由(x,x+i)=],利用勾股方程的通解公式

x=a1-b2x+1=a1-b2

得：＜x+1=lab,或，x=lab

y-a'+b1y=a2+b2

其中，a〉b〉0,且奇一偶，=

(I)由前一方程組得

b~+2ab-a1=l=(a—=2b~—1.由x+1=2ab,得

逐一驗(yàn)證，知。=2,。=12,》=119滿足條件.

(2)由后一方程組得

a2—2ab—b2=1=>(a—Z?)'=2M+1.由x—2ab,得

逐一驗(yàn)證，知人=2,a=5,x=20滿足條件.

綜上，x=119或20.

【點(diǎn)評(píng)】此題為不定方程的問題，不定方程是數(shù)論試題中常見題型。此題運(yùn)用不等式估

計(jì)的方法，這是處理不定方程的常用方法。通過對(duì)所考察量的放大、縮小得到未知數(shù)取

值條件的不等式，解這些不等式就得到未知數(shù)取值范圍，從而達(dá)到求解目的。

本題一眼看去視乎有很多解，所以必須分析出解的形式或情形。本題的解決方案為

先設(shè)法限定所求值在某一較小的范圍，再對(duì)范圍內(nèi)的整數(shù)逐一檢驗(yàn)而后得到所求結(jié)果.

次種做法看似呆板，但很有效果。

目標(biāo)三思想方法

數(shù)學(xué)競(jìng)賽中常用的方法有：同余法、構(gòu)造法、無窮遞降法、反證法、數(shù)學(xué)歸納法、不等

式估計(jì)法、配方法，因式分解法。

重要定理有：算術(shù)基本定理，費(fèi)馬小定理，歐拉定理，拉格朗日定理，威爾遜定理，裴

蜀定理，中國(guó)剩余定理。找準(zhǔn)所要運(yùn)用的定理，靈活運(yùn)用方法技巧，才能比較好的解決問題。

例4.(2012,全國(guó)高中數(shù)學(xué)聯(lián)賽)

試證明：集合A={2,22,2)..}滿足下列性質(zhì)：

(1)對(duì)于任意的aeA力eZ+，若匕<2a—1,則80+1)不為2。的倍數(shù)；

(2)對(duì)于任意的aeZ+/A,且awl,存在匕eZ+，h<2a-\,

使得Mb+1)為2a為倍數(shù).

解：(1)對(duì)于任意的awA,設(shè)a=2"(%￡Z.).假設(shè)可。+1)為2a為倍數(shù).則2a卜0+1).

由反。+1一奇一偶，且2。為2哥，知2d〃或24(/?+1),即或2a+1,與

Z?<2a-1矛盾.

(2)設(shè)a=2'q(/eN均為正奇數(shù)，且4>1).則2a=2"%.

由(2R,q)=1,貝ij1x2/+|,2x2/+|,3x2/+|,……,qx2/+|構(gòu)成模q的完全剩余系,即存在

\<i<q(iGZ+),使得2"■=l(modfy).顯然，i/q,令Z?=2，，—1<2a-l.

則2,+1k(人+1).又2*i三1(modq),q|(2/+lz-1),即q也(/?+1),結(jié)合(2*,q)=1,

得2aMe+1).

【點(diǎn)評(píng)】此題在當(dāng)年聯(lián)賽題為第二題，難度不算很大，但有一定的思維靈活要求。從

考查數(shù)論的基本知識(shí)、基本方法的角度說，本題是一道很好的綜合考察題。

其中運(yùn)用的反證法、構(gòu)造法是解決數(shù)論問題常用的辦法也是很有效的辦法.

例5.(2006國(guó)家集訓(xùn)隊(duì)測(cè)試題)

求所有的正整數(shù)對(duì)(a,")，使得n|(a+l)"-a"

證法一：首先易知(a,〃)=(a,l)是滿足要求的，

當(dāng)〃22時(shí)，易知〃為奇數(shù)且(〃,a)=(〃,a+l)=l,由條件：

(a+1)"三a"(mod〃)...........①

因?yàn)?a,n)=l,

由裴蜀定理，存在mGN+，使得。+1三%(mod〃)，

所以(a+1)"三"a"(mod”)......②，

由①，②得a"三m"a"(mod〃).

又(優(yōu),〃)=1,所以小三1(171041〃)，

設(shè)p是〃的最小質(zhì)因數(shù),所以(〃,p—1)=1,所以p\m-\.

所以Q+1三Qm三々(mod/?).所以矛盾！

綜上所述滿足要求的(〃,〃)為(4,1)(〃GN).

證法二：當(dāng)〃22時(shí)，，設(shè)p為〃的最小質(zhì)因數(shù)，

貝ij(〃,〃一1)=1,由裴蜀定理

存在〃,uwN+，滿足力〃一(p-l)u=l,

又p[(Q+l)〃_〃〃，所以p[(Q+l)〃"

即p(a+l)"f陽(yáng)—

又由費(fèi)馬小定理(a+l)z三三l(mod〃)，

所以由①知p|(a+l)-a矛盾!

所以〃=1.

綜上所述滿足要求的(。,“)為(a,l)(?e牝).

【點(diǎn)評(píng)】本題題干簡(jiǎn)明，實(shí)則對(duì)思維的要求比較高，在茫茫的定義、定理中尋求有效的解

決途徑是不容易的，本題想到用裴蜀定理找到突破口是關(guān)鍵，而后觀察到本題本質(zhì)是指數(shù)型

數(shù)問題，很有可能是費(fèi)馬小定理的運(yùn)用，通過嘗試，此思路是正確的。

目標(biāo)四靈活運(yùn)用

數(shù)論知識(shí)的靈活運(yùn)用關(guān)鍵在于知識(shí)點(diǎn)的串通，以及處理方法的精確選擇。

例6.(第八屆東南地區(qū)數(shù)學(xué)競(jìng)賽)

對(duì)正合數(shù)〃，記/(〃)為其最小的三個(gè)正約數(shù)之和，g(〃)為其最大的兩個(gè)正約數(shù)之和.

求所有的正合數(shù)〃，使得g(〃)等于/(〃)的某個(gè)正整數(shù)次基.

解法一若〃是奇數(shù)，則〃的一切約數(shù)都是奇數(shù)，故由題意知/(〃)為奇數(shù)，

g(〃)為偶數(shù)，這樣g(“)不可能等于/(〃)的某個(gè)正整數(shù)次辱.因此只需考慮幾

；7

是偶數(shù)的情況，此時(shí)1,2是〃最小的兩個(gè)正約數(shù)，〃，,是“最大的兩個(gè)正約數(shù).

2

設(shè)d是"除1,2以外的最小正約數(shù).若存在左eN*使g(〃)=—(〃)，

則J=(l+2+d)*=(3+d)?m/(mod3).由于二顯然是3的倍數(shù)，故3|#,

22

即3|4,由〃的最小性知d=3.因此解得〃=4X6&T,又3|〃，故其中Z22.

綜上可知，〃的所有可能值為〃=4x6,(/eN*).

解法二設(shè)合數(shù)〃滿足g(，?)=/?(〃)(AeN*),并設(shè)〃的最小素因子為p,

則〃的第二大正約數(shù)為2.若〃的第三小正約數(shù)為〃2,則=eZ,此時(shí)

PP'

77n,

/(?)=1+p+p2si(modp),g(〃)-n+—=p(l+/?)?—z-(modp),

PP-

從而/三/(〃)=g(〃)三O(modp),矛盾.因此〃的第三小正約數(shù)不是

從而必為某一素?cái)?shù)易知此時(shí)——￡Z,故有

pq

/(〃)=1+p+q三］+p(modq),g(n)-n-\——=q(l+p)---(modq).

ppq

因此(1+p)k=/A(n)=g(n)s0(modq).

又4為素?cái)?shù)，故4|l+〃，從而p<qWl+〃，只有〃=2,q=3.此時(shí)有

6*=/"“)=g(〃)=j〃，解得〃=4X6&T,又3|〃，故其中上22.

綜上可知，ii的所有可能值為〃=4x6/(/eN*).

【點(diǎn)評(píng)】此題是數(shù)論與函數(shù)結(jié)合的問題，主要考查整除和同余，整除和同余是高中數(shù)學(xué)

競(jìng)賽數(shù)論問題的重要問題，處理這類問題往往需要嚴(yán)格的邏輯推理，而不在于繁瑣的代數(shù)運(yùn)

算。

本題給出的兩種解決方法一個(gè)是直接法，另一個(gè)是間接法。直接法需要準(zhǔn)確的找到突破

口，這是不容易的，一旦找出問題就會(huì)很快解決；間接法總是運(yùn)用迂回戰(zhàn)術(shù)，構(gòu)造是常用的

思想。這兩個(gè)解題的方法都是對(duì)約數(shù)的靈活討論，大有“四兩撥千斤”的功效。

目標(biāo)五創(chuàng)新能力

數(shù)論問題不僅在高中數(shù)學(xué)競(jìng)賽中經(jīng)常出現(xiàn)，而且在北京大學(xué)、清華大學(xué)等著名高校的數(shù)

學(xué)夏令營(yíng)、金秋營(yíng)中也經(jīng)常涉及數(shù)論的基礎(chǔ)知識(shí)和思想方法.數(shù)論問題的包容性很大，它可

以包容很多其他數(shù)學(xué)分支知識(shí)，這個(gè)對(duì)學(xué)生的創(chuàng)新能力的考察是很直接的。

數(shù)論與遞推數(shù)列的結(jié)合是各種數(shù)學(xué)競(jìng)賽中的熱點(diǎn)，此類問題也是經(jīng)常會(huì)讓人耳目一新。

例7.(2016,北京大學(xué)數(shù)學(xué)科學(xué)夏令營(yíng)初賽)

給定正整數(shù)p,q,定義數(shù)列{q}:

證明：對(duì)任意正整數(shù)加,〃，均有（品，4）=%”,,）的.充分必要條件為p=l.

證明：必要性.

簡(jiǎn)單計(jì)算易知=P+q,%=/+pq+q,（生,。4）=%,4）=1?于是，（P，4）=L

又4=pa5+眄=3+q）a4+pq4,由（《，生）=4，

得（4，%）=（（〃2+4”4，。3）=（〃2+4嗎）=（"2_p，〃+<7）=P+q

而（p+q,p）=l,（p+g）Kp-l）,顯然，p-l<p+4,則只能p-1=0,即p=1.

充分性.若p=l,則當(dāng)加=〃時(shí)，結(jié)論顯然成立.

若m>n,設(shè)左=加一〃，則an+k=a”,.注意到，

由于（4，a“+J=l，貝|」（%，%）=-=（4，4）=1?

故（q4+i，4,）=（%，凡）=（%+?，凡）?又%“,“）=%+《”）=%:,

因此，%,"）=（%4）?

綜上，命題成立.

【點(diǎn)評(píng)】本題運(yùn)用了數(shù)學(xué)實(shí)驗(yàn)的思想方法，對(duì)于數(shù)學(xué)競(jìng)賽問題，數(shù)學(xué)實(shí)驗(yàn)是一種較好的

思想方法，這樣不僅可以認(rèn)識(shí)問題的本質(zhì)，還可以探索問題的解題思路。

與數(shù)論有關(guān)的數(shù)列問題.先通過數(shù)學(xué)實(shí)驗(yàn)證明必要性,再模仿斐波那契數(shù)列

（耳“，工）=%,“）的證明過程，完成充分性的證明?

目標(biāo)六壓軸例題

近三年的高中聯(lián)賽二試壓軸題都為數(shù)論題，而且難度是比較大的。由此看來數(shù)論題在全

國(guó)聯(lián)賽中的地位是很高的。正是因?yàn)閿?shù)論的內(nèi)容包容性大、解題技巧性要求高、思維要求靈

活，對(duì)學(xué)生的能力的考察很直接，所以得到出題者的青睞。要解決此類題對(duì)學(xué)生的綜合素養(yǎng)

要求比較高。

例&（2016年全國(guó)數(shù)學(xué)競(jìng)賽二試第四題）

設(shè)p與P+2均為素?cái)?shù)，p〉3.數(shù)列｛凡｝定義為

q=2,an=a“_1+［，'i］,〃=2,3,..

這里［x］表示不小于實(shí)數(shù)x的最小整數(shù).

證明：首先注意，｛4｝是整數(shù)數(shù)列.

對(duì)〃用數(shù)學(xué)歸納法.

當(dāng)〃=3時(shí)，

由條件知。2=〃+2，故〃。2+1=（〃+1）2.

因p與p+2均為素?cái)?shù)，且p〉3,故必須3加+1.

因此3|p%+l,即〃=3時(shí)結(jié)論成立.

對(duì)3cp-1,

設(shè)對(duì)左=3,…,成立gp%+l，此時(shí)|以=

故

PWT+1=〃a_+

k2k-yJJIk—\/k-\

故對(duì)3<〃W〃—1,有

2〃(P+Dc”

因此p4_]+1=

(p+〃)(p+2「

由此知(注意C；；+“是整數(shù))〃|(P+〃)(P+2)(W“T+1)?

因〃<p,p為素?cái)?shù)，故(〃,〃+〃)=(",〃)=1,

又p+2是大于〃的素?cái)?shù)，

故(〃卬+2)=1,從而r與(p+2)(p+〃)互素,

故由①知〃|pa“_i+L

由數(shù)學(xué)歸納法知，本題得證.

【點(diǎn)評(píng)】解決本題的重要思想方法是數(shù)學(xué)歸納法，數(shù)學(xué)歸納法在解決數(shù)學(xué)問題時(shí)是非常常

用的，也是非常有效的。而在解決問題時(shí)，方法的選擇是至關(guān)重要的。當(dāng)然作為壓軸題，它

不僅僅只是考察思想方法，它還對(duì)知識(shí)的理解深度，知識(shí)間的融會(huì)貫通由很高的要求。比如

本題我們還要對(duì)數(shù)論基本函數(shù)：高斯函數(shù)，數(shù)列遞推式，整除，互素等有較深的理解。

三、趨勢(shì)與展望

初等數(shù)論基礎(chǔ)知識(shí)比較簡(jiǎn)單，但是在處理問題方法技巧性很強(qiáng)，在培養(yǎng)人們思維能力的方

面起著重要作用，所以在國(guó)內(nèi)外數(shù)學(xué)競(jìng)賽中占有重要地位.數(shù)論的發(fā)展有著很長(zhǎng)的歷史，數(shù)論

以及思想又是競(jìng)賽數(shù)學(xué)中最重要的一部分，不管是小學(xué)數(shù)學(xué)競(jìng)賽，初中的數(shù)學(xué)競(jìng)賽，還是高中

的數(shù)學(xué)競(jìng)賽，或者IMO,數(shù)論思想都是重點(diǎn)。數(shù)學(xué)競(jìng)賽是當(dāng)前數(shù)學(xué)教育的重要組成部分，對(duì)學(xué)生

的數(shù)學(xué)思維提高起到了巨大地推動(dòng)作用。

在中學(xué)數(shù)學(xué)的學(xué)習(xí)中，初等數(shù)論知識(shí)常被廣泛應(yīng)