数学竞赛中的数论问题

数学竞赛中的数论问题

罗增儒

引言

数论的认识：数论是关于数的学问，主要研究整数，重点对象是正整数，对中学生可以说，数论是

研究正整数的一个数学分支.

什么是正整数呢？人们借助于“集合”和“后继”关系给正整数(当时也即自然数)作过本质的描

述，正整数1,2,3,…是这样一个集合

(1)有一个最小的数1.

(2)每一个数。的后面都有且只有一个后继数除1之外，每一个数的都是且只是一个数的后

继数.

这个结构很像数学归纳法，事实上，有这样的归纳公理：

(3)对N.的子集M,假设leM,且当awM时，有后继数〃‘EM,那么M=N,.

就是这么一个简单的数集，里面却有无穷无尽的奥秘，有的奥秘甚至使得人们疑心：人类的智慧还

没有成熟到解次它的程度.比方，哥德巴赫猜测：

1742年6月7日，普鲁士派往俄国的一位公使哥德巴赫写信给欧拉，提出“任何偶数，由4开始，

都可以表示为两个素数和的形式，任何奇数，由7开始，都可以表示为三个素数的和.后者是前者的推

论，也可独立证明(已解决).“表示为两个素数和的形式”就是著名的哥德巴赫猜测，简称1+1.

欧拉认为这是对的，但证不出来.

1900年希尔伯特将其归入23个问题中的第8个问题.

1966年陈景润证得：一个素数+素数x素数(1+2),至今仍无人超越.

・陈景润的数学教师沈元很重视利用名人、名言、名事去鼓励学生，他曾屡次在开讲时，说过这样

的话：“自然科学的皇后是数学，数学的皇冠是数论，哥德巴赫猜测那么是皇冠上的明珠.……”陈景

润就是由此而受到了后示和鼓励，展开了艰苦卓绝的终生奋斗和灿烂辉煌的奋斗终生，离摘4又“皇冠上

的明珠”仅一步之遥.

•数论题涉及的知识不是很多，但用不多的知识来解决问题往往就需要较强的能力和精明多的技

巧，有人说：用以发现数学人才，在初等数学中再也没有比数论教材更好的课程了.任何学生如能把当

今一本数论教材中的练习做出，就应当受到鼓励，劝他(她)将来去从事数学方面的工作(U.Dudley

《数论根底》前言).下面，是一个有趣的故事.

当代最高产的数学家厄尔多斯听说一个叫波萨(匈牙利，1948)的小男孩很聪明，就问了他一个问

题加以考察(1959)：如果你手头上有〃+1个正整数，这些正整数小于或等于2〃，那么你一定有一对

整数是互素的，你知道这是什么原因吗？

不到12岁的波萨只用了1分半钟，就给出了问题的解答.他将1〜2〃分成(1,2),(3,4),…,

共〃个抽屉，手头的，+1个正整数一定有两个属于同一抽屉，这两个数是相邻的正整数,

必定互素.

通过这个问题，厄尔多斯认定波萨是个难得的英才，就精心加以培养，不到两年，14岁的波萨就发

表了图论中“波萨定理”.

・重视数学能力的数学竞赛，已经广泛采用数论题目，是数学竞赛四大支柱之一，四大支柱是：代

数，几何，初等数论，组合初步(俗称代数题、几何题、算术题和智力题).高中竞赛加试四道题正好

是四大模块各一题，分别是几何题、代数题、数论题、组合题，一试中也会有数论题.数论受到数学竞

赛的青睐可能还有一个技术上的原因，就是它能方便地提供从小学到大学各个层面的、新鲜而有趣的题

R.

数论题的主要类型：在初中竞赛大纲中，数论的内容列有：十进制整数及表示方法；整除性，被2、

3、4、5、8、9、11等数整除的判定；素数和合数，最大公约数与最小公倍数；奇数和偶数，奇偶性分

析：带余除法和利用余数分类：完全平方数；因数分解的表示法，约数个数的计算：简单的一次不定

方程.

在高中竞赛大纲中，数论的内容列有：同余，欧几里得除法，装蜀定理，完全剩余类，二次剩余，

不定方程和方程组，高斯函数［1］，费马小定理，格点及其性质，无穷递降法，欧拉定理",孙子定理".

根据已出现的试题统计，中学数学竞赛中的数论问题的主要有8个重点类型：

(1)奇数与偶数(奇偶分析法、01法)；

(2)约数与倍数、素数与合数：

(3)平方数；

(4)整除;

(5)同余;

(6)不定方程；

(7)数论函数、［可高斯函数、0(〃)欧拉函数；

(8)进位制(十进制、二进制).

下面，我们首先介绍数论题的根本内容(10个定义、18条定理)，然后，对数学竞赛中的数论问题

作分类讲解.

第一讲数论题的根本内容

中学数学竞赛中的数论问题涉及的数论内容主要有10个定义、18条定理.

首先约定，本文中的字母均表示整数.

定义1(带余除法)给定整数见仇如果有整数小网)满足

a=qb+r,

那么g和厂分别称为。除以〃的商和余数.特别的，厂=（）时，那么称。被〃整除，记作可。，或者说。

是〃的倍数，而6是。的约数.（夕”的存在性由定理1证明）

定义2（最大公约数）设整数4,生，，勺中至少有一个不等于零，这〃个数的最大公约数是能

整除其中每一个整数的最大正整数，记作（q,%,,4）.

（%,%,,%）中的4没有顺序，最大公约数也称最大公因数.

简单性质：（4吗,伽同,，㈤）・

一个功能：可以把对整数的研究转化为对非负整数的研究.

定义3（最小公倍数）非零整数q,生，…的最小公倍数是能被其中每一个4。所整除

的最小正整数，记作［4,。,，

简单性质：如果攵是正整数。力的公倍数，那么存在正整数〃?使

证明假设不然，有攵=河。，0+厂（0<r<［t7,/?］）,曰仁［〃,句都是。/的公倍数得7•也是41

的公倍数，但（）<〃<［〃,句，与的最小性矛盾.故攵=闻。,句.

定义4如果整数。力满足（。力）=1,那么称。与〃是互素的（也称互质）.

定义5大十1且除1及其自身外没有别的止整数因子的止整数，称为素数（也称质数J.其余大

于1的正整数称为合数；数1既不是素数也不是合数.

定理1假设。力是两个整数，b>0,那么存在两个实数qj,使。=夕〃+厂（0工厂<〃），并且以〃

是唯一性.

证明1先证存在性.作序列

,—3b.—2b,—b,0,b,2b,3b,

那么。必在上述序列的某两项之间，从而存在一个整数q,使

qb£av（q+l）b,

即04。一qb<b,

取r=a-qb,0<r<b,

得a=qb+r,

即存在两个实数夕，厂，使〃一夕/?十厂（OK/・<〃）.

冉证唯一性.假设小唯一，那么同时存在多”与使

4=4力+/（0«q</?）,

a=q2b+r2（（）</;<b）,

相减([_/)〃=与一{，

%一%|〃=,_用<方，

。引4-％|<1，

但|%一%|为整数，故.一％|二0，得夕i=%，从而4=与.

注：如果取消0<rc〃，当厂<()或〃>〃，不保证唯一.

经典方法：紧扣定义，构造法证存在性，反证法证唯•性.

证明2只证存在性，用高斯记号，由

记r=q一”,故存在4一使

a=c/b+r(0<r<b).

证明3只证存在性，作集合

M={a-bx\x^Z,a-bx>0]

这是一个有下界的非空整数集，其中必有最小的，设x=g时，有最小值/上20)

a=qb+r.

再证尸《人，假设不然，r>b,记/=6+4，有

4=q/7+厂=q/7+(〃+4)=/?(〃+1)+彳

/；=4一/?(夕+1)GM

即M有4比，•更小，这与r为最小值矛盾.

故存在两个实数使。=4〃+40<〃<人).

定理2设。/,c是三个不全为0的整数，满足a=q/?+c,其中夕也为整数，那么(。3)=伍,。).

证明设4=｛。/的公约数｝,

B=｛b,c的公约数｝.

d\a_d\c=a-bq

'=dwB=AuB,

任取d£A=,d\b^

d\b

,d\bd\b

任取d£3=<=>=>d£A=BqA,

d\cd\a=bq+c

得A=B.

有4中元素的最大值=8中元素的最大值，即

(a,〃)=S，c).

注：这是辗转相除法求最大公约数的理论根底.

经典方法：要证明A=8,只需证AqB且

定理3对任意的正整数。力，有

证明因为出7是。功的公倍数，所以。力的最小公倍数也是C力的约数，存在q使

ab=q\ci,b\，

十[〃肉口[a,b]见击“她

有a=q-——i且1——1为整数，

bb

故4是。的约数.同理q是〃的约数，即q是的公约数.下面证明，q是。力的最大公约数.假设

不然，qv(a,b).有

cib=q\a,b\<(a,b)\a,b\.①

设攵/T，可见％是。的倍数，同样=，攵是〃的倍数，即k是出。

(〃,/?)(〃,/?)(a.b)(a,b)

的公倍数，那么存在正整数/〃但女=〃?[。,5|,有

-^—=ui[ayb]>[a,b],

得ab=q[a,b\>[a,Z?)[a,b\

与①矛盾，所以，q=(a,b),得证句.

ah

〜k(。力)q

注也可以由二厂司二R-二值同，得”(4/)，与4<(班)矛盾.

q

两步必=4。,可,"二(。力)々可以交换吗？

定理4b是两个不同时为0的整数，假设4%+与，0是形如QX+by(x,y是任意整数)的数中

的最小正数，那么

(1)axQ+by0ax+by；

(2)a7+瓯=(4〃).

证明(1)由带余除法有

ax+by=(q)+b)%+厂，0<r<ar0+by0,

得〃=a(x-/o)x+。(y-油〈”+by。,

知r也是形如以十力的非负数，但办o+b%是形如ar+外的数中的最小正数，故/*=0,即

ar0+by0\ax+by.

(2)由⑴有

ar0+by01a・l+b・0=a，

axQ+by0|a・0+b・l=b,

得aq+/?%是的公约数.另一方面，的每一个公约数都可以整除,所以也+打加是

。力的最大公约数,a0+"%=(〃,/?).

推论假设(。/)=1,那么存在整数型，使废+初=1.(很有用)

定理5互素的简单性质：

(1)(1,f/)=l.

(2)(〃,〃+1)=1.

(3)(2/1-1,2/?+1)=1.

(4)假设〃是一个素数，。是任意一个整数，且。不能被p整除，那么(a,p)=l.

证明因为(。,〃)|〃，所以，素数〃的约数只有两种川能：但〃不能被〃

整除，(a,p)wp，得“)=1.

推论假设〃是一个素数，。是任意一个整数，那么或(a,p)=〃.

(5)假设那么存在整数sj,使as+初=1.(定理4推论〕

(6)假设(a,b)=l,(a,c)=l,那么(a,〃c)=l.

证明由(。/)=1知存在整数s,1,使心+初=1.

有a(cs)+bct=c,

得加、)=(〃,c)=l.

(7)假设®b)=l,那么(a±b,a)=l,(a±b,b)=l,(a±b,ab)=l.

证明(a±〃,a)=(±Z?,a)=(〃M)=1,

(4±仇〃)=(4力)=1,

由⑹(a±b,ab)=\.

⑻假设(。力)=1,那么(，/〃)=1,其中〃〃为正整数.

证明据(6)，由(〃㈤=1可得(a、〃)=l.

同样，由(优")=1可得(a"〃)=1.

定理6设。是大于1的整数，那么4的除1之外的最小的正约数^必是素数，且当。是合数时，

q<4a.

证明用反证法,假设q不是素数，那么存在正整数数价，1</vq,使［|q,但q|a,故有名|。，

这与q是。的除1之外的最小正约数矛盾，故夕是素数.

当。是合数时，设a=那么。i也是。的一个正约数，由的最小性得夕wq，从而

2

q<a1q=a,开方得q£&i.

定理7素数有无穷多个，2是唯一的偶素数.

证明假设素数只有有限多个，记为8，生,…,〃〃，作一个新数

口=%・小•…・P“+1>L

假设〃为素数，那么与素数只有〃个Pi，〃2,…，〃〃矛盾.

假设〃为合数，那么必有化仪〃],%…，〃"}，使从而〃[1，又与P,>1矛盾.

综上所述，素数不能只有有限多个，所以素数有无穷多个.

2是素数，而大于2的偶数都是合数，所以2是唯一的偶素数.

注：这个证明中，包含着数学归纳法的早期因素：假设假设有〃个素数，便有〃+1个素数.(构造

法、反证法)秒

定理8(整除的性质〕整数通常指非零整数

(1)\\a,-1Rz；当。工0时，a\aftz|O.

⑵假设@a,awO,那么网《时;假设他，例>时,那么a=O;假设">0,且作用,

那么。=/?.

证明由awO,有a=bq,得同=怜同之例.

逆反命题成立“假设”a,网>同，那么。=0”；

由同工同且网引《得同=例，又或>0,得

(3)假设a+>=c+d,且e|a,e|6,e|c,那么e|d.

(4)假设c|〃，b\a,那么c|a.

证明(定义法)由c|〃，b\a,有

b=q}c,a=q2b,

得a=([%)，,

即布.

(5)假设c|a,那么。c]而.

(6)假没c|a,c\b,那么对任意整数/%〃，c\ma+nb.

证明(定义法)由c|a,c\b,有

a=q]c,b=q2c,

得ma+/?/?=(mq、+〃％)c，

即c\ma+nb.

⑺假设=且4仇?，那么dC.

证明由(。力)=1知存在整数S/，使4S+4=1,有

a(cs)+(〃(?)/=c,

因为a\bc,所以。整除等式的左边，进而整除等式的右边，即。卜.

注意不能由。忸。且。“2得出。上.如6|4x9,但6]4且6/9.

(8)假设(0力)=1,且*,*,那么曲|c.

证明由(。/)=1知存在整数$,/,使心+初=1,有

acs+bci=c,

又由a|c,〃|c有c=aqi，c=。%代入得

ab(q)s)+ab(q/)=c,

所以砌c.

注意不能由可。且@c得出如不能由6|30且10|3()得出6()|3().

19)假设a为素数，且《林，那么々M或a|c.

证明假设不然，那么且Q/C,由〃为素数得(a,〃)=l,(a,c)=l,由互素的性质(6)得

(tz,Z?c)=1,再由〃为素数得a|〃c,与4Z?c矛盾.

注意没有〃为素数，不能由白匠推出或〃卜.如l6|4x9,但6|4且6|9.

定义6对于整数。也c,且cwO,假设c|3-力，那么称。力关于模c同余，记作a三b(modc)；

假设。/(。一。)，那么称关于模c不同余，记作。壬伙mode).

定理9(同余的性质)设。,儿。,”,6为整数，相》(),

(1)假设。三伙mod/%)且b三c(mod〃2),那么。三c(mod〃i)；

证明由。三Z?(modm)且b三c(modm),有

a-b=mq]yb-c=mq2,

a-c=〃?(q+%),

得。三c(modm).

(2)假设a=/?(modm)且。三d(modm),那么〃+c三。+4(modm)且ac三/7a(mcxim).

证明由。三Z?(modin)且。三"(modin),有

a-b=，nq、,c-d=mq2,①

对①直接相加，有

(a+c)-(O+d)=m(Q+%)，

得a+c=b+d(n】odin).

对①分别乘以c/后相加，有

ac-hd=(^ac-be)-(be-bd^=tn^cqi+bq),

得ac=bd(mod/?t).

(3)假设。三〃(mod〃?)，那么对任意的正整数〃有a"=bn(modm)JSLan=bn(modmn).

(4)假设。三伏mod〃z),且对非零整数&有川那么£=工mod?.

KK\Ky

证明由。三Z?(modm)>,有

a=b+mg,

又有均为整数，目

abm

———i—q，

kkk

定理10设〃/为整数，〃为止整数，

(1)假设那么(4-6)|(."一力").

a"-bn=(a-3(a'i+an-2b+an-3b2++abn-2-bn-l).

(2)假设aw-/?,那么(〃+6)|(1小+/E).

〃2,1+一/-3〃+/1/----刈2〃-3+〃〃-2)

(3)假设"一匕，那么(〃+以«产—庐).

a211-b2n=（a+b）（a2n-l-a2n-2Z>+a2n-V+ab2n~2-b2'1'1）.

定义7设〃为正整数，%为大于2的正整数，q,令，，《“是小于人的非负整数，且可>。.假

设

n1

ti=a^k'+612km'+,,,+a,”_\k+cint,

那么称数a.a2ant为〃的左进制表示.

定理11给定整数々>2,对任意的正整数〃，都有唯一的々进制表示.如

-2

n=+a210"+...+am_x10+,0«qY9,q>0（10进制）

x,n2

n=a,T'-+a22-++-2+a,n.0<a.<l,a,>0]2进制）

定理12（算术根木定理）每个大于1的正整数都可分解为素数的乘积，而且不计因数的顺序时，

这种表示是唯一的

〃=P?P0…PB,

其中Pi<P2V…vP人为素数，%,％，…，%为正整数.（分解唯一'性）

证明1先证明，正整数〃可分解为素数的乘积

…I"?…1小①

如果大于1的正整数〃为素数，命题已成立.

当正整数〃为合数时，〃的正约数中必有一个最小的，记为〃「那么P1为素数，有

n=pial,\<ax<n.

如果4为素数，命题已成立.当外为合数时，4的最小正约数〃2为必为素数，有

n=Pi%=Pip2a2,1v%<4v〃♦

这个过程继续进行下去，由于〃为有限数，而每进行一步q就要变小一次，于是，经过有限次后，

比方加次，〃就变为素数的乘积

下面证明分解式是唯一的.假设〃还有另一个分解式

〃=②

那么有pm…Pm=q。…③

因为等式的右边能被4整除，所以左边也能被名整除，于是％整除由，〃2,中的某一个化，

但为素数，所以p,与卬相等：不妨设1入为Pi,有

Pl=Q.

把等式③两边约去Pl=0,得

P2P3…An=%%…%•

再重复上述步骤，又可得〃2二%,凸=%，…，直到等式某一边的因数被全部约完，这时，如果

另一边的因数没有约完，比方右边没有被约完(〃?〈/),那么有

i=—,q「④

但%+-/+2，，%均为素数，素数都大于1，有或+闯小2%>1，这说明等式④不可能成立，

两个分解式的因数必然被同时约完，即分解式是唯一的.

将分解式按P,的递增排列，并将相同的P,合并成指数形式，即得

-P\Pl…Pk«

其中P\<Pl<­•<〃人为素数，四乌,…,%为正整数.

证明2用第二数学归纳法证明

n=P\P丁

(1)当〃=2,因为2为素数，命题成立.

(2)假设命题对一切大于1而小于〃的正整数已成立.

这时，假设〃为素数，命题成立；假设〃不为素数，必存在。涉，使

n=ab,\<a<n,\<b<n,

由归纳假设，小于〃的。力可分解为素数的乘积

〃="+瓜+2•••"，P.2WP；+2£••4〃；，

得〃=〃；〃；•••P.Z'42，

适当调整〃；的顺序，可得命题对于正整数〃成立.

由数学归纳法，命题对一场大于1的正整数〃成立.

下面证明分解式是唯一的.假设〃的分解式不唯一，那么至少有两个分解式

n=PR…P,"，

"0%0，0工％«4％，

得P\P1Pm=q9・%•

有四I%％…0且"P/2…P”,，

这就存在?，/乙，使

〃|1%且51匕，

但Pi，4,%,Pj均为为素数,所以

Pi=%，/=Pj，

又Pi=4之1=Pj2%，

所以Pi=l.

把等式两边约去Pi=q「得

再重复上述步骤，又可得0=%，〃3=%，…，直到等式某一边的因数被全部约完，这时，如果

另一边的因数没有约完，比方右边没有被约完(m<r),那么有

1=-2,・%•

但。向，或+2,…，0均为素数，素数都大于1，有夕”用心+2…Z>1，这说明上述等式不可能成立，

两个分解式的因数必然被同时约完，即分解式是唯一的.

将分解式按P,的递增排列，并将相同的〃,•合并成指数形式，即得

其中P1<〃2<•••</〃为素数，%,。2,…，火为正整数.

定理13假设正整数〃的素数分解式为〃=〃：P2%…那么〃的正约数的个数为

d(〃)=(q+l)(%+l)…(4+1)，

"的一切正约数之和为

«1+，-1«2+,-1^+1_1

s(/?)=-/^7——L0n——-••…区n——-.

Pi—P2TP「1

证明对于正整数〃=〃/力2%..“J*,它的任意一个正约数可以表示为

m=p0p/】p/*,0</?,.<ai,①

由于A有0,1,2,…,冬共％十1种取值，据乘法原理得〃的约数的个数为

"（〃）=（《+1）（%+1）…（%+1）•

考虑乘积

+++2+

（Pi°+P；+,,+P/）（P2°P?',,Pz）4,,（/A°Pk+-+〃*）,

展开式的每一项都是〃的某一个约数（参见①），反之，〃的每一个约数都是展开式的某一项，于

是，〃的一切约数之和为

5（〃）=（〃i°+p；+,+〃/）…仇°+〃J+..+〃/）

=P”-1〃2叫〃尸-1

P「1〃2T0T

注构造法.

定义8（高斯函数〕对任意实数x,［可是不超过x的最大整数.亦称［司为x的整数局部，

［x］<X<［x］+1.

定理14在正整数〃!的素因子分解式中，素数〃作为因子出现的次数是

十・・・.

证明由于〃为素数，故在〃!中〃的次方数是1,2,•,〃多数中〃的次方数的总和（注意，假设"

不为素数，这句话不成立）.

在1,2,…，〃中，有-个p的倍数；在［彳个〃的倍数的因式中，有A个〃2的倍数；在A

Pp~.pP~

个〃2的倍数的因式中，有二个p'的倍数：…，如此下去，在正整数川的素因子分解式中，素数〃

_P.

作为因子出现的次数就为

升［升［孙,

注省略号其实是有限项之和.

画线示意50!中2的指数.

50!=2a'365/7%1P13勺7勺9%23%29.31・37・41.43.47

定理15（费玛小定理）如果素数〃不能整除整数。，那么〃|（。内一1）.

证明1考察下面的〃-1个等式：

a=pq、+r],0"v〃，

2a=pq2+r2,0<r2<p

=叫T+小，0，<P

由于素数p不能整除整数。，所以，p不能整除每个等式的左边，得小与,…，弓_|均不为0,只能

取1,2,…,p—1.下面证明不火各不相等.

假设不然，存在使

§a=pq卢q,

ta=pq,+rt,

IK

相减(s-i)a=p(q、-q)・

应有素数〃整除(S—但素数〃不能整除。，所以素数〃整除(S—。，然而由1WZCS《〃一1

可得

O<s-t<p-2<p,

要素数p整除(s—f)是不可能的，得不弓,各不相等.有

任小T・2・・(p-l)=(p-l)!.

再把上述〃-1个等式相乘，有

(〃-1叱=坳+柏・%，

即(〃_|)!小=帅+(〃—1)!,

其中M是一个整数.

亦即(〃_1)!(屋Z_1)=帅.

由于〃是素数，不能整除(〃一1)!,所以素数〃整除。川一1,得证

H"i)

证明2改证等价命题：如果素数〃不能整除整数。，那么〃'三〃(mod〃).

只需对。=1,2,…，〃—1证明成立，用数学归纳法.

(1)4=1,命题显然成立.

(2)假设命题对a-A(lWAvp-1)成立，那么当a—上十1时，由于〃|C；,(i一1,2,」〃一1),

故有

（八1）JM+C'*z++C；'k+1

三M+1三A+l（modp）.（用了归纳假设）

这说明，命题对。=攵+1是成立.

由数学归纳法得〃〃三a（mod〃）.

又素数〃不能整除整数〃，有（a,p）=l,得

定义9（欧拉函数）用*（〃）表示不大F〃且与〃互素的正整数个数.

定理16设正整数〃=p：p2s…〃产，那么

=〃1--

\P\八Pi)IPk)

证明用容斥原理.设S=[1,2,…记4为S中能被P,整除的数所组成的集合㈠=1,2,k）,

用|4|表示4中元素的个数，有

I止jlariAj=—,…,14。4n…n4|=-------------

PiPjP/2…&

易知，5={1,2,♦,〃}中与〃互素的正整数个数为

|AA?AJ,

由容斥原理得

|4n用n…同二同-x⑷+Z|AA^

\<i<k\<i<j<k

-E|A「4na”|++(-i)14n&n・..n4|

l£i<j<m<k

—+z---------工--------+«--------

14MPi\<i<j<kPiPj\<i<j<m<kPiPjP,nP\P1Pk

A

=wL_y1+yJ_一y—+(-i)—!—

Pi\<i<j<kPiPj\<i<j<m<kPiPjPmPl〃2-Pk

(1V1A(1)

=n1——1——…1——.

IAAPi)IAJ

注示意〃=3的容斥原理.

推论对素数〃有夕(〃)=〃一1,0(〃。)=〃。一〃"7.

定理17整系数不定方程3•十外・=c（c心40）存在整数解的充分必要条件是㈤卜.

证明记〃=(4/?).

(1)必要性(方程有解必须满足的条件).假设方程存在整数解，记为1"="°',那么

[y=加

ax0+by0=c,

由有d|ax()+〃y0,得证(a,9|c.

(2)充分性[条件能使方程有解).假设d|c,可设c二曲由于形如ar+by的数中有最小正数

O¥()+/?)、)满足

axi}+by()=(a,b).

两边乘以e,得

a®)+b(.)=c

这说明方程有解《x=ex°(}i

.、fx=A,

定理18假设时工0,(。力)=1,一且{_°n是整系数不定方程or+勿=。的一个整数解，那么

y=%，

方程的一切整数解可以表示为

x=x-bt,..

°a(reZ).①

y=yQ+(it,

证明直接代入知①是方程的整数解，下面证明任意一个整数解都有①的形式.

由(毛,%)是方程的一个解，有

姐=c，

又方程的任意一个解(X,)，)满足

ax+by=c,©

相减«(x-^))+/?(y-yo)=O.③

但(。/)=1,故有

〃l()f)，

有^=2ZA=MGZ

-ba

得方程的任意一个整数解可以表示为

定义10(平面整点)在平面直角坐标系上，纵横坐标都是整数的点称为整点(也称格点).类似地

可以定义空间整点.

第二讲数论题的范例讲解

主要讲几个重要类型：奇数与偶数，约数与倍数(素数与合数)，平方数，整除，同余，不定方程,

数论函数等.重点是通过典型范例来分析解题思路、提炼解题方法和稳固根本内容.

一、奇数与偶数

整数按照能否被2整除可以分为两类，一类余数为0,称为偶数，一类余数为1,称为奇数.偶数

可以表示为2〃，奇数可以表示为2〃-1或2〃+1.一般地，整数被正整数机去除，按照余数可以分为〃?

类,称为模"7的剩余类G={X%三，.(modm)},从每类中各取出一个元素qwG，可得模用的完全剩

余系(剩余类派出的一个代表团)，0,1,2,，机—1称为模〃？的非负最小完全剩余系.

通过数字奇偶性质的分析而获得解题重大进展的技巧，常称作奇偶分析，这种技巧与分类、染色、

数字化都有联系，在数学竞赛中有广泛的应用.

关于奇数和偶数，有下面的简单性质：

(1)奇数/偶数.

(2)偶数的个位上是0、2、4、6、8；奇数的个位上是1、3、5、7、9.

(3)奇数与偶数是相间排列的；两个连续整数中必是一个奇数一个偶数；.

(4)奇数个奇数的和是奇数；偶数个奇数的和是偶数；偶数跟奇数的和是奇数；任意多个

偶数的和是偶数.

15)除2外所有的正偶数均为合数；

(6)相邻偶数的最大公约数为2,最小公倍数为它们乘积的一半.

(7)偶数乘以任何整数的积为偶数.

18)两数和与两数差有相同的奇偶性，。+〃三。一〃(mod2).

(9)乘积为奇数的充分必要条件是各个因数为奇数.

(10)〃个偶数的积是2"的倍数.

(11)(一1)"=1的充分必要条件是A为偶数，(一1)人=一1的充分必要条件是攵为奇数.

(12)(2/?)2=0(mod4).(2/?-l)2=l(mod4),(2/2-l|2三1(mod8).

(13)任何整数都可以表示为〃=2"'(2k一1).

例1（1906,匈牙利J假设，。〃是1，2,-的某种排列，证明：如果〃是奇数，那么乘枳

是偶数.

解法1（反证法）假设侬一1）（出一2）也一〃）为奇数，那么q-i均为奇数，奇数个奇数

的和还是奇数

奇数=（一-2）++（4-〃）

=（4+〃■）+-+。〃）—（1+2++〃）=0,

这与“奇数工偶数，，矛盾.所以（0-1）（生一2）・・・（（一〃）是偶数.

评析这个解法说明（4-1）（生-2）-（4-〃）不为偶教是不行的，但没有指出为偶数的真正原

因.表达了整体处理的优点，但掩盖了“乘积”为偶数的实质.

解法2（反证法）假设（0―1）（勾—2）…（可一〃）为奇数，那么q-i均为奇数，q.与i的奇偶

性相反，｛1,2,,〃｝中奇数与偶数一样多，〃为偶数.但条件〃为奇数，矛盾.所以

（4—1）（%—2）是偶数.

评析这个解法揭示了（4-1）（%-2）,（《「〃）为偶数的原因是“〃为奇数”.那么为什么“〃为

奇数”时“乘积”就为偶数呢？

解法31.2.…，几生.….凡中有〃+1个奇数，放到〃个括号，必有两个奇数在同一个括号，这

两个奇数的差为偶数，得（4一1）（生一2）（4-〃）为偶数.

评析这个解法揭示了（4-1）（%-2）…（为一〃）为偶数的原因是“当〃为奇数时，1,2,・一,〃中奇

数与偶数个数不等，奇数多，某个括号必是两个奇数的差，为偶数”.

类似题：

例1T（1986,英国）设%,生，，%是整数，4也,也是它们的一个排列，证明

（q—4）（出一伪）（％-白）是偶数.

（4,4，•••，的中奇数与偶数个数不等）

例1-24的前24位数字为1=3.14159265358979323846264,记《,生，…，生4为该24个数

字的任一排列，求证（4-%X%—%）…（。23・。24）必为偶数.

（喑藏3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4中奇数与偶数个数不等）

例2能否从1,2,,15中选出10个数填入图的圆圈中，使得每两个有线相连的圈中的数相减〔大

数减小数），所得的14个差恰好为1,2,,14?；5木

解考虑14个差的和S,一方面V?■/.《

5=1+2+-・+14=105为奇数.W…

另一方面，每两个数。,人的差与其和有相同的奇偶性卜-耳三a+伙mo<12）,因此，14个差的和S

的奇偶性与14个相应数之和的和S'的奇偶性相同，由于图中的每一个数。与2个或4个圈中的数相加,

对S'的奉献为2。或4〃，从而S'为偶数,这与S为奇数矛盾，所以不能按要求给图中的圆圈填数.

评析：用了计算两次的技巧.对同一数学对象，当用两种不同的方式将整体分为局部时，那么按两

种不同方式所求得的总和应是桂等的，这叫计算两次原理成富比尼原理.计算两次可以建立左右两边关

系不太明显的恒等式.在反证法中，计算两次又可用来构成矛盾.

例3有一大筐苹果和梨分成假设干堆，如果你一定可以找到这样的两堆，其苹果数之和与梨数之

和都是偶数，问最少要把这些苹果和梨分成儿堆？

解（1）4堆是不能保证的.如4堆的奇偶性为：（反例）

（奇奇），（偶偶），（奇偶），（偶奇）.

（2）5堆是可以保证.因为苹果和梨数的奇偶性有且只有上述4种可能，当把这些苹果和梨分成

5堆时，必有2堆属于同一奇偶性，其和苹果数与梨数都是偶数.

例4有〃个数芭,马,di，%，它们中的每一个要么是1，要么是-1.假设

x1x2+々占+"••+•••+Nix”=0，求证41n.

证明由斗有书句再由

王占+看毛+…+怎+当玉=0，

知〃个七七+1中有一半是1,有一半是一1,〃必为偶数，设〃=2%.

现把〃个西一川相乘，有

(-1/(+1/=

可见，及为偶数，设4=2〃2,有九=4相，得证4|〃.

例5一个整数4,。2,…，4-1，。“，其积为〃，其和为0，试证4|〃.

证明先证〃为偶数，假设不然，由4LQ〃=〃知，ci,%,全为奇数，其和必为

奇数，与其和为0（偶数），故〃必为偶数.（q,%，，《“，可中至少有1个偶数）

再证〃为4的倍数，假设不然，由〃为偶数知，4,生,…恰有一个为偶数，其余，一1个数

全为奇数，奇数个奇数之和必为奇数，加上一个偶数，总和为奇数，与。|,生，…，之和为0矛盾，

所以，〃为4的倍数，4|〃.（/,3,。〃中至少有2个偶数）

评析要证4|〃，只须证4,。2，，4i，%中至少有2个偶数，分两步，第一步证至少有1个偶数，

第二步证至少有2个偶数.

例6在数轴上给定两点1和正，在区间（1,血）内任取〃个点，在此〃+2个点中，每相邻两点

连一线段，可得〃+1条互不重叠的线段，证明在此〃+1条线段中，以一个有理点和一个无理点为端点

的线段恰有奇数条.

证明将〃+2个点按从小到大的顺序记为A，4,…,4,+2,并在每一点赋予数值《，使

=f1,当4为有理数点时，

当A为无理数点时.

与此同时，每条线段44+1也可数字化为qam（乘法）

当&As—为有理数点，另一为无理数时，

叫={1,当同为有理数点或无理数点时，

记卬心二-1的线段有攵条，一方面

（%生）（廿3）（WJ…（%+得〃+2）=（T）"（+D…=（-D*

另一方面（―）（。2。3）（。3a4尸・（4+|。”+2）

=4（4%…。〃-J%〃+2=44+2=T，

得㈠）人二一1,故左为奇数.

评析用了数字化、奇偶分析的技巧.

二、约数与倍数

最大公约数与最小公倍数的求法.

（1）短除法.

（2）分解质因数法.设

a=Pi"**,P：*,qN0,，=1,2,…，女，

b=p，pj、・p"2i=1，2,.、k.

记/=min{«,力},6=max{«,力},

那么（a,b）=,•,〃J，

［。，句-Q。"P/•

13）辗转相除法

（〃，6）=修"）=（小弓）=一,=（*，/）=（%0）=大

例7(1)求(8381,1015)，[8381,1015]；

(2)(144,180,108),[144J80J08].

解⑴方法1分解质因数法.由

8381=172X29,

1015=5x7x2