数学竞赛中的数论问题

数学竞赛中的数论问题 韩熙

引言

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

什么是正整数呢？人们借助于“集合”和“后继”关系给正整数（当时也即自然数）作过本质的描述，正整数1，2，3， 是这样一个集合N ：

（1）有一个最小的数1．

（2）每一个数a的后面都有且只有一个后继数a；除1之外，每一个数的都是且只是一个数的后继数．

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

（3）对N 的子集M，若1 M，且当a M时，有后继数a M，则M N ． 就是这么一个简单的数集，里面却有无穷无尽的奥秘，有的奥秘甚至使得人们怀疑：人类的智慧还没有成熟到解决它的程度．比如，哥德巴赫猜想：

1742年6月7日，普鲁士派往俄国的一位公使哥德巴赫写信给欧拉，提出“任何偶数，由4开始，都可以表示为两个素数和的形式，任何奇数，由7开始，都可以表示为三个素数的和．后者是前者的推论，也可独立证明（已解决）．“表示为两个素数和的形式”就是著名的哥德巴赫猜想，简称1+1．

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

1900年希尔伯特将其归入23个问题中的第8个问题． 1966年陈景润证得：一个素数+素数 素数（1+2），至今仍无人超越． ●陈景润的数学教师沈元很重视利用名人、名言、名事去激励学生，他曾多次在开讲时，说过这样的话:“自然科学的皇后是数学，数学的皇冠是数论，哥德巴赫猜想则是皇冠上的明珠． ”陈景润就是由此而受到了启示和激励，展开了艰苦卓绝的终生奋斗和灿烂辉煌的奋斗终生，离摘取“皇冠上的明珠”仅一步之遥．

●数论题涉及的知识不是很多，但用不多的知识来解决问题往往就需要较强的能力和精明多的技巧，有人说：用以发现数学人才，在初等数学中再也没有比数论教材更好的课程了．任何学生如能把当今一本数论教材中的练习做出，就应当受到鼓励，劝他（她）将来去从事数学方面的工作（U．Dudley《数论基础》前言）．下面，是一个有趣的故事．

当代最高产的数学家厄尔多斯听说一个叫波萨（匈牙利，1948）的小男孩很聪明，就问了他一个问题加以考察（1959）：如果你手头上有n 1个正整数，这些正整数小于或等于2n，那么你一定有一对整数是互素的，你知道这是什么原因吗？

不到12岁的波萨只用了1分半钟，就给出了问题的解答．他将1～2n分成（1，2），（3，4）， ，（2n 1,2n）共n个抽屉，手头的n 1个正整数一定有两个属于同一抽屉，这两个数是相邻的正整数，必定互素．

通过这个问题，厄尔多斯认定波萨是个难得的英才，就精心加以培养，不到两年，14岁的波萨就发表了图论中“波萨定理”．

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

/

/

支柱是：代数，几何，初等数论，组合初步（俗称代数题、几何题、算术题和智力题）．高中竞赛加试四道题正好是四大模块各一题，分别是几何题、代数题、数论题、组合题，一试中也会有数论题．数论受到数学竞赛的青睐可能还有一个技术上的原因，就是它能方便地提供从小学到大学各个层面的、新鲜而有趣的题目．

数论题的主要类型：在初中竞赛大纲中，数论的内容列有：十进制整数及表示方法；整除性，被2、3、4、5、8、9、11等数整除的判定；素数和合数，最大公约数与最小公倍数；奇数和偶数，奇偶性分析；带余除法和利用余数分类；完全平方数；因数分解的表示法，约数个数的计算； 简单的一次不定方程．

在高中竞赛大纲中，数论的内容列有：同余，欧几里得除法，裴蜀定理，完全剩余类，二次剩余，不定方程和方程组，高斯函数[x]，费马小定理，格点及其性质，无穷递降法，欧拉定理，孙子定理．

根据已出现的试题统计，中学数学竞赛中的数论问题的主要有8个重点类型： （1）奇数与偶数（奇偶分析法、01法）； （2）约数与倍数、素数与合数； （3）平方数； （4）整除； （5）同余； （6）不定方程；

（7）数论函数、 x 高斯函数、 n 欧拉函数；

（8）进位制（十进制、二进制）．

下面，我们首先介绍数论题的基本内容（10个定义、18条定理），然后，对数学竞赛中的数论问题作分类讲解．

第一讲 数论题的基本内容

中学数学竞赛中的数论问题涉及的数论内容主要有10个定义、18条定理． 首先约定，本文中的字母均表示整数．

定义1 （带余除法）给定整数a,b,b 0,如果有整数q,r0 r b满足 a qb r，

则q和r分别称为a除以b的商和余数．特别的，r 0时，则称a被b整除，记作ba，或者说a是b的倍数，而b是a的约数．（q,r的存在性由定理1证明）

定义2 （最大公约数）设整数a1,a2,

,an中至少有一个不等于零，这n个数的最大

公约数是能整除其中每一个整数的最大正整数，记作 a1,a2,

a1,a2,

,an ．

,an 中的ai没有顺序，最大公约数也称最大公因数．

,an a1,a2,

,an ．

简单性质： a1,a2,

一个功能：可以把对整数的研究转化为对非负整数的研究． 定义3 （最小公倍数）非零整数a1,a2,

,an的最小公倍数是能被其中每一个

ai 1 i n 所整除的最小正整数，记作 a1,a2,,an ．

简单性质：如果k是正整数a,b的公倍数，则存在正整数m使k m证明 若不然，有k m a,b r（0 r a,b ），由k,

a,b

a,b 都是a,b的公倍数得r

a,b ．

也是a,b的公倍数，但0 r a,b ，与 a,b 的最小性矛盾．故k m

定义4 如果整数a,b 满足 a,b 1，则称a与b是互素的（也称互质）．

定义5 大于1且除1及其自身外没有别的正整数因子的正整数，称为素数（也称质数）．其余大于1的正整数称为合数；数1既不是素数也不是合数．

定理1 若a,b是两个整数，b 0，则存在两个实数q,r，使a qb r 0 r b ，并且q,r是唯一性．

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

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

则a必在上述序列的某两项之间，从而存在一个整数q，使

qb a q 1 b，

即 0 a qb b， 取 r a qb， 0 r b， 得 a qb r，

即存在两个实数q,r，使a qb r 0 r b ． 再证唯一性．假设不唯一，则同时存在q1,r1与q1,r2，使 a q1b r1 0 r1 b ， a q2b r2 0 r2 b ， 相减 q1 q2 b r2 r1， q1 q2b r2 r1 b， 0 q1 q2 1，

但q1 q2为整数，故q1 q2 0，得q1 q2，从而r1 r2．

注：如果取消0 r b，当r 0或r b，不保证唯一．

经典方法：紧扣定义，构造法证存在性，反证法证唯一性． 证明2 只证存在性，用高斯记号，由 0

ab a

b 1， 有 0 a b a b

b，

记r a b a ，故存在q a a b b ,r a b b

,0 r b使

a qb r 0 r b ．

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

M a bx|x Z,a bx 0

这是一个有下界的非空整数集，其中必有最小的，设x q时，有最小值r r 0 a qb r．

再证r b，若不然，r b，记r b r1，有

a qb r qb b r1 b q 1 r1

r1 a b q 1 M

即M有r1比r更小，这与r为最小值矛盾． 故存在两个实数q,r，使a qb r 0 r b ．

定理2 设a,b,c是三个不全为0的整数，满足a qb c，其中q也为整数，则

a,b b,c ．

证明 设A ｛a,b的公约数｝， B ｛b,c的公约数｝．

任取d A

d|a d|c a bq

d B A B， d|b d|b

d|b d|b

任取d B d A B A，

d|cd|a bq c

得 A B．

有A中元素的最大值 B中元素的最大值，即

a,b b,c ．

注：这是辗转相除法求最大公约数的理论基础．

经典方法：要证明A B，只需证A B且B A． 定理3 对任意的正整数a,b，有 a,b a,b ab．

证明 因为ab是a,b的公倍数，所以a,b的最小公倍数也是ab的约数，存在q使 ab q a,b ，

有

a,b a,b a q且为整数，

b

b

故q是a的约数．同理q是b的约数，即q是a,b的公约数．下面证明，q是a,b的最大公约数．若不然，q a,b ．有

ab q a,b a,b a,b ． ①

设k

abbaba

，可见k是a的倍数，同样k ，k是b的倍 a b

a,ba,ba,ba,b数，即k是a,b的公倍数，则存在正整数m使k m

a,b ，有

ab

m a,b a,b ， a,b得 ab q a,b a,b a,b

与①矛盾，所以，q a,b ，得证 a,b a,b ab．

ab

a,b qk 注 也可以由1 m ，得q a,b ，与q a,b 矛盾．

aba,ba,bq

两步ab q a,b ,ab a,b k可以交换吗？

定理4 a,b是两个不同时为0的整数，若ax0 by0是形如ax by（x,y是任意整数）的数中的最小正数，则

（1）ax0 by0|ax by； （2）ax0 by0 a,b ． 证明 （1）由带余除法有

ax by ax0 by0 q r，0 r ax0 by0， 得 r a x qx0 x b y qy0 ax0 by0，

知r也是形如ax by的非负数，但ax0 by0是形如ax by的数中的最小正数，故r 0，即

ax0 by0|ax by．

（2）由（1）有

ax0 by0|a1 b0 a， ax0 by0|a0 b1 b，

得ax0 by0是a,b的公约数．另一方面，a,b的每一个公约数都可以整除ax0 by0，所以

ax0 by0是a,b的最大公约数，ax0 by0 a,b ．

推论 若 a,b 1，则存在整数s,t，使as bt 1．（很有用） 定理5 互素的简单性质： （1） 1,a 1． （2） n,n 1 1． （3） 2n 1,2n 1 1．

（4）若p是一个素数，a是任意一个整数，且a不能被p整除，则 a,p 1． 证明 因为 a,p |p，所以，素数p的约数只有两种可能： a,p 1, a,p p．但

a不能被p整除， a,p p，得 a,p 1．

推论 若p是一个素数，a是任意一个整数，则 a,p 1或 a,p p． （5）若 a,b 1，则存在整数s,t，使as bt 1．（定理4推论） （6）若 a,b 1, a,c 1，则 a,bc 1． 证明 由 a,b 1知存在整数s,t，使as bt 1． 有 a cs bct c， 得 a,bc a,c 1．

（7）若 a,b 1，则 a b,a 1， a b,b 1， a b,ab 1． 证明 a b,a b,a b,a 1， a b,b a,b 1， 由（6） a b,ab 1．

mn

（8）若 a,b 1，则a,b 1，其中m,n为正整数． m

证明 据（6），由 a,b 1可得a,b 1． mmn

同样，由a,b 1可得a,b 1．

定理6 设a是大于1的整数，则a的除1之外的最小的正约数q必是素数，且当a是

合数时，q

证明 用反证法，假设q不是素数，则存在正整数数q1，使q1|q，但q|a，1 q1 q，故有q1|a，这与q是a的除1之外的最小正约数矛盾，故q是素数．

当a是合数时，设a a1q，则a1也是a的一个正约数，由q的最小性得q a1，从而

q2 a1q

a，开方得q

定理7 素数有无穷多个，2是唯一的偶素数． 证明 假设素数只有有限多个，记为p1,p2, p p1p2

,pn，作一个新数

pn 1 1．

,pn矛盾．

若p为素数，则与素数只有 n个p1,p2,若p为合数，则必有pi p1,p2,

,pn ，使pi|p，从而pi|1，又与pi 1矛盾．

综上所述，素数不能只有有限多个，所以素数有无穷多个． 2是素数，而大于2的偶数都是合数，所以2是唯一的偶素数．

注：这个证明中，包含着数学归纳法的早期因素：若假设有n个素数，便有n 1个素数．（构造法、反证法）秒

定理8（整除的性质）整数a,b,c通常指非零整数 （1）1a， 1|a；当a 0时，a|a，a|0．

（2）若ba，a 0，则b a;若ba，b a，则a 0;若ab 0，且b,a，则a b．

证明 由ba，a 0，有a bq，得a bq b． 逆反命题成立“若ba，b a，则a 0”; 由b a且b a得a b，又ab 0，得a b． （3）若a b c d，且e|a,e|b,e|c，则e|d． （4）若cb，ba，则ca． 证明 （定义法）由cb，ba，有 b q1c,a q2b， 得 a q1q2 c，

即 ca．

（5）若ca，则bcab．

（6）若ca，cb，则对任意整数m,n，有cma nb． 证明 （定义法）由ca，cb，有 a q1c,b q2c， 得 ma nb mq1 nq2 c， 即 cma nb．

（7）若 a,b 1，且abc，则ac．

证明 由 a,b 1知存在整数s,t，使as bt 1，有

a cs bc t c，

因为aa，abc，所以a整除等式的左边，进而整除等式的右边，即ac．

|b得出ac．如64 9，但6 |4且6 |9． 注意 不能由abc且a

（8）若 a,b 1，且ac,bc，则abc．

证明 由 a,b 1知存在整数s,t，使as bt 1，有

acs bct c，

又由ac,bc有c aq1,c bq2代入得

ab q2s ab q1t c，

所以abc．

注意 不能由ac且bc得出abc．如不能由630且10|30得出60|30． （9）若a为素数，且abc，则ab或ac．

|b且a |c，证明 若不然，则a 由a为素数得 a,b 1, a,c 1，由互素的性质（6）|bc，与abc矛盾． 得 a,bc 1，再由a为素数得a

|4且6 |9． 注意 没有a为素数，不能由abc推出ab或ac．如64 9，但6

定义6 对于整数a,b,c，且c 0，若c(a b)，则称a,b关于模c同余，记作

a b(modc)；若c | a b ，则称a,b关于模c不同余，记作

a

定理9（同余的性质）设a,b,c,d,m为整数，m 0, （1）若a b(modm)且b c(modm)，则a c(modm)； 证明 由a b(modm)且b c(modm)，有 a b mq1,b c mq2，

b(modc)．

a c m q1 q2 ，

得a c(modm)．

c b d（2）若a b(modm)且c d(modm)，则a

证明 由a b(modm)且c d(modm)，有

m(odm)且ac bd(modm)．

a b mq1,c d mq2， ① 对①直接相加 ，有

a c b d m q1 q2 ，

得 a c b d(modm).

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

ac bd ac bc bc bd m cq1 bq2 ，

得 ac bd(modm)．

（3）若a b(modm)，则对任意的正整数n有a b(modm)且an bn(modmn). （4）若a b(modm)，且对非零整数k有k(a,b,m)，则

n

n

ab m

mod ． kk k

证明 由a b(modm)、，有 a b mq， 又k(a,b,m)，有

abm

,,均为整数，且 kkk

abm

q， kkk

得

ab m mod ． kk k

定理10 设a,b为整数，n为正整数，

nn

（1）若a b，则 a b a b．

an bn a b an 1 an 2b an 3b2

（2）若a b，则 a b a

abn 2 bn 1 ．

2n 1

b2n 1 ．

ab2n 3 b2n 2 ．

a2n 1 b2n 1 a b a2n 2 a2n 3b a2n 4b2

（3）若a b，则 a b a

2n

b2n ．

ab2n 2 b2n 1 ．

a2n b2n a b a2n 1 a2n 2b a2n 3b2

定义7 设n为正整数，k为大于2的正整数, a1,a2,,am是小于k的非负整数，且

a1 0．若

n a1km 1 a2km 2 则称数a1a2

am 1k am，

am为n的k进制表示． n a110m 1 a210m 2 n a12m 1 a22m 2

定理11 给定整数k 2，对任意的正整数n，都有唯一的k进制表示．如

am 110 am，0 ai 9,a1 0（10进制） am 12 am．0 ai 1,a1 0（２进制）

定理12 （算术基本定理）每个大于1的正整数都可分解为素数的乘积，而且不计因数的顺序时，这种表示是唯一的

n p11p2其中p1 p2

2

pk k，

, k为正整数． （分解唯一性）

pk为素数， 1, 2,

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

n p1p2pm． ①

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

当正整数n为合数时，n的正约数中必有一个最小的，记为p1，则p1为素数，有

n p1a1，1 a1 n．

如果a1为素数，命题已成立．当a1为合数时，a1的最小正约数p2为必为素数，有

n p1a1 p1p2a2，1 a2 a1 n．

这个过程继续进行下去，由于n为有限数，而每进行一步ai就要变小一次，于是，经过有限次后，比如m次，n就变为素数的乘积

n p1p2

pm．

下面证明分解式是唯一的．假设n还有另一个分解式 n q1q2则有 p1p2

qt， ② pm q1q2

qt． ③

,pm中的

因为等式的右边能被q1整除，所以左边也能被q1整除，于是q1整除p1,p2,某一个pi，但pi为素数，所以pi与q1相等，不妨设pi为p1，有

p1 q1．

把等式③两边约去p1 q1，得 p2p3

pm q2q3qt．

再重复上述步骤，又可得p2 q2，p3 q3， ，直到等式某一边的因数被全部约完，这时，如果另一边的因数没有约完，比如右边没有被约完（m t），则有

1 qm 1qm 2但qm 1,qm 2,

qt． ④

qt 1，这表明等式④不

,qt均为素数，素数都大于1，有qm 1qm 2

可能成立，两个分解式的因数必然被同时约完，即分解式是唯一的． 将分解式按pi的递增排列，并将相同的pi合并成指数形式，即得

n p1 1p2 2

其中p1 p2

pk k．

, k为正整数．

pk为素数， 1, 2,

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

n p1p2pm，p1 p2 pm．

（1）当n 2，因为2为素数，命题成立．

（2）假设命题对一切大于1而小于n的正整数已成立． 这时，若n为素数，命题成立；若n不为素数，必存在a,b，使 n ab，1 a n,1 b n， 由归纳假设，小于n的a,b可分解为素数的乘积

/

a p1/p2

/

ps/, p1/ p2 /s 2

ps/,

/s 2

b pp

/s 1

p, pps/qs/ 1qs/ 2

/t/s 1

p p,

/t

//

得 n p1p2qt/，

适当调整pi/的顺序，可得命题对于正整数n成立．

由数学归纳法，命题对一切大于1的正整数n成立．

下面证明分解式是唯一的．假设n的分解式不唯一，则至少有两个分解式

n p1p2

n q1q2

得 p1p2有 p1|q1q2这就存在qi,pj，使

pm，p1 p2 qt，q1 q2 pm q1q2

qt．

pm， qt，

qt且q1|p1p2pm，

p1|qi且q1|pj，

但p1,qi,q1,pj均为为素数，所以

p1 qi,q1 pj，

又 p1 qi q1 pj p1， 所以 p1 q1．

把等式两边约去p1 q1，得 p2p3

pm q2q3qt．

再重复上述步骤，又可得p2 q2，p3 q3， ，直到等式某一边的因数被全部约完，这时，如果另一边的因数没有约完，比如右边没有被约完（m t），则有

1 qm 1qm 2

qt．

但qm 1,qm 2,,qt均为素数，素数都大于1，有qm 1qm 2qt 1，这表明上述等式

不可能成立，两个分解式的因数必然被同时约完，即分解式是唯一的． 将分解式按pi的递增排列，并将相同的pi合并成指数形式，即得

n p1 1p2 2

其中p1 p2

pk k．

, k为正整数．

2

pk为素数， 1, 2,

定理13 若正整数n的素数分解式为 n p11p2

pk k则n的正约数的个数为

d n a1 1 a2 1 ak 1 ，

pk k 1 1

．

pk 1

n的一切正约数之和为

p1 1 1 1p2 2 1 1

S n

p1 1p2 1

证明 对于正整数n p11p2 m p11p2由于 i有0,1,2,

2

2

pk k，它的任意一个正约数可以表示为

pk k，0 i i ， ①

, i共 i 1种取值，据乘法原理得n的约数的个数为

d n a1 1 a2 1

考虑乘积

01

p1 p1

ak 1 ．

p2 2

p1 1 p20 p21 p

0k pk1 pk k，

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

S n p10 p11 p1 1 p

0k pk1

pk 1

p1 1 1 1p2 2 1 1

p1 1p2 1

注 构造法．

pk k 1 1

．

pk 1

定义8 （高斯函数）对任意实数x， x 是不超过x的最大整数．亦称 x 为x的整数部分， x x x 1．

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

n n n

3 2

p p p

．

证明 由于p为素数，故在n!中p的次方数是1,2,意，若p不为素数，这句话不成立）．

在1,2,

,n各数中p的次方数的总和（注

n n n

,n中，有 个p的倍数；在 个p的倍数的因式中，有 2 个p2的

p p p

倍数；在

n n 2

个的倍数的因式中，有个p3的倍数； ，如此下去，在正整数n!p 2 3 p p

n n n

3 2

p p p

的素因子分解式中，素数p作为因子出现的次数就为

．

注 省略号其实是有限项之和． 画线示意50!中2的指数．

50! 2 13 25 37 411 513 617 719 823 9293137414347

p 1

定理15 （费玛小定理）如果素数p不能整除整数a，则pa 1．

证明1 考察下面的p 1个等式： a pq1 r1，0 r1 p，

2a pq2 r2，0 r2 p

p 1 a pqp 1 rp 1，0 rp 1 p

由于素数p不能整除整数a，所以，p不能整除每个等式的左边，得r1,r2,为0，只能取1,2,

,rp 1均不

,p 1．下面证明r1,r2,,rp 1各不相等．

若不然，存在t,s,1 t s p 1，使

sa pqs rs,

ta pqt rt,

rs rt,

相减 s t a p qs qt ．

应有素数p整除 s t a，但素数p不能整除a，所以素数p整除 s t ，然而由

1 t s p 1可得

0 s t p 2 p， 要素数p整除 s t 是不可能的，得r1,r2,,rp 1各不相等．有

rr12

rp 1 12

p 1 p 1 !．

再把上述p 1个等式相乘，有 p 1 !ap 1 Mp rr12

rp 1，

即 p 1 !ap 1 Mp p 1 !， 其中M是一个整数．

亦即 p 1 ! ap 1

1

Mp．

由于p是素数，不能整除 p 1 !，所以素数p整除ap 1

1，得证

p

a

p 1

1

证明2 改证等价命题：如果素数p不能整除整数a，则ap

a modp ．

只需对a 1,2,,p 1证明成立，用数学归纳法．

（1）a 1，命题显然成立．

（2）假设命题对a k 1 k p 1 成立，则当a k 1时，p|Cip i 1,2,,p 1 ，故有

k 1 p

kp C1p 1

pk

Cp 1pk 1

kp

1 k 1 modp ．（用了归纳假设）

这表明，命题对a k 1是成立． 由数学归纳法得ap

a modp ．

又素数p不能整除整数a，有 a,p 1，得p ap 1

1

．

定义9 （欧拉函数）用 n 表示不大于n且与n互素的正整数个数． 定理16 设正整数n p

11p 22

p kk，则

n n 1

1 1 1

p 1 1

1 p2 p ． k

于

由

证明 用容斥原理．设S 1,2,（i 1,2

,n ，记Ai为S中能被pi整除的数所组成的集合

，用Ai表示Ai中元素的个数，有 ,k）

Ai

n

，Aipi

Aj

n,pipj

,A1A2Ak

np1p2

pk

．

易知，S 1,2, A1由容斥原理得

,n 中与n互素的正整数个数为

Ak，

A2

A1

A2Ak S Ai

Aj

1 i k

Ai

1 i j k

k

AiA2

Aj

1 i j m k

Am

1 A1

Ak

1

k

n

1 i k

nnn

pi1 i j kpipj1 i j m kpipjpm

111 pi1 i j kpipj1 i j m kpipjpm

1 1 .

pk

np1p2

k

pk1

pk

n 1

1 i k

1

p1p2

1 1

n 1 1

p1 p2

注 示意n 3的容斥原理．

1

推论 对素数p有 p p 1, p p p．

定理17 整系数不定方程ax by c（ab 0）存在整数解的充分必要条件是

a,b c．

证明 记d a,b ．

（1）必要性（方程有解必须满足的条件）．若方程存在整数解，记为

x x0,

，则

y y0,

ax0 by0 c，

由d|a,d|b， 有d|ax0 by0，得证 a,b |c．

（2）充分性（条件能使方程有解）．若d|c，可设c de由于形如ax by的数中有最小正数ax0 by0满足

ax0 by0 a,b ．

两边乘以e，得

a ex0 b ey0 c

x ex0,

这表明方程有解

y ey.0

定理18 若ab 0, a,b 1，且 解，则方程的一切整数解可以表示为

x x0,

是整系数不定方程ax by c的一个整数

y y0,

x x0 bt,

t Z ． ①

y y at,0

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

ax0 by0 c，

又方程的任意一个解 x,y 满足

ax by c， ② 相减 a x x0 b y y0 0． ③ 但 a,b 1，故有 a| y y0 ， 有

x x0y y0

t,t Z ba

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

x x0 bt,

t Z ．

y y0 at,

定义10 （平面整点）在平面直角坐标系上，纵横坐标都是整数的点称为整点（也称格点）．类似地可以定义空间整点．

第二讲 数论题的范例讲解

主要讲几个重要类型：奇数与偶数，约数与倍数（素数与合数），平方数，整除，同余，不定方程，数论函数等．重点是通过典型范例来分析解题思路、提炼解题方法和巩固基本内容．

一、奇数与偶数

整数按照能否被2整除可以分为两类，一类余数为0，称为偶数，一类余数为1，称为奇数．偶数可以表示为2n，奇数可以表示为2n 1或2n 1．一般地，整数被正整数m去除，按照余数可以分为m类，称为模m的剩余类Ci xx i modm ，从每类中各取出一个元素ai Ci，可得模m的完全剩余系（剩余类派出的一个代表团），0,1,2,

,m 1称

为模m的非负最小完全剩余系.

通过数字奇偶性质的分析而获得解题重大进展的技巧，常称作奇偶分析，这种技巧与分类、染色、数字化都有联系，在数学竞赛中有广泛的应用． 关于奇数和偶数，有下面的简单性质：

（1）奇数 偶数．

（2）偶数的个位上是0、2、4、6、8；奇数的个位上是1、3、5、7、9． （3）奇数与偶数是相间排列的；两个连续整数中必是一个奇数一个偶数；． （4）奇数个奇数的和是奇数；偶数个奇数的和是偶数；偶数跟奇数的和是奇数；任意多个偶数的和是偶数．

（5）除2外所有的正偶数均为合数；

（6）相邻偶数的最大公约数为2，最小公倍数为它们乘积的一半． （7）偶数乘以任何整数的积为偶数．

（8）两数和与两数差有相同的奇偶性，a b a b mod2 ． （9）乘积为奇数的充分必要条件是各个因数为奇数． （10）n个偶数的积是2的倍数．

（11） 1 1的充分必要条件是k为偶数， 1 1的充分必要条件是k为奇数．

（12） 2n 0 mod4 , 2n 1 1 mod4 , 2n 1 1 mod8 ． （13）任何整数都可以表示为n 2

例1 （1906，匈牙利）假设a1,a2,数，则乘积

a1 1 a2 2 是偶数．

解法1 （反证法）假设 a1 1 a2 2

m

2

2

2

k

k

n

2k 1 ．

,n的某种排列，证明：如果n是奇

,an是1,2,

an n

an n 为奇数，则ai i均为奇数，奇

数个奇数的和还是奇数

奇数= a1 1 a2 2

an n

n 0，

a1 a2 an 1 2

这与“奇数 偶数”矛盾． 所以 a1 1 a2 2 评析 这个解法说明 a1 1 a2 2

an n 是偶数．

但没有指出为偶数 an n 不为偶数是不行的，

的真正原因．体现了整体处理的优点，但掩盖了“乘积”为偶数的实质．

解法2 （反证法）假设 a1 1 a2 2

an n 为奇数，则ai i均为奇数，ai与

i的奇偶性相反， 1,2,,n 中奇数与偶数一样多，n为偶数．但已知条件n为奇数，矛

盾． 所以 a1 1 a2 2 an n 是偶数．

．那么 an n 为偶数的原因是“n为奇数”

评析 这个解法揭示了 a1 1 a2 2

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

解法3 1,2,

,n,a1,a2,,an中有n 1个奇数，放到n个括号，必有两个奇数在同一

个括号，这两个奇数的差为偶数，得 a1 1 a2 2 评析 这个解法揭示了 a1 1 a2 2

an n 为偶数．

an n 为偶数的原因是“当n为奇数时，

1,2,,n中奇数与偶数个数不等，奇数多，某个括号必是两个奇数的差，为偶数”．

类似题：

例1-1（1986，英国）设a1,a2,

,a7是整数，b1,b2,,b7是它们的一个排列，证明

a1 b1 a2 b2 a7 b7 是偶数．

（a1,a2,

,a7中奇数与偶数个数不等）

为

例1-2 的前24位数字为 3.14159265358979323846264，记a1,a2,,a42该24个数字的任一排列，求证 a1 a2 a3 a4

a23 a24 必为偶数．

（暗藏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？

数相减（大数减小数），所得的14个差恰好为1,2,

解 考虑14个差的和S，一方面

S 1 2 14 105为奇数．

另一方面，每两个数a,b的差与其和有相同的奇偶性 a b a b(mod2)，因此，14个差的和S的奇偶性与14个相应数之和的和S的奇偶性相同，由于图中的每一个数a与2个或4个圈中的数相加，对S的贡献为2a或4a，从而S为偶数，这与S为奇数矛盾，所以不能按要求给图中的圆圈填数．

评析：用了计算两次的技巧．对同一数学对象，当用两种不同的方式将整体分为部分时，则按两种不同方式所求得的总和应是相等的，这叫计算两次原理成富比尼原理．计算两次可以建立左右两边关系不太明显的恒等式．在反证法中，计算两次又可用来构成矛盾．

例3 有一大筐苹果和梨分成若干堆，如果你一定可以找到这样的两堆，其苹果数之和与梨数之和都是偶数，问最少要把这些苹果和梨分成几堆？

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

（2）5堆是可以保证． 因为苹果和梨数的奇偶性有且只有上述4种可能，当把这些苹果和梨分成5堆时，必有2堆属于同一奇偶性，其和苹果数与梨数都是偶数．

例4 有n个数x1,x2,

/

/

/

,xn 1,xn，它们中的每一个要么是1，要么是 1．若

x1x2 x2x3

nxx nxx0，求证4|n． 1n1

证明 由xi 1, 1 ，有xixi 1 1, 1 ，再由

x1x2 x2x3

xn 1xn xnx1 0，

知n个xixi 1中有一半是1，有一半是 1，n必为偶数，设n 2k．

现把n个xixi 1相乘，有 ( 1)k( 1)k x1x2x2x3

xn 1xnxnx1 x12x22xn 12xn2 1，

可见，k为偶数，设k 2m，有n 4m，得证4|n．

例5 n个整数a1,a2,

,an 1,an，其积为n，其和为0，试证4|n．

an 1an n知，a1,a2,

,an 1,an全为奇数，

证明 先证n为偶数，若不然，由a1a2

其和必为奇数，与其和为0（偶数），故n必为偶数．（a1,a2,

再证n为4的倍数，若不然，由n为偶数知，a1,a2,

,an 1,an中至少有1个偶数）

,an 1,an恰有一个为偶数，其余

n 1个数全为奇数，奇数个奇数之和必为奇数，加上一个偶数，总和为奇数，与

a1,a2,

（a1,a,an 1,an之和为0矛盾，所以，n为4的倍数，4|n．2,,a,1n an中至少有

本文来源：https://www.bwwdw.com/article/2gpe.html