《数学竞赛辅导》-初等数论

《数学竞赛辅导》——初等数论部分上犹中学刘道生 编辑1991年，IMO6IMO道与数论有关。难的数论问题，适合于任何人去研究。初等数论最基础的理论在于整除，由它可以演化出许多数论定a,bNqrNabqr0rb。除了在题目上选择我们努力做到精挑细选，在内容的安排上我们也尽量做到讲解详尽，明白。相信通过对本书学习，您可以对数论有一个大致的了解。希望我们共同学习，相互交流，在学习交流中，共同提高。编者：刘道生2007-8-21于江西赣州第一节整数的p进位制及其应用基础知识给定一个m位的正整数A，其各位上的数字分别记为a ,a ,,a，则此数可以简m1 m2 0记为：Aa a a （其中a 0。m1 m2 0 m1A可以表示成10的m1次多项式，即A

10m1a

m2

10m2a1

10a0

，其中ai

i1,2,m1且a 0，像这种10的多项式表示的数常常简记为A(a a a) 。在我们的日常m1 m1 m2 010生活中，通常将下标10省略不写，并且连括号也不用，记Aa a a ，以后我们m1 m2 001这两种Ap进制表示：Aam1

am2

pm2a1

pa0

，其中ai

pm1且a 0。而m仍然为十进制数字，简记为A(a a a) 。m1 m1 m2 0 p典例分析例1．将一个十进制数字）八进制，并将其表示成多项式形式。分析与解答分析：用2作为除数（若化为p进位制就以p作为除数，除2004商100，余数为210025010；0解：01371531621252505011002200421111各次余数1010100被除数除数各次商数故(2004) (11111010100) ，412被除数除数各次商数10 2同理，有(2004) (3274) ，4784。10 8处理与数字有关的问题，通常利用定义建立不定方程来求解。例2．求满足abc(abc)3的所有三位数abc。 （1988年上海市竞赛试题）解：由于100abc999，则100(abc)3999，从而5abc9；abc55312525)3；abc663216(216)3；abc773343(343)3；abc883512(512)3；abc993729(729)3；于是所求的三位数只有512。例3．一个四位数，它的个位数字与百位数字相同。如果将这个四位数的数字顺序颠倒过来（即个位数字与千位数字互换，十位数字与百位数字互换7812，求原来的四位数。解：设该数的千位数字、百位数字、十位数字分别为x,y,z，则

（1979年云南省竞赛题）原数103x102y10zy ①颠倒后的新数103y102z10yx 由②－①得7812＝999(yx)90(zy)即868yx)10(zy)102(yx)10(zy)(yx) 比较③式两端百位、十位、个位数字得yxzx6由于原四位数的千位数字x不能为0x1yx89，又显然百位数字y9，所以y9,x1,zx67。所以所求的原四位数为1979。例递增数列是由一些正整数组成，它们或3的幂，或是若个不同的3的幂之和求该数列的第100项。 （第4届美国数学邀请赛试题解：将已知数列写成3的方幂形式：a 30,a ,a 30,a 32,a 3230,a 32,a 3230,1 2 3 4 5 6 7易发现其项数恰好是自然数列对应形式的二进制表示：即120,221,3

20,422,522

20,622

2,722

20,由于100＝(1100100) 26210036

2535

2232

981。例5．1987可以在b进制中写成三位数xyz，如果xyz1987，试确定所有可能的x,,y,z和b。 （1987年加拿大数学竞赛试题xb

1987xyz25x(b

y(b162，1963即(b1)xy1962232109，1963由b10知b19。由1962b2

1知b

45故9b145；又因为1962232109 有12个正约数，分别为1,2，3,69,18,109,218,327,654,981,1962，所以b118，从而b19。又由1987519291911xyz11.例6．设n是五位数（第一个数码不是零，m是由n取消它的中间一个数码后所成的四位数，试确定一切n使得

n是整数。 （第3届加拿大数学竞赛试题）m解：设nxyzuvx104

y103

z102

u10v，其中x,y,z,u,v{0,1,2,,9}且x1；mxyuvx103y102u10v；nk

是整数，可证9mn，即x13y12u1)x14y13z12u1vm即80u8v103x102y102z，这显然是成立的；又可证n1m，即x14y13z12u1v＜1(x13y12u10)即102z103x102y102u10v，这显然也是正确的。于是9mn，即9k11，又因为k是整数，从而k10；于是n10m，即x14y13z12u1v＝1(x13

y102

u10v)即z10290u9v9(10v)，而9|102z但3102知z9t(t为正整数）从而t10210uvtuv0nN103其中10N99。7．若n且n是其各位数字和的倍数，这样的n有多少个？（2004年南昌竞赛试题））若n为个位数字时，显然适合，这种情况共有9种；若n100若n为二位数时，不妨设nab，则n10ab，由题意得(ab|b)即10abZ即9a

Z也就是(ab)|9a；ab ab若b09若b0，则由aba，故3|(ab)若(ab)|9，则显然可以，此时共有2＋8＝10个；若（ab）9，则ab6ab1224,42,48,8449＋1＋9＋10＋4＝33例8．如果一个正整数n在三进制下表示的各数字之和可以被3整除，那么我们称n为“好2005个“好的”正整数之和是多少？2005年中国奥林匹克协作体夏令营试题解：首先考虑“好的”非负整数，考察如下两个引理：13n是非负整数13（，引理1得证。299n,9n1,9n8（n是非负整数）中，有且仅有33出现一次。199n,9n1,9n8（n是非负整数）中，有3另一方面，在这三个“好的”非负整数的三进制表示中，最高位与倒数第三位完全相同，倒数第二位分别取0,1，2。若它使它们成为“好的”非负整数，则最后一位不相同，引理2得证。将所有“好的”非负整数按从小到大的顺序排成一列，设第2004个“好的”非负整数为m，1，得20033m20043，即6009m6012。设前m个“好的”正整数之和为Sm

，由于前2003个“好的”正整数之和等于前2004个“好的”非负整数之和。因此S2003(0122003320046023022；又因为(6013) (22020201)和(6015) (22020210) 都是“好的”正整数。因此前10 3 10 32005年“好的”正整数之和是：S S 601360156035050。2005 2003第二节整数的性质及其应用（1）基础知识全平方数及整数的尾数等几个方面的应用。整除的概念及其性质在高中数学竞赛中如果不加特殊说明定义：设abb0，若存在整数c，使得abc则称b整除a，记作b|a，并称b是a的一个约(因称a是b的一个倍数如果不存在上述c则称b不能整除a记作b a。由整除的定义，容易推出以下性质：若b|c且c|a，则b|a()；若b|a且b|cb|acb|a及b|cuv有b|aucv。更一般，若a,

,,

bb|

)a|

，则a|cb 其中1 2 n

1 2 n

i iii1cZ,i1,2,,n；i若b|a，则或者a0，或者|ab|，因此若b|aa|b，则ab；ab互质，若a|cb|c，则ab|c；pp|aaa1 2 n

p能整除aa1 2

,,an

中的某一个；特别地，若p是质数，若p|an，则p|a；(6)()ab为整数，b0，则存在整数qrabqr，其中0rb，并且q和r由上述条件唯一确定；整数q被称为a被b()商，数r称为a被b除得的余数。注意：r共有b1。若r0，即为a被b整除的情形；a a易知，带余除法中的商实际上为b（不超过b的最大整数，而带余除法的核心是关r0rb。证明b|a的基本手法是将a分解为b与一个整数之积，在分解式在这类论证中应用很多，见例1。若nxn

y

(xy)(xn1

xn2yxyn2yn1)；若n是正奇数，则xny）

yn

(xy)(xn1xn2yxyn2yn1)（在上式中用y如果在等式

am

中取去某一项外，其余各项均为c的倍数，则这一项也是c的倍数；

i knn的倍数；n6整除；：奇数=偶数＝偶数＝偶数＝偶数＝奇数＝差仍为奇数，偶数个奇数的和、差为偶数，奇数与偶数的和为奇数，和为偶数；奇数的平方都可以表示成的形式，偶数的平方可以表示为或8m4的形式；任何一个正整数n，都可以写成n2ml的形式，其中ml为奇数。完全平方数及其性质能表示为某整数的平方的数称为完全平方数，简称平方数。平方数有以下性质与结论：平方数的个位数字只可能是0,1，4,5，6,9；偶数的平方数是4的倍数，奇数的平方数被81，即任何平方数被401；奇数平方的十位数字是偶数；十位数字是奇数的平方数的个位数一定是6；33133整除。因而，平方数被9也合乎的余数为0,14,9除的余数也只能是4,7；平方数的约数的个数为奇数；任何四个连续整数的乘积加1，必定是一个平方数。设正整数a,b之积是一个正整数的k次方幂（k2，若（a,b）＝1，则a,b都是整数的k次方幂。一般地，设正整数a,b,,c之积是一个正整数的k次方幂（k2ab,c两两互素，则ab,c都是正整数的k次方幂。整数的尾数及其性质整数a的个位数也称为整数a的尾数，并记为G(a)。G(a)也称为尾数函数，尾数函数具有以下性质：（1）GG(a))G(a)（）G(a a1 2

an

)＝G[G(a1

)G(a2

)G(an

)]；（3）G(aa a) )G(a)G(a

)] ；（4）G(10a)0 ；1 2 n 1 2 nG(10ab)G(b)；（5）若ab1c，则G(a)Gb)（6）G(a4k)G(a4),a,kN；（7）G(a4kr)G(ar),k0,0r4,a,k,rN； G(ab

为奇数，b2

是偶数1（8）G(abb2bn1

)G(a4),b

为偶数，b

为奇数或b2

b同时为偶数时21G(abb11

b同为奇数时2整数整除性的一些数码特征（即常见结论）若一个整数的未位数字能被5）整除，则这个数能被5）整除，否则不能；3（9）3（9）整除，否则不能；4（或25）4（或25）不能；若一个整数的未三位数字能被或125）整除，则这个数能被或125）不能；若一个整数的奇位上的数码之和与偶位上的数码之和的差是1111整除，否则不能。质数与合数及其性质（）单位数1）质数（素数：一个大于1的因数只有1和它本身，则称为质（素）（）如果一个自然数包含有大于1身的因子，则称这个自然数为合数。有关质（素）数的一些性质a若a,a1则a的除1以外的最小正因数q是一个（素数如果qa则q ；ap是质（素）ap|a或（ap）＝1；设a,a,a为n个整数，p（素p|aaap必整除某个a（i；1 2 n 12 n i4（算术基本定理任何一个大于1的正整数a（素（计较因数的排列顺序；1（5）任何大于1 的整数a能唯一地写成apa11

pa22

pakkk

,i,,k ①的形式，其中pi

为质（素）数（pi

p(ij。上式叫做整数a的标准分解式；j若a的标准分解式为①，af(af(a

1)。典例分析例．证明：1被1001整除。2000个0

1 2 k证明：11020011103)6671103103)666103)665103]2000个0所以103

(100)整除1。2000个0例nS(n)为n的十进制表示中数码之和9|n的充要条件是9|S(n)。n

10ka10a（这里0a

9，且a

0

aa，k 1 0 i k 0 1 n于是有nS(n)ak

a1

(101) ①对于1ik，知9|(10i

，故①式右端k9的倍数，从而由整除的性质可知它们的和也能被9整除，即9|(nS(n))。由此可易推出结论的两个方面。3．设k1是一个奇数，证明L对于任意正整数n，数2k不能被n2整除。n1时，结论显然成立。设n2，记所说的和为A，则：2A2(2knk3knk(nk2k。k是正奇数，从而结于每一个i2，数ik

(n2i)k被i(n2i)n2整除，故2A被n22，从而A不可能被n2整除（注意n22。例．设,n是正整数，m2（2

1（2

1。证明：首先，当nm时，易知结论成立。事实上，mn时，结论平凡；当nm时，结果可由2n

12m1

12m1推出来（注意m2。nm的情形可化为上述特殊情形：由带余除法nmpr,0rmq0，由于n1mqrr1，从而由若n是正整数，则nn12x2知(2m|(2mq；而0rm，故由上面证明了的结论知(2m(2r（注意r0时结论平凡，从而当nm时，也有（2

1（2

1。这就证明了本题的结论。例5．设正整数a,b,c,d满足abcd，证明：abcd不是质（素）数。abcdad

m其中(mn1a

m a意味着有理数的分子、c b n c n c分母约去了某个正整数u后得既约分数mn

，因此，amu,cnu ①同理，存在正整数v使得bnv,dmv ②abcd＝(mn)(uv1的整数之积，从而不是素数。注：若正整数abcd适合abcd，则abcdcd cd (ac)(ad)证法二：由abcd，得b

，因此abcda cd ，a a a(ac)(ad)因为abcd是整数，故 也是整数。a若它是一个素数，设为p，则由(ac)(ad)ap ③可见p整除(ac)(ad)，从而素数p整除ac或ad。不妨设p｜ac，则acp，结合③推出ada，而这是不可能的（因为d1。6．求出有序整数对n）1m99n99，(mn)23mn是完全平方数。 （1999年美国数学邀请赛试题解：由于1m99，1n99可得：(mn)23mn(mn)24(mn4(mn2)2。又(mn)2

(mn)2

3mn，于是(mn)2

(mn)2

3mn(mn2)2若(mn)23mn是完全平方数，则必有(mn)2

3mn＝(mn1)2。然而(mn)2

3mn＝(mn

nm，于是必有nm10mn1，此时n2,3,,99m1,2,,98。所以所求的有序整数对（n）98对：(m,n)(1,2),(2,3),(3,4),,(98,99)。a,b满足2a

a

bab和2a1都是完全平方数。证法一：已知关系式即为2a2

a

b2(a

（2006年ft东省第二届夏令营试题）b2)(ab)b2（ab（2ab1）＝b2 ①若ab0（或者说a,b中有一个为0时，结论显然。不妨设ab且ab0，令(ab)d，则aadbbd(ab)11 1 1 1从而ab＝(a1

b)d，将其代入①得2a1

2da b1

3b1

2d ②因为d|2a1

2d，所以d|(a1

b，从而da1

b；1而②式又可写成(a1

b)(2a1 2b1

1)bd2；1因为(ab)d且(ab1 1

)1，所以(a1

b,b1

)1(a1

b)1所以(a1

b)|d，从而a b1 1

d。所以da1

b，所以ab＝(a1

b)dd2，从而ab1所以2a1

b2 b( )2也是完全平方数。d2 d证法二：已知关系式即为2a2

a

b2(a2

b2)(ab)b2（ab（2ab1）＝b2 论证的关键是证明正整数ab与2a1互素。记d（ab，2ab1。若d1，则d有素因子p，从而由①知p|b2。因为p是p|bp|abp|ap|2a1p|1，这是不可能的。d1，从而由①推知正整数ab与2a1都是完全平方数。例8．证明不存在正整数n，使2n2+1，3n2+1，6n2+1都是完全平方数。证明：假设存在这样的正整数n，使2n2+1，3n2+1，6n2+1都是完全平方数，那么2n21（3n2（62）也必定是完全平方数。而2n21（321（6n1）36+3n+12+；(6n3

3n)

36n6+36n4+9n2；(6n3

3n

36n6+36n4+12n3+9n2+6n+1；所以(6n3

3n)

（2n2（321（6n1＜(6n

n)22n21（321（6n2）为完全平方数矛盾。n9．数列n

的通项公式为

1 1 5n 1 5n

，nZ+．5f 5n

2 2 记S

+C2f

+Cnf

，求所有的正整数n，使得S

能被82005年上海竞赛试题）n n1 n2 nn n1 5解：记1 5

, ,2 2S n

n5i15

Ci 1 1 5

i

n51i051

Ci n

i 1

Ci

Cii

1n1n553 53 5

n n 3 53 5515

n

n5 5

2 2

注意到

3,3 5 1，可得3 533 53 53 53 53 553 53 5153 53 5

n1

nS n2

2 2

2 2 2

2 3Sn1

Sn

3 533 53 5

S因此，Sn+2除以8的余数，完全由SS

、n+1

n除以8的余数确定SC1SC11 1

C1f

C2

3，故由式可以算出

各项除以8的余数依次是1,3，1 2 21 2 2 n0,5，7,0，1,3，……，它是一个以6为周期的数列，从而8Sn故当且仅当38S

3nn练习题1pp236p1的因子。p2p1pp1p23的余数各pp236p1的因子。2．设mn0，证明：(22

)|(22

1)；解：由22

1(22n122n1)2mn122n1]，故(22n1

)｜（22

1。又因为22n11(22

)(22

)，从而(22

)｜(22n

1)，于是由整除的性质知(22n

)|(22

1)。证明：对于任意正整数n，数

22005n2005 不能被n2整除。2（n2即可。因为若n是正整数，则xn

y

(xy)(xn1xn2yxyn2yn1)；若nxn

yn

(xy)(xn1xn2yxyn2yn1)；n2｜22005n2005n2｜32005(n1)2005，……，n2｜n200522005所以n2｜2（22005n2005。又因为n232，所以n2 2，所以n2 2（22005n2005）＋2即（n2命题得证。已知n60|6n

3n

2n

1。证明：因为若n是正整数，则xn

y

(xy)(xn1

xn2yxyn2yn1)；若nxn

yn

(xy)(xn1xn2yxyn2yn1)；所以3|6n

3n，3|2n

1，从而3|6n

3n

2n

1；4|6n

2n，4|3n

1，从而4|6n

3n

2n

1；5|6n

1，5|3n

2n，从而5|6n

3n

2n

1；又)1且34560，所以60|6n

3n

2n

1。设ab、c为满足不等式1＜a＜b＜c的整数，且（ab-1）（bc-1）（ca-1）能被abc整除，求所有可能数组（1989年上海竞赛试题解 ∵（ab-1）（bc-1）（ca-1）=a2b2c2-abc（a+b+c）+ab+ac+bc-1，①∵abc|（ab-1）（bc-1）（ca-1）.∴存在正整数k,使ab+ac+bc-1=kabc, ②k= ＜ ＜ ＜＜ ∴k=1.若a≥3，此时1= - ＜ 矛.已知a＞1. ∴只有a=2.当a=2时，代入②中得2b+2c-1=bc，即 1= ＜∴0＜b＜4，知b=3，从而易得c=5.说明：在此例中通过对因数k的范围讨论，从而逐步确定a、b、c是一项重要解题技巧.第三节整数的性质及其应用（2）基础知识最大公约数与最小公倍数是数论中的一个重要的概念，这里我们主要讨论两个整数互素、最大公约数、最小公倍数等基本概念与性质。最大公约数）设ab不全为零，同时整除ab的整数（如1）因为ab不全为零，故ab只有有限多个，我们将其中最大一个称为ab的最大公约数，用符号（ab）表示。显然，最大公约数是一个正整数。当（ab即ab的公约数只有1）时，我们称a与b互素（互质。这是数论中的非常重要的一个概念。同样，如果对于多个（不全为零）的整数a,b,,c，可类似地定义它们的最大公约（ab,c（ab,c，则称ab,cab,c两两互素；但反过来，若（ab,c）两两互素，则显然有（ab,c）＝1。ab的符号，不改变（a,b）的值，即(a,b)(a,b)（a,b）（a,b）＝（b,a；（ab）作为b的函数，以a为周期，即对于任意的实数x，有（a,bax）＝（ab）等等。为了更详细地介绍最大公约数，我们给出一些常用的一些性质：（1）设a,b是不全为0的整数，则存在整数x,y，使得axby(a,b)；2（裴蜀定理）两个整数a,b互素的充要条件是存在整数x,y，使得axby1；事实上，条件的必要性是性质x,y使等式成立，不妨设(a,bd，则d|ad|b，故d|ax及d|by，于是d|axby，即d|1，从而d1。若m|am|bm|abab的任何一个公约数都是它们的最大公约数的约数；（4）若m0，则(mamb)m(ab；5 (a,b)d

a,b1（）若

，则 d d

，因此两个不互素的整数，可以自然地产生一对互素的整数；若(ambm1，则(abm1，也就是说，与一个固定整数互素的整数集关(ab1，对于0有(akb1，进而有对0有(akbl)1。设b|ac，若(bc)1，则b|a；设正整数a,b之积是一个正整数的k次方幂（k2，若（a,b），则a,b都是整数的k次方幂。一般地，设正整数a,b,,c之积是一个正整数的k次方幂（k2，若a,b,,c两两互素，则a,b,,c都是正整数的k次方幂。2.设ab是两个非零整数，一个同时为ab倍数的数称为它们的公倍数，ab的公倍数有无穷多个，这其中最小的一个称为ab的最小公倍数，记作ab,c，可类似地定义它们的最小公倍数［ab,c。最小公倍数主要有以下几条性质：a与b的任一公倍数都是的倍数，对于多于两个数的情形，类似结论也成立；ab(ab|ab|（但请注意，这只限于两个整数的情形，对于多于两个整数的情形，类似结论不成立；（3）若ab,c两两互素，则［ab,c］＝｜ab,c｜；（4）若a|db|d,c|d，且ab,c两两互素，则ab,c｜d。典例分析1x,y是正整数，xyxy667120倍，x,y。解：设(x,y)d，则xmd,ynd，其中(m,n)1且mn，于是[x,y]mnd。mdnd667 (mn)d23

(1)所以 mnd d

120

即 mn2335

mn及（2）可得：m

;m2

m3;m4

m5;m6

m8;m10。n

n60

n40n

n24n

n15n12由（1）可知只能取m5m8; n24n15从而d23或29，故x115,y552或x232,y435。2．设mn0mn|m2n2)，则mn。证明：设(mndmm1

d，nn1

d，其中(mn1 1

)1。于是，已知条件转化为mn|(m11 1

n2)，故更有m1 1

|(m21

n2)，从而转化为m1 1

|n2，但是(m,n1 1

)1，故(m,n1

2)1，结合m1

|n2，知必有m1 1

1，同时n1

1，因此mn。3．设正整数abc1

ab c，证明ab是一个完全平方数。ab设(a,bdaadbd(a

,b)1(a,b,c)1(b,c)1，1现在问题中的等式可以转化为dab11

1ca1

1 1cb ①1由此可见a1

整除cb1

。因为(ab1 1

)1，故a1

|c，同样可得b1

|c，再由(ab1 1

)1便可以推出ab11

|c。设ca1

bk，其中k是一个正整数。一方面，显然k整除c；另一方面，结1合①式，得dk(a1

b)，故k|d，从而k|cd)，但(cd)1，故k1。1da1

b，故abd(a1

bd2，这样就证明了ab14abpq使得对任意的正整数nna与qnb互质？L[ab]rLsL，则(rs)1xy使得rxsy1，a bpxqyndn(pna,qnb)，有dn|rp即dn|rpsqrpsqrxsy1raLsbdn|1dn1，即对任意的正整数n（pna，qnb）1。例5．已知f(x)x2002x20011，证明：对于任意的正整数m，都有m,f(m),f(f(m)),f(f(f(m))),两两互素。（2002年克罗地亚竞赛试题）证明：设pn

(x)fff((x)（fn次f(0),f1，故对于nN有pn

(01pk

(x0pk

(0)1n

m1d1

(m)和p )又p (m)＝p(p())则当p(

(m))k kl l k l k除以p(m)时余数为1，即p (m)＝Qp(m)＋1。所以d|1，矛盾！k kl k从而可知m,f(m),f(f(m)),f(f(f(m))),两两互素。例6．求出所有的正整数对(m,n)，使得

n31mn

是一个整数。（2006年ft东省第二届夏令营试题）解：由于(m3mn1且mn1|n31mn1|mn1|m3n31m31mn1|m31，所以n是对称的。不妨设mn。mn

n31 n2n1 1 n N*n2，从而mn＝2；n21 n1 n1mn时，若n1时，则有m1|2，所以m23；n31若n2时，由于 是一个整数，从而kN*使得mn1kn1

n31n31n

，所以kn1＜1 1 。mn1 n2

n

n1又由于n2kN*，所以k1。所以31n)m)m3nm1 ，从而n21 2m n1 N*n23，所以m5；n1 n1综上知所有的(m,n)为（2,2）,(2,1),(1,2),(3,1),(1,3),(5,2),(2,5),(5,3),(3,5).例已知a,b,m,nN*(a,b),a2anbn|ambm的充要条件是n|m吗？（2006年ft东省第二届夏令营试题）

akn(anbnbn(aknbknanbn|ak

bk

anbn|aknbkn；又ar

br

arn(anbnbn(arnbrn)，所以anbn|arbranbn|arnbrn；mnqr(0rn，则有an

bn

|anq

bnqranbn|a(q1)nrb(q1)nr anbn|a(q2)nrb(q2)nr anbn|ar(1)qbr又因为nr，所以ar

(1)qbr

an

bnm从而上式r0且q为奇数，即anbn|ambm的充要条件是n|m且n

为奇数。8．我们知道23191个质因子，且

|23

1；23215133319有2个质因子，且33|221………………如此下去我们可以猜想kN*, 2k1至少有k个质因子且3k1|2

1。试证明之。ak纳法证明b

＝2k1，则ak是整数。

＝3kbk

，即要证bk

（2006年ft东省第二届夏令营试题k1个质因子。下用数学归kk1时，结论显然；假设nk时，成立；当nk＋1时，因为a (a－1)3+1=a3－3a2＋3a；kk k k k因为3k|a，所以3k2|a ，即b 是整数。k kk下证b 至少有k个质因子。k1a 3k2b ＝a3－3a2＋3a＝(3kb)3－3(3kb)2＋3(3kb).kkk k k k k k因为b

＝b(32kb23k

1)，令c

32kb23k

1，则b

＝b ckk k k

k k k

kk k由于(ck

,3)=1cbk k

)=1，从而ck

必有异于bk

质因子的质因子，所以b 至少有k个质因子。 证毕！k1练习1．若nNm是奇数，则(2m

1。2m1与2n11n不好处理，由m为奇数这一条件，我们可以想到2m

|2mn1从而找到思路。由于m为奇数，故2n1|2mn

1，又2m1|2mn1，从而（2m12n1）（2mn

,2mn1，而（2

2mn1）＝（2mn

1,2）＝1，故(2m

1)1。2．若17|(2a+3b),试证：17|(9a+5b).证明：注意到2(9a+5b)=9(2a+3b)－17b,于是17|2(9a+5b).但是(17,2)=1,即得17|(9a+5b).na设nana

不是整数，则必为无理数。

是非整数的有理数，则可设nac,b1,(b,c)1，于是anabna

cn(b,c1bn故可知(bncn)1。但bn1，因而bn

|cncnbnn

a是整数矛盾！证毕。a,b0ax+by(xyNd，试证：d=(a,b).n n 5.F＝2＋1,F)=1,mnn n 第四节同余基础知识三个数论函数(Gauss(Euler)函数(x)和它的计算公式。高斯(Gaussx]设x是实数不大于x的最大整数称为x的整数部分记为[x[x]称为x的小数部分，记为｛x。例如0.］0，[50],[],[]}1415 }7等等。由[x],{x}的定义可得如下性质：1.x[xx};01；2.x1[xx[x1；性质3.设aZ，则[ax]a[x]；4.[xy[xy];{x{x}{y};[x]15.[x[x]1

xx；性质6.对于任意的正整数n，都有如下的埃米特恒等式成立：；[x][x1][x2][xn1][nx]；n n n为了描述性质7，我们给出如下记号：b|a，且a，则称为b恰好整除a，记为b||a。例如：我们有24||2000,53||200011a能唯一地写成apa11

pa22

pakkk

ik的形式，其中pi

为质（素）数（p pi

(ijpai||a,i1,2,k。i7.p|，则

[ ][n][nnp p2 p3n请注意，此式虽然被写成了无限的形式，但实际上对于固定的n，必存在正整数k，pk

n，因而0pk

1，故

n0，而且对于mk时，都有[n0。因此，pk pmn!p的指数的计算方法。除数函数正整数n的正因数的个数称为除数函数，记为d(n)。这里给出d(n)的计算公式：1)( )，,,, 为素数唯一分解定理中的指数。为了叙述1 2 k1 2 k地更加明确，我们组出素数唯一分解定理。算术基本定理（素数唯一分解定理：任何一大于1若不考虑素数乘积的先后顺序，则分解式是唯一的。242223。当一个整数分解成素数的乘积时，其中有些素数可以重复出现。出现了三次。把分解式中相同的素数的积写成幂的形式，我们就11aapa11

pa22

pakkk

,i,,k （1）此式称为a1唯一的（不考虑乘积的先后顺序。1.若a的标准分解式是式，则d是a的正因数的充要条件是：1dp11

p2

pkkk

,0i

a,i1,2,,,k （2）i应说明2）不能称为是di

可能取零值（d也有可能不含有某个素因数pi

，因而i

0）2.设abc，且(b,c)1，若a是整数的k次方，则bc也是整数的k次方。特别地，若a是整数的平方，则bc也是整数的平方。(Euler)函数(n)设nn1中与nn(n)n1的标准分解式是npa11

pa22

pakkk

,i1,2,,,k，则(n)的计算公式是：(n)papapa(p1)(p 1)(

1),i1,2,,,k1 2 k1 2 k 1 2 k例如：(2000)(2453)2453(21)(51)800；(2001)(32329)(31)(231)(291)1432.以下我们讲述同余的概念：同余的概念是高斯（Gauss）在1800年左右给出的。设m是正整数，若用m去除整数a,b，所得的余数相同，则称为a与b关于模m同余，记作ab(modm)，否则，称为a与b关于模m不同余。1.（同余）设m0，若m|ab，则称a和b对模m同余，记作ab(modm；若不然，则称a和b对模m不同余，记作a b(modm)。例如：344(mod15)，10007等等。当0bmab(modm，则称b是a对模m的最小非负剩余。a和bma与bm固定的模m，模m的同余式与通常的等式有许多类似的性质：1.ab(modm的充要条件是abmt,tZm|ab。2.同余关系满足以下规律：1（反身性）aa(modm)；2（对称性）若ab(modm)，则ba(modm)；3（传递性）若ab(modm)，bc(modm)，则ac(modm)；4（同余式相加）若ab(modm)，cd(modm)，则acbd(modm)；5（同余式相乘）若ab(modm)，cd(modm)，则acbd(modm)；反复利用4（，可以对多个两个的（模相同的）同余式建立加、减和乘法的运算公ab(modmc为整数且k0akcbkc(modm；但是同余式的消去律一般并不成立，即从acbc(modm)未必能推出ab(modm)，可是我们却有以下结果： m acbc(modmabmod(mc，由此可以推出，若(cm)，则有 ab(modm，即在c与m互素时，可以在原同余式两边约去c而不改变模（这一点再一次说明了互素的重要性。现在提及几个与模相关的简单而有用的性质：若ab(modmd｜m，则ab(modd；若ab(modmd0，则dadb(moddm；若aka,m

,,

])，特别地，若m,m,,mi两两互素时，则有ab(modmm1 2

1 2 nm)；n

1 2 n3.若

b(odm),i,,k，则kakb(modm)；k ak b；i i i i i ii1 i1 i1 i14f(x是系数全为整数的多项式，若ab(modmf(a)f(b)(modm。。2.设(am)1d是使ad0

m成立的最小正整，则称d为a对模m的阶。0在取定某数m后，按照同余关系把彼此同余的整数归为一类，这些数称为模m的剩余类。相同，这样我们就把全体整数按照模m划分为了mKr|qZ,0余数rm。在上述的m个剩余类中，每一类任意取一个剩r余，可以得到m个数a0

,a,,1

，称为模m的一个完全剩余系。例如关系模7，下面的每一组数都是一个完全剩余系：0，1，2，3，4，5，6；-7，8，16，3，-10，40，20；-3，-2，-1，0，1，2，3。显然，一组整数成为模m的完全剩余系只需要满足两个条件）有m（2）各数关于模mmm1;即除数为m时，余数可能取到的数的全部值。当m为奇数时，绝对值最小的完全剩余系是：m1,,1,0,1,,m1；2 2当m为偶数时，绝对值最小的完全剩余系有两个：m1,,1,0,1,,m；2 2m,,1,0,1,,m1。2 2念给出，希望大家好好地研究：定义3.（同余类）设Mr为模m的同余类。

x|xZxmrm1，每一个这样的类说明ma和bma和b属同一类，否则不属于同一类，每一个这样的类为模m的一个同余类。由带余除法，任一整数必恰与0,1,……，m1中的一个模m同余，而0,1m1m个数彼此模m不同余，因此模m共有m个不同的同余类，即M {x|xZ,xm)},rm1。r22k和2k1（k为任意整数。定义4（剩余类）设m是正整数，把全体整按对模m的余数分成m类，相应的m个集合记为：K,K,,K 其中K r|qZ,0余数rm称为模m的一个0 1 m1 r剩余类。以下是几条常用性质：Z

K 且K Ki i 0im1

(ij)；每一个整数仅在K,K,,K 的一个里；0 1 m1对于任意abZ，则abKr

的充要条件是ab(modm)。定义5.（完全剩余系）yy,,y称为模m的完全剩余系，如果对任意a有且仅1 2 s有一个yj

是a对模m的剩余，即ayj

(modm)。换一种说法更好理解：设K,K,,K

为模m

中任取一个a

，得m个数a

,aa 组0 1

r r 0

m1成的数组，叫做模m的一个完全剩余系。说明：在m个剩余类中各任取一个数作为代表，这样的m个数称为模m的一个完全剩1余系，简称模m的完系。换句话说，m个数c1

,c,,c2

称为模m的一个完系，是指它们m不同余，例如0,1，2m1m的一个完系，这称作是模m的最小非负完系。（）m个整数构成模m的一个完全剩余系两两对模不同余；（2）若(am)1x与axb同时跑遍模m的完全剩余系。典例分析例1．试解方程：56x15x7。8 5解：因为左边是整数，因而右边的分式也应该是整数，所以56x15x715x756x08 5 5 8 于是8190x0，从而08190x

1，故08190x40。40 40但是15x7是整数，故15x7，tZ ，代入前面的不等式，得503930t40,tZ，直接观察即知tx

7,4。155例2．数100！的十进位制表示中，未尾连续地有多少位全是零？100101025100251005由10010020424即可知100！的未尾连续地有24位全是数码零。5523．试求(2573346)2650解：由于(x33

46)26x的整系数多项式，而2577(mod50)，于是知(2573346)26(73346)26(mod50)。又注意到72

49(mod50)，故25334)267334)26(mo5)2167426((1)16746)26(746)265326326(mod50)又

24325077(mod50)，所以(2573346)26(35)53(7)53(72)2732129(mod50)注意到02950，因而29就是所求的余数。说明：在上述过程中，我们已经看到72

491(mod50)的作用。一般而言，知道一个整数的多少次幂关于模同余于1是非常有用的。事实上，若ak

1(modm)，则对大的指数nnkqr,0rkanakqr(ak)qararm，这里余数r是一个比n小得多的数，这样一来，计算an的问题，就转化成了计算余数r次幂ar的问题，从而使计算简单化。例4．设a101010，计算某星期一后的第a天是6星期几？7103(mod7102

32

2(mod7)，103332361(mod7)，因而1061(mod7)。为了把指数a的指数1010写成6qr的形式，还需取6为模来计算1010。为此我们有104(mod6)102424(mod6)103434(mod6)10104(mod6)，所以10106q4(mod6)a106q4106)q104104347)这样，星期一后的第a天将是星期五。5p，使4p

1与6p

1也是素数。4p

1与6p

1也是素数，应该是对p除以某个数素q的余数进行分类讨论，最后确定pq什么效果，试验q发现对本题不起任何效果，现对q5展开讨论。解：设u4p2

1，v6p

1p5kkZrr14p

5)，u4p

1410(mod5)；r23p

5)，v6p

12410(mod；即r0时，u,v为5的倍数且比5大，不为质数。故r0，此时p5，u5241101v5261151都是素数。p5。注：要使几个数同为质数，一般是对这几个数也合乎以某一质数的余数来确定，如p,p2,p4均为质数，可得p只能为3，由于这是p的一次式，故三个数就模3，而二次式对三个数就模5，四个数一般就模7了。6．求满足|12m5n|7的全部正整数n。分析：如果5n

12m

7，两边mod4，得13(mod4)，这是不可能的；12m

5n

7，而n中有一个大于1，则另一个也大于 1，mod3得n，故n为奇数，mod8，得5n8528，n为奇数，从而5所以mn1为唯一解。注：在解不定方程时，往往要分情况讨论，也常常利用同余来导出一些性质求出矛盾！例7．数列{an

a0

n1

,nN.7a 7a 45a236n n证明1）对任意nN,a 为正整数(2对任意nN,aa 1为完全平方数。n n n1（2005年全国高中数学联赛试题）1）a1

5,且{an

}2an1

7an

45an

36两边平方整理得a2n1

7an

an1

an

90 ①an

7a

an1

a2n1

90 ②①-②得(a a )(a a 7a)0, a aa a 7a 0n1 n1 n1 n1 n n1 n n1 n1 na 7a a . ③n1 n b1由③式及a0

a1

5可知，对任意nN,an

为正整数.（2）将①两边配方，得(a

n1

a)2n

9(an

an1

an

an1

1

a n13

n)2. ④由③式a

an1

9an

n1

a)≡(an

an1

)mod3n

a a∴an1

a≡n

aa1

≡0（mod3）∴

n13

n为正整数，④式成立.aa 1.n n13n18

n(2n

可以写成有限小数，那么自然数n的值是多少？解：由于(n,3n1若1与2n1p

1n(2n

是既约分数；若12n1dd1，设1da,2n1db，d(2a)2(3n3(2n51与2n1p的。由于p可以写成有限小数，故约分之后p的分母除了2,5以外，没还有其它的公约数，因此n(2n2k5m。 n2k因为2n1是奇数，(n,2n1，故 ，即2k2n15m

5m

1。由于5m12(mod4故2k4，从而k0，即mn1，故只有np才是有限小数。练习56x 15x7 7 4试求方程8

的实数解x（答案：x , ）5 1552(n165n（答案：17，32，34，40，48）31999)5025（答案：24）nan

1(modm)，这些n中最小的正整数为，试证：|n。特别地，若(am1，则|(m。证明：设nr,0r，则易知ar

(a)qar

an

1(modm)，但是最小的正整数，故r0，即nq。设a是任意整数，试证下面形状的数都不是完全平方数（）a22）5a

6。）a22不同余x2(mod)；（2）5a

6a2

223(modx2

01(mod5。求所有满足8x

15

17z的正整数三元组(x,y,z)。第五节初等数论中的几个重要定理基础知识定义（欧拉(Euler)函数）一组数x,x1 2

,,xs

称为是模m的既约剩余系，如果对任意的1js，(xj

m)1且对于任意的aZ(amxj

是a对模m的剩余，即axj

(modm)。并定义(m)s{1,2,,m}中和m互质的数的个数，(m)称为欧拉（Euler）函数。这是数论中的非常重要的一个函数，显然(1)1，而对于m1，(m)就是1,2，…，m1中与mp是素数，则有p)p1。引理：(m)m 1P|mP

－（证明略。P定理1（欧拉Eule）定理）设(a,m)＝，则a(m)

1(modm)。m的一个既约剩余系bb1 2

,,bs

,(s(m))，考虑ab1

,ab2

,,abs

，由于a与m互质，故abj

js)m互质，且有abi

abijs)，于是对每个j1js都能找到唯一的一个1j)sabj

b(j

(modm)，这种对应关系是一一的，从而

ab)j

b

(mo)

b(mo)asj

b)j

b)(modm)。j(,sj1

b)1，asm，故am)m。证毕。jam)m，我们得设法找出(m个n相乘，由(m个数我们想到1,2,mm互质的(m的个数：aa1 2

,,m

(am)＝1maa1,aa2,,)也是与m 互质的(m)个数，且两两余数不一样，故maa1

a

(m

aa1

,aa2

,,m)

a(m) aa1 2

a

(m

（modm ），（aa a m）＝1，故am)m。1 2 (m)余系来解决问题。定理2（费尔马（Ferma）小定理）对于质数p及任意整数a有a

a(modp)。papa

0pap1由引理及欧拉定理得()p,()(mo)a1(moap(mo)，由此即得。2*推论papap11(modp。定理3（威尔逊（Wilso）定理）设p为质数，则(p)!(modp)。p1个数，然后来对应乘法。证明：对于(x,p)1x,2x,p1)x中，必然有一个数除以p余1，这是因为x,2x,p1)xp。从而对xpypxyp；若xy1

xy2

p(x,p)1xy1

y)p)，p|(y2

y，故2yy1

,p，有xy1

xy(modp)。即对于不同的x对应于不同的y，即21,2,,p1p余1，xx2p，即与它自x

1p)(x1)(x0(modpx1xp，xp1x1。xp1p1pp1。

(x)（1jkxjf(x)0(modmj

)（1jk）称为同余方组程。特别地fi

(x)均为x的一次整系数多项式时，该同余方程组称为一次同余方程组.若整数c同时满足：f

(c)0(modm)j j1jkMc

x|xZxm（mmm1 2

,,mk

]）称为同余方程组的一个解，写作xc(modm)定理4（中国剩余定理）设m,m1 2

,,mk

是两两互素的正整数，那么对于任意整数a,a1

,,ak

，一次同余方程组xaj

(modmj

，1jk必有解，且解可以写为：xM

Na1 1

M Na2 2

M Nak k

(modm)这里mmmmM1 2 k

mik)mi

满足M Nj j

mj

)，1jk（即N 为j

对模mj

的逆。中国定理的作用在于它能断言所说的同余式组当模两两互素时一定有解，而对于解的形式并不重要。定理5（拉格郎日定理设p是质数，n是非负整数，多项式f(x)axn

a1

xa0是一个模p为n次的整系数多项式（即p an解（p有意义的情况下。

，则同余方程f(x)0(modp)至多有n个6：若l为a对模ms为某一正整数，满足as

1(modm)，则s必为l的倍数。意想不到的作用，如：n2为奇数时，n2

0(mod9) 时。这里我们 0(mod4) 为偶数时 0(mod3) 不整时只介绍几个较为直接的应用这些定理的例子。典例分析1.设ab191|a12b12。91713ab1知a1(7,aa1，但是(7)12a12(a6)27a121(mod13，从而a12b12。

b1211，即91|a12b12。注明：现考虑整数a的幂anaa2,an,若有正整数k使ak

1(modm)，则有an

ar(modm)，其中nkqr,0rk；因而关于mod(maa2,an,的项依次同余于aa2,ak,aa2,ak,a,这个数列相继的k项成一段，各段是完全相同的，因而是周期数列。如下例：2100，且使11|

7n

4成立的自然数n的和。解：通过逐次计算，可求出3n关于mod11的最小非负剩余（即为被11除所得的余数）为：3345343因而通项为3n的数列的项的最小非负剩余构成周期为5的周期数列：3，9，5，4，1，3，9，5，4，1，………类似地，经过计算可得7n的数列的项的最小非负剩余构成周期为10的周期数列：7，5，2，3，10，4，6，9，8，1，………于是由上两式可知通项为3n

7n

4的数列的项的最小非负剩余，构成周期为即上两式周期的最小公倍数）的周期数列：3，7，0，0，4，0，8，7，5，6，………1n1n6n7n4(mo1)11|(3n

7n

4)；又由于数列的周期性，故当10k1n10(k1)时，满足要求的n只有三个，即n10k6从而当1n时，满足要求的n的和为：91k)1k)1k)9

3k13

k101330451301480.k0 k0 k0下面我们着重对Fetmat小定理及其应用来举例：1 1 7例3．求证：对于任意整数x，

x5 x3 x是一个整数。5 3 151 1 7证明令f(x) x5 x35 3 15

x，则只需证15f(x)3x55x37x是15的倍数即可。3，5是素数及Fetmatx5

x(mod5)，x3

x(mod3)，则3x55x37x3x7x5)；3x55x37x2xx而（3，5）=1，故3x55x37x0(mod15)，即15f(x)是15的倍数。所以f(x)是整数。42730|n13n（n为任意整数。f(nn13nf(nn(n1)(n1)(n2n1)(n2n1)(n61；所以f(n)含有因式n7

n,n5

n,n3n,n2nFetmat13|n13n7|n7

n,5|n5

n,3|n3n,2|n2n13，7，5，3，22730=137532能整除n13n。例5．设a,b,c是直角三角形的三边长。如果a,b,c是整数，求证：abc可以被30整除。证明：不妨设c是直角三角形的斜边长，则c2

a

b2。若ab则c2|abc.

a

b2

112，又因为c

1(mod2)矛盾！若3a，3b，3c，因为(3k1)2c23|abc.

)a

b2

112(mod，又若5a，5b，5，因为(5k1)2

5)，(5k2)2

1(mod5)，所以a2

b2

20(mod5)与c

1(mod5)矛盾！5|abc.又(2,3,5)=130|abc.例6．证明：对于任意给定的正整数n，均有连续n个正整数，其中每一个都有大于1的平方因子。证明：由于素数有无穷多个，故我们可以取n个互不相同的素数p,p1 2

,,pn

，而考虑同余组xp2),in ①因为p2,p1

2,,pn

2显然是两两互素的，故由中国剩余定理知，上述同余组有正整数解。于是，连续nx1x2,xnp2,p1 2

2,,pn

2整除。1）n具有某种性质”的问题转化为“找n个两两互素的数具有某种性质易解决的。（2）本题若不直接使用素数，也中以采用下面的变异方法：由费尔马数F 22k1(k0p2F2(ink i i有解，同样可以导出证明。例7．证明：对于任意给定的正整数n，均有连续n个正整数，其中每一个都不是幂数。分析：我们来证明，存在连续n个正整数，其中每一个数都至少有一个素因子，在这个数的标准分解中仅出现一次，从而这个数不是幂数。证明：取np,p1 2

,,pn

xp2),in因为p2,p1

2,,pn

2显然是两两互素的，故由中国剩余定理知，上述同余组有正整数解。对于1inxi

(modp2)故p2|(xi)但由①式可知p2 (xi)即p在i i i i i(xi的标准分解中恰好出现一次，故x1x2,xn都不是幂数。8．设nkn0且k(n1是偶数。xy使得(xnyn1xyk(modn。证明：我们先证明，当n为素数幂p时结论成立。实际上，能够证明，存在x,y使xy且xyk：p2，则条件表明kx