数学竞赛中的数论问题题型全

数学竞赛中的数论问题

定理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． 推论 若p是一个素数，a是任意一个整数，则?a,p??1或?a,p??p． （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． （8）若?a,b??1，则am,bn?1，其中m,n为正整数．

证明 据（6），由?a,b??1可得a,b?1．同样，由a,b?1可得am,bn?1．

mm????????定理7 素数有无穷多个，2是唯一的偶素数． 证明 假设素数只有有限多个，记为p1,p2,若p为素数，则与素数只有 n个p1,p2,若p为合数，则必有pi??p1,p2,,pn，作一个新数 p?p1p2pn?1?1．

,pn矛盾．

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

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

1

注：这个证明中，包含着数学归纳法的早期因素：若假设有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，且ba,ab，则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． （7）若?a,b??1，且abc，则ac．

证明 由?a,b??1知存在整数s,t，使as?bt?1，有a?cs???bc?t?c， 因为aa，abc，所以a整除等式的左边，进而整除等式的右边，即ac．

（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．

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

a为素数得a?|bc，与abc矛盾．

定义6 对于整数a,b,c，且c?0，若c(a?b)，则称a,b关于模c同余，记作a?b(modc)；若c?|?a?b?，则称a,b关于模c不同余，记作ab(modc)．

定理9（同余的性质）设a,b,c,d,m为整数，m?0,

若a?b(modm)且c?d(modm)，则a?c?b?d(modm)且ac?bd(modm)．

证明 由a?b(modm)且c?d(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).

2

nn（4）若a?b(modm)，且对非零整数k有k(a,b,m)，则

ab?m???mod?． kk?k?证明 由a?b(modm)、，有 a?b?mq，又k(a,b,m)，有

abm,,均为整数，且 kkkab?m?abm??q，得 ??mod?．

kk?k?kkk定理10 设a,b为整数，n为正整数， （1）若a?b，则?a?b?a?bn?n?．

?abn?2?bn?1?．

an?bn??a?b??an?1?an?2b?an?3b2?（2）若a??b，则?a?b?a?2n?1?b2n?1?．

a2n?1?b2n?1??a?b??a2n?2?a2n?3b?a2n?4b2?（3）若a??b，则?a?b?a?ab2n?3?b2n?2?．

?2n?b2n?．

a2n?b2n??a?b??a2n?1?a2n?2b?a2n?3b2??ab2n?2?b2n?1?．

,am是小于k的非负整数，且a1?0．若

定义7 设n为正整数，k为大于2的正整数, a1,a2, n?a1km?1?a2km?2??am?1k?am，则称数a1a2am为n的k进制表示．

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

n?a110m?1?a210m?2?n?a12m?1?a22m?2??am?110?am，0?ai?9,a1?0（10进制） ?am?12?am．0?ai?1,a1?0（２进制）

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

唯一的

n?p11p2??2pk?k，其中p1?p2??pk为素数，?1,?2,??2,?k为正整数． （分解唯一性） pk?k则n的正约数的个数为

定理13 若正整数n的素数分解式为 n?p11p2d?n???a1?1??a2?1??ak?1?，

pk?k?1?1． ?pk?1p1?1?1?1p2?2?1?1n的一切正约数之和为 S?n????p1?1p2?1证明 对于正整数n?p11p2 m?p11p2由于?i有0,1,2,

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

pk?k，0??i??i ， ①

,?i共?i?1种取值，据乘法原理得n的约数的个数为d?n???a1?1??a2?1??ak?1?．

3

考虑乘积p10?p11???p1?1??p20?p21??p2?2??p0k?pk1??pk?k，

?展开式的每一项都是n的某一个约数（参见①），反之，n的每一个约数都是展开式的某一项，于是，n的一切约数之和为S?n??p?p?0111??p1?1??p0k?pk?1?pk?1?p1?1?1?1p2?2?1?1???p1?1p2?1pk?k?1?1． ?pk?1注 构造法．

定义8 （高斯函数）对任意实数x，?x?是不超过x的最大整数．亦称?x?为x的整数部分，?x??x??x??1． 定理14 在正整数n!的素因子分解式中，素数p作为因子出现的次数是 ????证明 由于p为素数，故在n!中p的次方数是1,2,?n??n??n???3??2?pp?????p?．

,n各数中p的次方数的总和（注意，若p不为素数，这

句话不成立）．在1,2,?n??n??n??n?,n中，有??个p的倍数；在??个p的倍数的因式中，有?2?个p2的倍数；在?2??p??p??p??p??n?3p个的倍数；…，如此下去，在正整数n!的素因子分解式中，素数p作为因子出3??p?．注 省略号其实是有限项之和．

个p的倍数的因式中，有?2现的次数就为?????n??n??n???3??2??p??p??p?定理15 （费玛小定理）如果素数p不能整除整数a，则pap?p?1?1?．

证明2 改证等价命题：如果素数p不能整除整数a，则a?a?modp?． 只需对a?1,2,,p?1证明成立，用数学归纳法．

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

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

?k?1??k?Cpkp1pp?1?p?1（用了归纳假设） ?Cpk?1 ?kp?1?k?1?modp?．

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

p又素数p不能整除整数a，有?a,p??1，得pa?p?1?1?．

定义9 （欧拉函数）用??n?表示不大于n且与n互素的正整数个数． 定理16 设正整数n?p11p2??2?1??1?pk?k，则 ??n??n?1???1??p1??p2???1?1???．

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

???p???p??1．

4

第二讲 数论题的范例讲解

（12）?2n??0?mod4?,?2n?1??1?mod4?,?2n?1??1?mod8?． （13）任何整数都可以表示为n?2m?2k?1?． 例1-1（1986，英国）设a1,a2,是偶数．（a1,a2,222,a7是整数，b1,b2,,b7是它们的一个排列，证明?a1?b1??a2?b2??a7?b7?,a7中奇数与偶数个数不等）

,a24为该24个数字的任一排

例1-2 ?的前24位数字为??3.14159265358979323846264，记a1,a2,列，求证?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个差恰好为1,2,,14？

解 考虑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,?x1n,，它们中的每一个要么是1，要么是?1．若

x1x2?x2?x3?n??xn1x?0x，求证x4|n． n1???xn?1xn?xnx1?0，

证明 由xi??1,?1?，有xixi?1??1,?1?，再由x1x2?x2x3?知n个xixi?1中有一半是1，有一半是?1，n必为偶数，设n?2k．现把n个xixi?1相乘，有

kk (?1)(?1)?x1x2x2x3xn?1xnxnx1?x12x22xn?12xn2?1，

5

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

例6 在数轴上给定两点1和2，在区间(1,2)内任取n个点，在此n?2个点中，每相邻两点连一线段，可得n?1条互不重叠的线段，证明在此n?1条线段中，以一个有理点和一个无理点为端点的线段恰有奇数条．

证明 将n?2个点按从小到大的顺序记为A1,A2,…,An?2，并在每一点赋予数值ai，使

a? 1, 当Ai为有理数点时，i??与此同时，每条线段A??1,　当AiAi?1也可数字化为aiai?1（乘法） i为无理数点时.a??1,　当Ai,Ai?1一为有理数点，另一为无理数时，iai?1?? ? 1,　 当Ai,Ai?1同为有理数点或无理数点时,记aa)?(?1)k(?1)n?k?1i?1??1的线段有k条，一方面(a1a2)(a2a3)(a3a4)…(an?1an?2?(?1)ki 另一方面 (aa21a2)(2a3)(a3a4)…(an?1an?2) ?a1(a2a3…an?1)an?2?a1an?2??1，

得??1?k??1，故k为奇数．评析 用了数字化、奇偶分析的技巧． 二、约数与倍数

最大公约数与最小公倍数的求法． （1） 短除法．（2）分解质因数法．设

a?p?121p?2p?kk,?i?0,i?1,2,,k，b?p?11p?22p?kk,?i?0,i?1,2,,k．

记 ????，则 ?a,b??p??i?mini,?i?,?i?max??i,?i11p22p???kk，?a,b??p?11p22pkk．（3）辗转相除法 ?a,b???b,r???r1,r2????rn?1,rn???rn,0??rn．

例7 （1）求?8381,1015?，?8381,1015?； （2）?144,180,108?，?144,180,108?．

解（1）方法1 分解质因数法．由

8381?172?29,1015?5?7?29,得

?8381,1015??29，?8381,1015??5?7?172?29?293335． 方法2 辗转相除法．

或 ?8381,1015???261,1015???261,232???29,232???29,0??29．

?8381,1015??8381?1015?8381,1015??8381?101529?8381?35?293335．

（2）方法1 短除法．由

2144 180 108272 90 54得

336 30 27312 10 9?144,180,108??22?32?36，

4 5 3

6

?144,180,108??24?33?5?2160．

方法2 分解质因数法．由

144?24?32, 180?2?3?5,，

22108?22?33,得 ?144,180,108??22?32?36，?144,180,108??24?33?5?2160．

例8 正整数n分别除以2,3,4,5,6,7,8,9,10得到的余数依次为1,2,3,4,5,6,7,8,9，则n的最小值为 ． 解 依题意，对最小的n，则n?1是2,3,4,5,6,7,8,9,10的公倍数n?1?2?3?5?7，得n?2519． 例9 有两个容器，一个容量为27升，一个容量为15升，如何利用它们从一桶油中倒出6升油来？ 解 相当于求不定方程15x?27y?6的整数解．由?15,27??3知，存在整数u,v，使

3215u?27v?3，可得一个解u?2,v??1，从而方程 15?4?27???2??6．

即往小容器里倒2次油，每次倒满之后就向大容器里倒，大容器倒满时，小容器里剩有3升油；再重复一次，可得6升．

例10 对每一个n?2，求证存在n个互不相同的正整数a1,a2,,an，使ai?ajai?aj，对任意的

i,j??1,2,,n?,i?j成立．

证明 用数学归纳法．当n?2时，取a1?1,a2?2，命题显然成立． 假设n?k时，命题成立，即存在a1,a2, 现取b为a1,a2,,ak，使 ai?ajai?aj，对任意的i,j??1,2,,k?,i?j成立．

,ak及它们每两个数之差的最小公倍数，则k?1个数

b,a1?b,a2?b,??at?b??b?at?b??b,?,ak?b满足 ?

a?b???aj?b??ai?b???aj?b?,???i 即命题对n?k?1时成立．由数学归纳法知命题对n?2成立．

例11 ?1959,IMO1?1?证明对任意正整数n，分数证明1 （反证法）假若

21n?4不可约．

14n?321n?4可约，则存在

14n?3d?1， ①

使 ?21n?4,14n?3??d，

?21n?4?dp, ②从而存在p,q,?p,q??1，使?

14n?3?dq, ③?消去n，?3??3??2??2，得 1?d?3q?2p?， ④

7

的 d?1． ⑤

由（1）、（5）矛盾，得d?1． 解题分析：（1）去掉反证法的假设与矛盾就是一个正面证法．

（2）式④是实质性的进展，表明 1?3?14n?3??2?21n?4?，

可见 ?21n?4,14n?3??1．由此获得2个解法． 证明2 设?21n?4,14n?3??d．存在p,q,?p,q??1，使

?21n?4?dp, ① ?14n?3?dq, ②?消去n，②×3-①×2，得

1?d?3q?2p? ③ 得 d?1．

证明3 由1?3?14n?3??2?21n?4? 得 ?21n?4,14n?3??1．

证明4 ?21n?4,14n?3? ??7n?1,14n?3? ④

??7n?1,1? ⑤ ?1． 解题分析：第④ 相当于 ①-②；第⑤ 相当于②-2（①-②）=②×3-①×2；所以③式与⑤式的效果是一样的．

例12 不存在这样的多项式 f?n??amn?am?1nmm?1??a1n?a0，

使得对任意的正整数n，f?n?都是素数．

证明 假设存在这样的多项式,对任意的正整数n，f?n?都是素数，则取正整数n?b，有素数p使 f?b??amb?am?1bmm?1??a1b?a0?p，

mm?1进而对任意的整数k,有 f?b?kp??am?b?kp??am?1?b?kp???a1?b?kp??a0

??ambm?am?1bm?1??a1b?a0??Mp（二项式定理展开）?P?1?M?，其中M为整数，这表明

f?b?kp?为合数．这一矛盾说明，不存在这样的多项式,对任意的正整数n，f?n?都是素数．

三、平方数

若a是整数，则a就叫做a的完全平方数，简称平方数． 1．平方数的简单性质

（1）平方数的个位数只有6个：0,1,4,5.6.9．

（2）平方数的末两位数只有22个：00，01，21，41，61，81，04，24，44，64，84，25，16，36，56，76，

8

296，09，29，49，69，89．

（3）?2n??0?mod4?,?2n?1??1?mod4?．（４）?2n?1??1?mod8?．

（6）凡是不能被3整除的数，平方后被3除余1．（7）在两个相邻整数的平方数之间，不能再有平方数． （8）非零平方数的约数有奇数个．

（9）直角三角形的三边均为整数时，我们把满足a?b?c的整数?a,b,c?叫做勾股数．勾股数的公式为

222222?a?m2?n2,? ?b?2mn,

?c?m2?n2,?其中m,n为正整数，?m,n??1且m,n一奇一偶．这个公式可给出全部素勾股数．

2．平方数的证明方法

（1）反证法．（2）恒等变形法．（3）分解法．设a为平方数，且a?bc，?b,c??1，则b,c均为平方数． （4）约数法．证明该数有奇数个约数． 3．非平方数的判别方法

（1）若n?x??n?1?，则x不是平方数．（2）约数有偶数个的数不是平方数．

22（3）个位数为2，3，7，8的数不是平方数．（4）同余法：满足下式的数n都不是平方数．

n?2?mod3?， n?2或3?mod4?， n?2或3?mod5?， n?2或3或5或6或7?mod8?，n?2或3或7或8?mod10?．

（5）末两位数不是：00，01，21，41，61，81，04，24，44，64，84，25，16，36，56，76，96，09，29，49，69，89．如

个位数与十位数都是都是奇数的数， 个位数是6、而十位数是偶数的数．

例13 有100盏电灯，排成一横行，从左到右，我们给电灯编上号码1，2，…，99，100．每盏灯由一个拉线开关控制着．最初，电灯全是关着的．另外有100个学生，第一个学生走过来，把凡是号码为1的倍数的电灯的开关拉了一下；接着第2个学生走过来，把凡是号码为2的倍数的电灯的开关拉了一下；第3个学生走过来，把凡是号码为3的倍数的电灯的开关拉了一下，如此等等，最后那个学生走过来，把编号能被100整除的电灯的开关拉了一下，这样过去之后，问哪些灯是亮的？

讲解 （1）直接统计100次拉线记录，会眼花缭乱．

（2）拉电灯的开关有什么规律：电灯编号包含的正约数（学生）才能拉、不是正约数（学生）不能拉，有几个正约数就被拉几次．

（3）灯被拉的次数与亮不亮（开、关）有什么关系：

0 关 1 开 2 关 3 开 4 关 5 开 6 关 7 开 8 关 9 开

灯被拉奇数次的亮！

（4）哪些数有奇数个约数：平方数． （5）1～100中有哪些平方数：共10个：

1，4，9，16，25，36，49，64，81，100．

答案：编号为1，4，9，16，25，36，49，64，81，100共10个灯还亮．

9

例14 已知直角三角形的两条直角边分别为正整数a,b，斜边为正整数c，若a为素数，求证2?a?b?1?为平方数．证明 由勾股定理c2?a2?b2，有 ?c?b??c?b??a2，

但a为素数，必有 ??c?b?a2,c?b?1,解得 b?1?a2?1?，

?2从而 2?a?b?1??2a??a2?1??2??a?1?2，为平方数．

例15 求证，任意3个连续正整数的积不是平方数．

证明 设存在3个连续正整数n?1,n,n?1（n?1）的积为平方数，即存在整数m，使 ?n?1?n?n?1??m2，即 ?n2?1?n?m2，

?n2?1?a2但?n2?1,n??1，故n2?1,n均为平方数，有?,?n?b2,

??

m?ab,得 1?n2?a2?n2??n?1?2?2n?1?1，（注意n?1）

这一矛盾说明，3个连续正整数的积不是平方数．

四．整除

整除的判别方法主要有7大类．

1．定义法．证ba?a?bq，有三种方式．

（1）假设a?qb?r，然后证明r?0．（定理4）（2）具体找出q，满足a?bq．（3）论证q的存在． 例18 任意一个正整数m与它的十进制表示中的所有数码之差能被9整除．

证明 设m?ann?1n?10?an?1?10??a1?10?a0，其中0?ai?9,an?0，则

m??an?an?1??a1?a0? ?an?1n?10n?1??an?1?10?1???a1?10?1?

?9???an?111??an?1?111??a?2?11?a1?n个1n?1个1?,按定义 9m??an?an?1??a1?a0?．

2．数的整除判别法．

（1）任何整数都能被1整除．（2）如果一个整数的末位能被2或５整除，那么这个数就能被2或５整除． （3）如果一个整数的末两位能被４或25整除，那么这个数就能被4或25整除． （4）如果一个整数的末三位能被8或125整除，那么这个数就能被8或125整除． （5）如果一个整数各数位上的数字之和能被3或9整除，那么这个数就能被3或9整除．

证明 由10?1?mod3?,10?1?mod9?，有

an?1n?10?an?1?10n??a1?10?a0?an?an?1??a1?a0?mod3?，

10

an?10n?an?1?10n?1??a1?10?a0?an?an?1??a1?a0?mod9? （6）如果一个整数的末三位数与末三位数以前的数字所组成的数的差能被7或11或13整除，那么这个数就能被7或11或13整除． 证明 由m?anan?1a2a1a0 ?anan?1a3?1001??anan?1a3?a2a1a0?， 知 1001anan?1a3a2a1a0?1001?anan?1a3??a2a1a0?， 又由1001?7?11?13，而7,11,13均为素数知，m能被7或11或13整除． （7）如果一个整数的奇位数字之和与偶位数字之和的差能被11整除，则这个数能被11整除． 证明 由10??1?mod11?，有an?10n?an?1?10n?1??a1?10?a0?an1n??1??an?1??1?n???a1??1??a0?mod11?. 3．分解法．主要用乘法公式．如

an?bn??a?b??an?1?an?2b?an?3b2??abn?2?bn?1?．

a2n?1?b2n?1??a?b??a2n?2?a2n?3b?a2n?4b2??ab2n?3?b2n?2?．

a2n?b2n??a?b??a2n?1?a2n?2b?a2n?3b2??ab2n?2?b2n?1?．

例19 试证?1?2??9??15?25??95?．

证明 改证45?15?25??95?．设S?15?25??95，则

S??15?85???25?75???35?65???45?55??95 ??1?8?m1??2?7?m2??3?6?m53??4?5?m4?9

?9?m41?m2?m3?m4?9?,得9S．又 S??15?95???25?85???35?75???45?65??55

??1?9?m1??2?8?m2??3?7?m3??4?6?m54?5?5?2m4得5S．

1?2m2?2m3?2m4?5?,但?9,5??1，得45S，即?1?2??9??15?25??95?．

例20 ?1979,IMO21?1?设p与q为正整数，满足

p1q?1?112?3??1318?11319，求证p可被1979整除（1979p） 证明

pq?1?112?3??111318?13 19 ???1?111??2?13??1318?1?1319??11??2??2?4??1318??

11

?11??1????23?11??11????1???13181319??23?1?? 659??1111 ????66066113181319660?1319661?1318989?990 ????660?1319661?1318989?990M660?661?659!M?1979?1319!?1979??1319

得1979整除1319!p，但1979为素数，?1979,1319!??1，得p可被1979整除．

例20-1 2009年9月9日的年、月、日组成“长长久久、永不分离”的吉祥数字20090909，而它也恰好是一个不能再分解的素数．若规定含素因子20090909的数为吉祥数，请证明最简分数子m是吉祥数．

证明：由

m1?1??n2?1的分

20090908m1?1??n2?1

200909081111?1??1?????????????????120090908??220090907??1004545410045455?200909092009090920090909 ????1?200909082?2009090710045454?10045455p?20090909?,1?2??20090907?20090908其中p为正整数，有 20090909?n?p?1?2??20090907?20090908?m，

这表明，20090909整除1?2??200909?072009m?0，9但20090909为素数，不能整除

，所以1?2??200909?07200920090909整除m，得m是吉祥数．

4． 余数分类法．

例21 试证3n?n?1??2n?1?．

证明1 任何整数n被3除其余数分为3类 n?3k,n?3k?1,n?3k?2,k?Z，

（1）n?3k时，有 n?n?1??2n?1??3??k?3k?1??6k?1???,

有3n?n?1??2n?1?．（2）n?3k?1时，有n?n?1??2n?1??3???3k?1??3k?2??2k?1???, 有3n?n?1??2n?1?．（3）n?3k?2n?n?1??2n?1??3???3k?2??k?1??6k?5???, 有3n?n?1??2n?1?．综上得，3n?n?1??2n?1?．

2n?2n?2??2n?1?证明2 n?n?1??2n?1??，得 32n?2n?2??2n?1?，又?3,4??1，得

4

12

3n?n?1??2n?1?．

5．数学归纳法．6．反证法．7．构造法． 例22 k个连续整数中必有一个能被k整除． 证明 设k个连续整数为a,a?1,a?2,,a?k?1，

,k?1，共k?1种情况，必存在两个数

若这k个数被k除没有一个余数为0，则这k个数的余数只能取1,2, a?i,a?j,0?i?j?k ，使 a?i?kq1?r,a?j?kq2?r, 其中q1?q2，相减 i?j?k?q1?q2?，有 i?j?kq1?q2?k， 即 i?j?k与i?j?k矛盾．故k个连续整数中必有一个能被k整除．

也可以由i?j?k?q1?q2?得 0?i?j?k?q1?q2??k，推出0?q1?q2?1，与q1?q2为整数矛盾．

例23 k个连续整数之积必能被k!整除． 证明 设k个连续整数为n,n?1,n?2,（1）若这k个连续整数为正整数，则

,n?k?1，

n?n?1??n?2?k!?n?k?1??n!k!?n?k?!??C?

kn只须证明，对任何一个素数p，分子中所含p的方次不低于分母中所含p的方次，由高斯函数的性质

?x?y???x???y?，有

kn?k??n?k???n??k??n?k??????ps???ps???ps???ps? ????????得

C为整数（证实了组合数的实际意义）

（2）若这k个连续整数中有0，则连乘积为0，必能被k!整除．

（3）若这k个连续整数为负整数，则

n?n?1??n?2??n?k?1?k!k??n???n?1???n?2? ???1?k!???1?kk??n?k?1?

Ck?n,n?n?1??n?2?由（1）知C?n为整数，故

k!?n?k?1?为整数．

例24 有男孩、女孩共n个围坐在一个圆周上（n?3），若顺序相邻的3人中恰有一个男孩的有a组，顺序相邻的3人中恰有一个女孩的有b组，求证3a?b．

证明 现将小孩记作ai(i?1,2,…,n)，且数字化

13

?1,　ai表示男孩时 ai????1, ai表示女孩时则“3人组”数值化为

Ai?ai?ai?1?ai?2?3,　　 ai,ai?1,ai?2均为男孩???3,　　ai,ai?1,ai?2均为女孩 ???1,　　 ai,ai?1,ai?2恰有一个女孩??1,　　a,a,a恰有一个男孩ii?1i?2?其中an?j?aj．又设取值为3的Ai有p个，取值为?3的Ai有q个，依题意，取值为1的Ai有b个，取值为?1的

a1?a2?…?an)?a(1?a??)a(?2a?a?4…)?an?(a?a1 )Ai有a个，得 3(2a33 ?3p?(?3)q?(?1)a?b?3(p?q)?(b?a)， 可见3a?b．

例25 （1956，中国北京）证明n?3321n?n?1对任何正整数n都是整数，并且用3除时余2． 22n?3n?1?321分析 只需说明n?n?为整数，但不便说明“用3除时余2”，应说明

222n?n?1??2n?1?2n?2n?2??2n?1?313213n3?n2?n??1,?3,8??1 ， 是3的倍数．作变形 n?n?n?1?222228命题可证．

n?n?1??2n?1?321?1， ① 证明 已知即n?n?n?1?2223因为相邻2个整数n,?n?1?必有偶数，所以n?3321n?n?1为整数．又①可变为 222n?2n?2??2n?1?31n3?n2?n?1??1，

228因为相邻3个整数2n,?2n?2?,?2n?1?必有3的倍数，故2n?2n?2??2n?1?能被3整除；又?3,8??1，所

以

2n?2n?2??2n?1?3213能被3整除；得n?n?n?1用3除时余2．

822五、同余

根据定义，同余问题可以转化为整除问题来解决；同时，同余本身有很多性质，可以直接用来解题．

例26 正方体的顶点标上?1或?1，面上标上一个数，它等于这个面四个顶点处的数的乘积，求证，这样得出的14个数之和不能为0．

证明 记14个数的和为S，易知，这14个数不是?1就是?1，若八个顶点都标上?1，则S?14，命题成立．

对于顶点有?1的情况，我们改变?1为?1，则和S中有4的数a,b,c,d改变了符号，用S表示改变后的和，由

14

/ a?b?c?d?0?mod2?知 S?S/?2a?b?c?d?0?mod4?， 这表明，改变一个?1，和S关于模4的余数不变，重复进行，直到把所有的?1都改变为?1，则

S?S/?1?1??1?14?2?mod4?，所以，S?0．

nn?1例27 设多项式f?x??a0x?a1x???an?1x?an的系数都是整数，并且有一个奇数?及一个偶数?使

得f???及f???都是奇数，求证方程f?x??0没有整数根．

证明 由已知有f????1?mod2??a0?a1?a2??an?1?mod2?， ①

f????1?mod2??an?1?mod2?， ②

若方程f?x??0存在整数根x0，即f?x0??0．当x0为奇数时，有

f?x0??0?mod2??a0?a1?a2??an?0?mod2?，

与①矛盾．有x0为偶数时，有f?x0??0?mod2??an?0?mod2?，与②矛盾．所以方程f?x??0没有整数根． 六、不定方程

未知数的个数多于方程个数的整系数代数方程，称为不定方程．求不定方程的整数解，叫做解不定方程． 解不定方程通常要解决3个问题，方程是否有解？有解时，有几个解，解数是有限还是无穷？求出全部解．

例28 解方程7x?19y?213． 解法1 由?7,19??1知方程有整数解． 观察特解，列表

y x 1 2 3 … ?x0?25,得一个特解?从而通解为

y?2,?019725 7t,?x?25?19 ?y?2?7t.?方法总结：第1步，验证?a,b?c，经常是?a,b??1．第2步，求特解（观察、列举、辗转相除等）． 第3步，代入公式．

方法总结：ax?by?c?ax?c?modb?或by?c?moda?． 例29 求方程x?2xy?2009的整数解． 解 由2009的分解式，有 x232?x?2y??12?2009?72?41，

?x2?1,?x?1,?x??1,??有 ? ?y?1004,y?1005,??x?2y?2009,??x2?72,?x?7,?x??7,? ????x?2y?41,?y?17,?y?24.

15

例30 甲乙两队各出7名队员按事先排好的顺序出场参加围棋擂台赛，双方先由1号队员比赛，负者被淘汰，胜者再与负方2号队员比赛，…直到有一方队员全被淘汰为止，另一方获得胜利，形成一种比赛过程，那么所有可能出现的比赛过程的种数为 ．（1988，高中联赛）

解法1 设甲、乙两队的队员按出场顺序分别为A1,A2,A3,A4,A5,A6,A7和B1,B2,B3,B4,B5,B6,B7．如果甲方获胜，设Ai获胜的场数是xi，则0?xi?7,1?i?7而且

x1?x2??x7?7 ， ①

容易证明以下两点：在甲方获胜时

（i）不同的比赛过程对应着方程①的不同非负整数解；

（ii）方程①的不同非负整数解对应着不同的比赛过程，例如，解（2，0，0，1，3，1，0）对应的比赛过程为：

A1胜B1和B2；B3胜A1、和A3；A4胜B3后负于B4；A5胜B4、B5和B6但负于B7；最后A6胜B7结束比赛．下

面求方程①的非负整数解个数，设yi?xi?1，问题等价于方程

y1?y2?y3?y4?y5?y6?y7?14，

正整数解的个数，将上式写成

1?1?1?1?1?1?1?1?1?1?1?1?1?1?14，

从13个加号取6个的方法数C13种．得甲方获胜的不同的比赛过程有C13种．

6同理，乙方获胜的不同的比赛过程也有C13种，合计2C13?3432种比赛过程

766例31（1989，高中）如果从数1，2，…，14中按由小到大的顺序取出a1,a2,a3，使同时满足 a2?a1?3, a3?a2?3，那么，所有符合上述要求的不同取法有多少种？

a1?1?0, 解 由已知得

a2?a1?3?0 a3?a2?3?0, 14?a3?0,4项均为非负数，相加得?a1?1???a2?a1?3???a3?a2?3??? 14?a3??7，

于是a1,a2,a3的取法数就是不定方程 x1?x2?x3?x4?7

的非负整数解的个数，作一一对应y1?xi?1，问题又等价于不定方 y1?y2?y3?y4?11 的正整数解．由 1?1?七．数论函数

主要是?x?高斯函数，??n?欧拉函数．

例32 某学校要召开学生代表大会，规定各班每10人推选一名代表，当各班人数除以10的余数大于时再增．．6．选一名代表．那么，各班可推选代表人数y与该班人数x之间的函数关系用取整函数y??x?（?x?表示不大于x的最大整数）可以表示为

33个解，即符合要求的不同取法有C10种． ?1?11，得C10 16

(A)y??? (B)y?? (C) y?? (D)y?? ???10101010????????（2010年全国高考数学陕西卷理科第10题）

解法1 选（B）．（求解对照）．规则是“六舍七入”，故加3即可进1． 选y???x??x?3??x?4??x?5??x?3?． ??10?解法2 选（B）．（特值否定）．取x?56，按规定应选5人，可否定(C)、(D)；再取x?57，按规定应选6

人，可否定(A)．

注：主要错误选(C) ，误为“五舍六入”．

例33 用?x?表示不大于x的最大整数，求

??1??2???366???366?????? ?366????2004??????366???．

???讲解 题目的内层有2004个高斯记号，外层1个高斯记号．关键是弄清?x?的含义，进而弄清加法谁与谁加、除法谁与谁除：

（1）分子是那些数相加，求出和来；

由366?5?1830?2004?2196?366?6，知分子是0～5的整数相加，弄清加数各有几个 1～365 366～731 732～1097 1098～1463 1464～1829 1830～2004 0 1 2 3 4 5 365个 366个 366个 366个 366个 175个 （2）除法谁除以366，求出商的整数部分．

?0?365?366?1?2?3?4??5?175?原式???

366???10?366?875????366??143????10?2? ?366???12. 命题背景2004年有12个月、366天．

例34 50!的标准分解式中2的指数．

解 50!?21325374115136177198239293137414347 2的指数为

17

??????????50??50??50??50??50???2???3???4???5??25?12?6?3?1?47． ??2???2??2??2??2? 图示（5条横线，25个偶数中2的方次，按横线求和）

八、综合练习

例35 整数勾股形中，证明

（1）必有一条直角边长是3的倍数；（2）必有一条直角边长是4的倍数； （3）必有一条边长是5的倍数；（4）三角形的面积是6的倍数．

证明 当整数勾股形的三边有公约数时，可以先约去，使三边长x,y,z互素，且满足

x2?y2?z2.

这时，若x,y两个均为偶数，则z也为偶数，与x,y,z互素矛盾；若x,y两个均为奇数，有

x2?1?mod4?,y2?1?mod4?，得 z2?x2?y2?2?mod4?， 这与平方数模4只能取0，1矛盾.所以，x,y中有且只有一个为偶数，不妨设x为偶数.

（1）设x,y中无一为3的倍数，则

x?1?mod3?,y?1?mod3?，得 z?x?y?2?mod3?，

22222这与平方数模3只能取0，1矛盾，故x,y中有一个为3的倍数. （2）由x为偶数.，必有y,z均为奇数，记

x?2m,y?2p?1,z?2q?1有 4m2?x2?z2?y2??2q?1???2p?1??4?q2?q?p2?p?

22则 m?q?q?1??p?p?1?右边是两个偶数的差，必为偶数，从而x为4的倍数.

2（3）若x,y中有5的倍数，命题已成立. 若x,y均不是5的倍数，则若x,y只能是形如5k?1或5k?2的正整数.若x,y均为5k?1型，则z?x?y?1?1?2?mod5?

222这与平方数模5只能取0，1，4矛盾若x,y均为5k?2型，则z?x?y?4?4?3?mod5?

222这与平方数模5只能取0，1，4矛盾.所以，x,y只能分别取5k?1与5k?2型，有 z?x?y?4?1?0?mod5?得5z，但5是素数，得5z.

2222（4）由上证（1）、（2）及?3,4??1知，xy是12的倍数，则

1xy是6的倍数，得三角形的面积是6的倍数． 2例36 已知ABC内有n个点，连同A,B,C共有n?3个点，以这些点为顶点，把ABC分割为若干个互不重叠的小三角形，现把A,B,C分别染上红色、蓝色、黄色，而其余n个点，每点任意染上红、蓝、黄三色之一，证明三顶点都不同色的小三角形的总数必是奇数．（斯潘纳定理）

证明1 给这些小三角形的边赋值：当边的两端点同色时，记为0；当边的两端点异色时，记为1；

再用三边之和给小三角形赋值：当三角形的三顶点同色时，和值为0，记这样的小三角形有a个；当三角形的三顶点中仅有两点同色时，和值为2，记这样的小三角形有b个；当三角形的三顶点两两异色时，和值为3，记这样的小三角形有c个.下面用两种方法计算所有三角形赋值的总和S，一方面

S?0?a?2?b?3?c?2b?3c. ①

另方面，AB,BC,CA的赋值均为1，和为奇数；而ABC内的每一条连线，在上述S的计算中都被计算了两

18

次，和为偶数；这两者之和得S为奇数，记为

S?2k?1 ② 由①，②得 2k?1?2可见c为奇数，即三顶点都不同色的小三角形的总数必是奇数．（ b?3c

证明：n个连续整数的乘积一定能被n!整除

设a为任一整数，则式： (a+1)(a+2)...(a+n) =(a+n)!/a! =n!*[(a+n)!/(a!n!)]

而式中[(a+n)!/(a!n!)]恰为C(a+n,a),也即是从a+n中取出a的组合数，当然为整数。 所以(a+1)(a+2)...(a+n)一定能被n!整除

同余式与不定方程

例：求使2+1能被3整除的一切自然数n. 解∵

∴

n

n

则2+1

n

n

∴当n为奇数时，2+1能被3整除；当n为偶数时，2+1不能被3整除. 例2 求2最后两位数码. 解 考虑用100除2所得的余数.∵∴∴

∴

∴2的最后两位数字为88.

例3 求证3证明 ∵∴

2．不定方程

不定方程的问题主要有两大类：判断不定方程有无整数解或解的个数；如果不定方程有整数解，采取正确的方法，求出全部整数解. (1) 不定方程解的判定

∴

1980

999999

999

又

+4

1981

能被5整除.

∴

19

如果方程的两端对同一个模m(常数)不同余,显然,这个方程必无整数解.而方程如有解则解必为奇数、偶数两种，因而可以在奇偶性分析的基础上应用同余概念判定方程有无整数解. 例4 证明方程2x-5y=7无整数解.

2

2

证明 ∵2x=5y+7，显然y为奇数.① 若x为偶数，则

22

∴

∵方程两边对同一整数8的余数不等，∴x不能为偶数.

② 若x为奇数，则但5y+7

2

∴x不能为奇数.因则原方程无整数解.

说明:用整数的整除性来判定方程有无整数解,是我们解答这类问题的常用方法. 例5 不存在整数x,y使方程

①证明 如果有整数x，y使方程①成立，

则=知（2x+3y）+5能被17整除.

2

设2x+3y=17n+a，其中a是0，±1，±2，±3，±4，±5，±6，±7，±8中的某个数，但是这时（2x+3y）

2

+5=（17n）+34na+（a+5）=a+5（mod17），而a+5被17整除得的余数分别是5，6，9，14，4，13，7，

2

2222

3，1，即在任何情况下（2x+3y）+5都不能被17整除，这与它能被17整除矛盾.故不存在整数x，y使①成立.

例7 满足方程x+y=x的正整数对（x，y）的个数是（ ）. （A）0 （B）1（C）2（D）无限个（E）上述结论都不对

解由x+y=x得y=x（x-1），所以只要x-1为自然数的平方，则方程必有正整数解.令x-1=k(k为自然

2

2

3

2

2

2

2

2

3

数),则为方程的一组通解.由于自然数有无限多个,故满足方程的正整数对(x,y)有无限多

个,应选(D).说明:可用写出方程的一组通解的方法,判定方程有无数个解.

20

(2) 不定方程的解法

不定方程没有统一的解法,常用的特殊方法有:配方法、因式（质因数）分解法、不等式法、奇偶分析法和余数分析法.对方程进行适当的变形,并正确应用整数的性质是解不定方程的基本思路.

例6 求方程

解(配方法)原方程配方得(x-2y)+y=13.

2

2

2

的整数解.

在勾股数中,最大的一个为13的只有一组即5,12,13,因此有8对整数的平方和等于13即

(5,12),(12,5),(-5,-12),(-12,-5),(5-,12),(12,-5),(-5,12),(-12,5).故原方程组的解只能是下面的八个方程组的解

2

解得

2

2

2

例7 已知两个自然数b和c及素数a满足方程a+b=c.证明:这时有a＜b及b+1=c. 证明（因式分解法）∵a+b=c，∴a=（c-b）（c+b），又∵a为素数，∴c-b=1，且c+b=a.

2

2

2

2

2

于是得c=b+1及a=b+c=2b+1＜3b，即

2

＜.而a≥3,∴≤1，∴＜1.∴a＜b.

21

例9满足联立方程

的正整数（a，b，c）的组数是（ ）.

解（质因数分解法）由方程ac+bc=23得（a+b）c=23=1×23.

∵a，b，c为正整数，∴c=1且a+b=23.将c和a=23-b代入方程ab+bc=44得(23-b)b+b=44,即(b-2)(b-22)=0, ∴b1=2,b2=22.从而得a1=21,a2=1.故满足联立方程的正整数组(a,b,c)有两个,即(21,2,1)和(1,22,1) 例10求不定方程2(x+y)=xy+7的整数解.

解 由(y-2)x=2y-7,得

分离整数部分得

由x为整数知y-2是3的因数, ∴y-2=±1，±3，∴x=3，5，±1. ∴方程整数解为

例11 求方程x+y=x-xy+y的整数解.

解（不等式法）方程有整数解 必须△=（y+1）-4（y-y）≥0，解得

2

2

2

2

≤y≤.

满足这个不等式的整数只有y=0，1，2.

当y=0时，由原方程可得x=0或x=1；当y=1时，由原方程可得x=2或0；当y=2时，由原方程可得x=1或2.

22

所以方程有整数解

最后我们来看两个分式和根式不定方程的例子.

例12 求满足方程且使y是最大的正整数解（x，y）.

解将原方程变形得

由此式可知，只有12-x是正的且最小时，y才能取大值.又12-x应是144的约数，所以， 12-x=1，x=11，这时y=132. 故 满足题设的方程的正整数解为 （x，y）=（11，132）.

例13（第35届美国中学生数学竞赛题）满足0＜x＜y及数是（ ）.

（A）0 （B）1 （C）3 （D）4 （E）7 解法1 根据题意知，0＜x＜1984，由

的不同的整数对（x，y）的个

得

6

2

当且仅当1984x是完全平方数时，y是整数.而1984=2·31，故当且仅当x具有31t形式时，1984x是完全平方数.

∵x＜1984，∵1≤t≤7.当t=1，2，3时，得整数对分别为（31，1519）、（124，1116）和（279，775）.当t＞3时y≤x不合题意，因此不同的整数对的个数是3，故应选（C）.

23

解法2 ∵1984=∴由此可知：x必须具有31t形式，y必须具有31k形式，并且

22

t+k=8（t，k均为正整数）.因为0＜x＜y，所以t＜k.当t=1，k=7时得（31，1519）；t=2，k=6时得（124，1116）；当t=3，k=5时得（279，775）.因此不同整数对的个数为3. (1)方程x-y=105的正整数解有( ).

（A） 一组 （B）二组 （C）三组 （D）四组

(2)在0,1,2,…，50这51个整数中，能同时被2，3，4整除的有（ ）. （A） 3个 （B）4个 （C）5个 （D）6个 2．填空题

（1）的个位数分别为_________及_________.

2

2

(2)满足不等式10≤A≤10的整数A的个数是x×10+1，则x的值________.

3

454

(3) 已知整数y被7除余数为5,那么y被7除时余数为________. (4) 求出任何一组满足方程x-51y=1的自然数解x和y_________. 3.求三个正整数x、y、z满足

2

2

.

4．（1985年上海数学竞赛题）在数列4，8，17，77，97，106，125，238中相邻若干个数之和是3的倍数，而不是9的倍数的数组共有多少组？

5．求的整数解.

6．求证可被37整除.

7．（全俄1986年数学竞赛题）求满足条件

的整数x，y的所有可能的值.

24

8．（1985年上海初中数学竞赛题）已知直角三角形的两直角边长分别为l厘米、m厘米，斜边长为n厘米，且l，m，n均为正整数，l为质数.证明：2（l+m+n）是完全平方数.9.(1988年全国初中数学竞赛题)

如果p、q、 练习二十

、都是整数，并且p＞1，q＞1，试求p+q的值.

1.D.C.2.(1)9及1. (2)9. (3)4.

(4)原方程可变形为x=(7y+1)+2y(y-7),令y=7可得x=50.

2

2

3.不妨设x≤y≤z,则,故x≤3.又有故x≥2.若x=2,则,故y≤6.又有,

故y≥4.若y=4,则z=20.若y=5,则z=10.若y=6,则z无整数解.若x=3,类似可以确定3≤y≤4,y=3或4,z都不能是整数.

4.可仿例2解.5.先求出方数,…,解得

,然后将方程变形为y=5+x-2要使y为整数,5x-1应是完全平

6.8888≡8(mod37),∴8888

7777≡7(mod37),7777

3333

2222

≡8(mod37).

3333

2

≡7(mod37),8888

2

2

32222

+7777≡(8+7)(mod37),而8+7=407,37|407,∴37|N.

2323

7.简解:原方程变形为3x-(3y+7)x+3y-7y=0由关于x的二次方程有解的条件△≥0及y为整数可得0≤y≤5,即y=0,1,2,3,4,5.逐一代入原方程可知,原方程仅有两组解(4,5)、(5,4). 8.∵l+m=n,∴l=(n+m)(n-m).∵l为质数,且n+m＞n-m＞0,∴n+m=l,n-m=1.于是

l=n+m=(m+1)+m=2m+1,2m=l-1,2(l+m+1)=2l+2+2m=l+2l+1=(l+1).即2(l+m+1)是完全平方数.

2

2

2

2

2

2

2

2

2

9.易知p≠q,不妨设p＞q.令p、q之值.

=n,则m＞n由此可得不定方程(4-mn)p=m+2,解此方程可得

25

赛题精讲

例1：数1978n与1978m的最末三位数相等，试求正整数m和n，使得n+m取最小值，这里n?m?1. （第20届IMO试题）

【解】由已知1978nn?1078m(mod1000),而1000=8×125，所以

m8) ① 1978?1078(mod1978n?1078m(mod125) ②

因n?m?1，且（1978m，125）=1，则由②式知1978nm≡1（mod125）③

又直接验证知，1978的各次方幂的个位数字是以8、4、2、6循环出现的，所以只有n－m为4的倍数时，③式才能成立，因而可令n－m=4k.由于. n+m=（ n－m）+2m=4k+2m，因而只需确定出k和m的最小值.

先确定k的最小值：因为19784=（79×25+3）4≡34≡1（mod5），19784≡34≡1（mod25）.故可令19784=5t+1，

－

而5 t，从而0≡1978n

－m－1=19784k－1=（5k+1）k－1≡

k(k?1)?(5t)2 2+k?5t(mod125)，显然，使上式成立的k的最小值为25.

再确定m的最小值：因1978≡2（mod8），则由①式知，2?2(mod8) ④ 由于n?m?1,④式显然对m=1，2不成立，从而m的最小值为3.

故合于题设条件的n+m的最小值为106.

【评述】比例中我们用了这样一个结论：1978的各次方幂的个位数字是以8，4，2，6循环出现，即，当r=1，2，3，4时，1978义：

整数列?xn?各项除以m（m≥2，m∈N*）后的余数an组成数列?an?.若?an?是一个周期数列，则称?xn?是关于模m的周期数列，简称模m周期数列.满足an?T?an（或an?T?xn （modm））的最小正整数T称为它的周期.

例如，（1）1978pnm?19784q?r?8,4,2,6(mod10).这种现象在数学上称为“模同期现象”.一般地，我们有如下定

?n?是模10周期数列，周期为4；（2）自然数列{n}是一个模m（m≥2，m∈N*）周期数列，

周期为m；（3）任何一个整数等差数列都是一个模m（m≥2，m∈N*）周期数列，周期为m.

例2：设a是方程x3?3x2?1?0的最大正根，求证：17可以整除[a1788]与[a1988].其中[x]表示不超过x的最大整数. （第29届IMO预选题）

【证明】根据如下符号表可知，若设三根依次为????a，则?1????

x f(x)符号

－1 － －11,???1, 221 21 2+ 1 － 23 － 3 + + 22?a,由于f(??)??2?3?(?3?2?2?1)??2?3?0,于是????,|?|??.

26

另一方面，由韦达定理知，

22?6a2?a3?2a3?a3????(???)?2???(3?a)??9??9??1?(8?a2)

aaa2222?a2?(22)2?8,??2??2?1.

为了估计[a1788]、[a1988]，先一般考察[an]，为此定义：

un??n??n?an.(n?0,1,2,?)

直接计算可知：u0?3,u1?2???a?3.u2??2??2?a2?9,以及un?3?3un?2?n(n?0). 又

因

0??n??n?1(?|?|??,即?n??n?0,又????3???2?22?1,当

n?2时，

?n??n?|?|n??n??2??2?1),则an?un?(?n??n)?un?1?[1?(?n??n) ]?[an]?un?1.(n?1,2,?)

由此知，命题变为证明：u1788?1和u1988?1能被17整除. 现考察?un?在模17的意义下的情况：

u0?3,u1?3,u2?9,u3?7,u4?1,u5?11,u6?9,u7?9,u8?16,u9?5,u10?6,u11?2,

u12?1,u13?14,u14?6,u15?0,u16?3,u17?3,u18?9,??

可见，在模17意义下，?un?是16为周期的模周期数列，即un?16?un(mod17).由于 1788?12(mod16),1988?4(mod16),故u1788?u12?1(mod17),u1988?u4?1(mod17),故

u1788?1?0,u1988?1?0(mod17).命题得证.

例3：求八个整数n1,n2,?,n8满足：对每个整数k（－1985

【解】令数集G?k|k?a1?a2?3?a3?32???an?1?3n,ai?{?1,0,1},i?1,2,?,n?1.

??3n?1?1记 2nG?1?3?3???3?显然 max H，mixG?1?3?3???3??H.

22n且G中的元素个数有3n?1?2H?1个.又因G中任意两数之差的绝对值不超过2H，所以G中的数对模2H+1不同

余.因此，G的元素恰好是模2H+1的一个绝对值最小的完系，于是，凡满足?H?k?H的任意整数都属于G，且可惟一地表示为：a1?a2?3?a3?32???an?1?3n形式.

当n=7时，H=3280>1985，而n=6时，H=1043<1985.故n1=1，n2=3，…，n8=37为所求.

例4：设n为正整数，整数k与n互质，且0

27

色中的一种，染法如下：（i）对M中每个i，i与n－i同色；（ii）对M中每个i，i≠k,i与|k－i|同色.求证：M中所有的数必为同色. （第26届IMO试题）

【证明】因(k,n)?1,又0，1，…n－1是模n的一个完全剩余系，所以0，k，2k，…，（n－1）k也是模n的一个完全剩余系.若设jk?rj(modn)(其中1?rj?n?1,j?1,2,?,n?1),

则M={r1,r2,?,rn?1}.下只需证rj?1与rj(1?j?n?2).因为，若如此，当r1的颜色确定后，M中所有都与r1同色.

由于(j?1)k?rj?1(modn),则rj?k?rj?1(modn)，因此，

（1）若rj?k?n,则rj?1?rj?k，于是，由条件（i）知，k?rj?1?n?rj与n?(n?rj)?rj同色.又由条件（ii）知，k?rj?1与|k?rj?1?k|?rj?1同色，故rj?1与rj同色.综上所述可知，rj?1与rj同色.命题得证.

例5：设a和m都是正整数，a>1.证明：m|?(a?1).

m【证明】实上，显然a与a?1互素，且a模a?1的阶是m，所以由模阶的性质③导出m|?(a?1).

mmm例6：设p是奇素数，证明：2p－1的任一素因了具有形式2px?1,x是正整数.

【证明】设q是2p－1的任一素因子，则q≠2.设2模q的阶是k，则由2?1(modq)知k|p，故k=1或p（因p是素数，这是能确定阶k的主要因素）.显然k≠1，否则2?1(modq),这不可能，因此k=p.

现在由费马小定理2证毕.

例7：设m,a,b都是正整数，m>1，则m?1,m?1)?mabab(a,b)q?1p1?1(modq)推出k|q?1,即p|q?1.因p、q都是奇数，故q－1=2px（x是个正整数），

?1.

(a,b)【证明】记d?(m?1,m?1).由于（a,b）|a及（a,b）|b，易知m?1|ma?1及

m(a,b)?1|mb?1，故m(a,b)?1|d，另一方面设m模d的阶是k，则由

ma?1(modd),mb?1(modd)推出，k|a及k|b，故k|（a，b）.因此m(a,b)?1(modd),即d|m(a,b)?1.

综合两方面可知，d?m(a,b)?1.证毕.

例8：设n，k是给定的整数，n>0，且k（n－1）是偶数.证明：存在x,y,使得(x,n)?(y,n)?1,是x?y?k(modn). 【证明】我们先证明，当n为素数幂p时结论成立.实际上，我们能证明，存在x,y，使

p xy，且x?y?k.如p=2，则条件表明k为偶数，可取x?1,y?k?1;如p?2,则x?1,y?k?1或x?1,y?k?2中有一对满足要求.一般情形下，设n?p11?prr是n的标准分解，上面已证明，对每个pi，均有整数xi，yi，使pi xiyi，且xi?yi?k(1,2,?,r).现在孙子定理表明，同余方程组

28

????1x?x1(modp1),?,x?xr(modprar)有解x，同样 ?1y?y1(modp1),?,y?yr(modprar)

也有解y.现在易证x,y符合问题中的要求：因pi xiyi，故pi xy（i=1，…，r），于是（xy，n）=1.又

x?y?xi?yi?k(modpi?1)(i?1,?,r),故x?y?k(modn).

例9：设n为任意的正整数.证明：一定存在n个连续的正整数解，使其中任何一个都不是质数的整数幂. （第30届IMO试题）

【证明】取2n个两两不同的质数p1,p2,?,pn和q1,q2,?,qn.同余方程组x??i(modpiqi),

i?1,2,?,n.由于p1q1,p2q2,?,pnqn两两互质，根据孙子定理必有解，取为正整数N，则n个连续正整数N+1，

N+2，…，N+n都至少含有两个不同的质因数，因而它们中的任一个都不是质数的整数幂.证毕.

.

、

数论素有“数学皇后”的美称。由于其形式简单，意义明确，所用知识不多而又富于技巧性，千姿百态，灵活多样。有人曾说：“用以发现数学天才，在初等数学中再也没有比数论更好的课程了。”因此在理念的国内外数学竞赛中，几乎都离不开数论问题，使之成为竞赛数学的一大重要内容。 例1 证明无穷数列10001，100010001，……中没有素数。 证明：设an?1000100011，则an?1?10?10?n个148?104(n?1)104n?1=4 10?1108k?1(108)k?1108?1?当n为偶数，设n?2k，an=4

10?1108?1104?1所以an为合数。当n为奇数，设n?2k+1，

（2k+1）2k?12k?1104?1（102）?1（102）?1an==所以an为合数。

104?1102?1102?1评析：对n分奇偶，分情况讨论，问题变得清晰易证。同时注意，若n为奇数时，xn?yn可分解因式。 例2 证明对任意整数n?1，n4?4n不是素数。

证明：当n为偶数时，n4?4n为偶数，所以n4?4n为合数； 当n为奇数，设n?2k?1，则n4?4n=n4?42k?1?n4?4(2k)4

=n4?4n2(2k)2?4(2k)4?4n2(2k)2 ?[n2?2(2k)2]2?4n2(2k)2?[n2?2(2k)2?2n?2k][n2?2(2k)2?2n?2k]

所以n4?4n为合数。

29

例3 设正整数a,b,c,d满足ab?cd。证明：a?b?c?d不是素数。

证明：由于ab?cd，则设

adu??，其中(u,v)?1，则 cbva?pu,c?pv故a?b?c?d=pu?qv?pv?qu?p(u?v)?q(u?v)?(p?q)(u?v)所以为合数。

d?qu,b?qv评析：此题中采用方法可扩展如下：若

ad?，不妨设gcd(a,c)?s,gcd(d,b)?t,则 cba1sd1tad?，所以1?1，即a1b1=c1d1 c1sb1tc1b1a?a1s,c?c1sb?d1t,b?b1t，且gcd(a1,c1)?gcd(d1,b1)?1由于

所以a1d1c1,gcd(a1,c1)?1，故a1d1。同理可证d1a1，所以a1=d1同理可得c1=b1例4 证明：若正整数a,b满足2a2?a?3b2?b，则a?b和2a?2b?1都是完全平方数。 证明： 因2a2?2b2?a?b?b2，即(a?b)(2a?2b?1)?b2 故只需证a?b和2a?2b?1互质。 设gcd(a?b,2a?2b?1)?d,即证d?1 则da?b,d2a?2b?1

由于d2b2，所以db，又da?b，则da。所以d1，故d?1得证。 故a?b和2a?2b?1互质，所以a?b和2a?2b?1都是完全平方数。 评析：有时，适当的因式分解可以使问题简化，以证得结论。

例5 一个正整数，加上100为一个完全平方数，若加上168则为另一个完全平方数，求这个数。 解：设这个数为x，则

2??x?100?a 其中a,b?N（注：限定正的可减少讨论）。 ?2??x?168?b故(b?a)(b?a)?22?17，从而b?a与b?a则等于把22?17拆开的因数1、2、4、17、34、68.这样就有六种情形。又由于b?a?b?a，且b?a与b?a同奇偶性，故

?b?a?2 ??b?a?34所以b?18,a?16。则x?162?100?156。

例6 求方程x4?y4?z4?2x2y2?2x2z2?2y2z2?24的全部整数解。 解：对原方程进行变形、因式分解

30

(?x2?y2?z2)2?4y2z2?24x4?y4?z4?2x2y2?2x2z2?2y2z2?4y2z2?24(?x2?y2?z2?2yz)(?x2?y2?z2?2yz)?24

(y?z?x)(y?z?x)(y?z?x)(y?z?x)?24左边四个括号内奇偶性相同，而24?23?3为偶数，故括号内每个都为偶数，则应出现24，矛盾。所以原方程无整数解。

例7 证明：两连续正整数之积不能是完全平方数，也不能是完全立方数。

证明：1若有两连续正整数之积为完全平方数，设x(x?1)?t2（x?1,t?2），则(x,x?1)?(x,1)?1，则x与x?1均为完全平方数。

故存在正整数a,b使得x?a2,x?1?b2，从而b2?a2?(b?a)(b?a)?1 这与b?a?2矛盾。所以两连续正整数不能是完全平方数。

设x(x?1)?t3（x?1,t?2），则(x,x?1)?(x,1)?1，则x与2若有两连续正整数之积为完全立方数，

x?1均为完全立方数。故存在正整数a,b使得x?a3,x?1?b3，从而

b3?a3?(b?a)(b2?ba?a2)?1这与b2?ba?a2?3矛盾。所以两连续正整数不能是完全平方数。

例9 在两个相邻的完全平方数n2与(n?1)2之间任取若干个不同的整数，证明它们中两两乘积互不相同。证明：只需证明若n2?a?b?c?d?(n?1)2则ad?bc 若ad?bc，则设

a?pu,b?quc?pv,d?qv（见例3），则q?p,v?u，即q?p?1,v?u?1

d?qv?(p?1)(u?1)?pu?p?u?1

2??pu?a?n ???p?u?2pu?2a?2n?d?n2?2n?1?(n?1)2，矛盾

故在两个相邻的完全平方数n2与(n?1)2之间任取若干个不同的整数，它们中两两乘积互不相同。 评析：与例三的思想方法大同小异，因为它们都利用ad?bc的结论。

例10 求不定方程(n?1)!?nk?1的全部正整数解。

解：当n?1时，无解； 当n?2时，1?2k?1，有k?1； 当n?2是，(n?1)!为偶数，n必为奇数1当n?3时，2?3k?1，k?1

31

2当n?5时，24?5k?1,k?23当n?5时，

n?1n?1n?1(n?2)!(?n?2)，2(n?2)! 222?Ckk?1(n?1)

1(n?1)k?1?故(n?1)(n?2)!，则(n?1)2nk?1而nk?1?(n?1?1)k?1?(n?1)k?Ck所以(n?1)2Ckk?1(n?1)，则?n?1?k，n?1?k故nk?1?nn?1?1?(n?1)!，与(n?1)2nk?1矛盾，则无解。综上，不定方程的正整数解为（2，1）、（3，1）、（5，2）。 评析：通过分析估计归纳，对n分类讨论，一一得出结果。

不等式的应用

I．排序不等式（又称排序原理）

设有两个有序数组a1?a2???an及b1?b2???bn.

则a1b1?a2b2???anbn（同序和）?a1bj1?a2bj2???anbjn（乱序和）?a1bn?a2bn?1???anb1（逆

序和）其中j1,j2,?,jn是1，2，…，n的任一排列.当且仅当a1?a2???an或b1?b2???bn时等号（对任一排列j1,j2,?,jn）成立.

IV．利用排序不等式还可证明下述重要不等式.

切比雪夫不等式：若a1?a2???an，b1?b2???bn ，

则

a1b1?a2b2???anbna1?a2???anb1?b2???bn??.

nnn

证明：由题设和排序不等式，有a1b1?a2b2???anbn=a1b1?a2b2???anbn，

a1b1?a2b2???anbn?a1b2?a2b3???anb1，

……a1b1?a2b2???anbn?a1bn?a2b1???anbn?1. 将上述n个不等式叠加后，两边同除以n2，即得欲证的不等式.

赛题精讲

I．排序不等式的应用

应用排序不等式可以简捷地证明一类不等式，请看下述例题.

例1：对a,b,c?R，比较a?b?c与ab?bc?ca的大小. 取

两

组

数

?333222a,b,c;a2,b2,c2.不管

a,b,c的大小顺序如何，

a3?b3?c3都是同序和a2b?b2c?c2a都是乱序和，故a3?b3?c3?a2b?b2c?c2a.

a2?b2b2?c2c2?a2a2b2c2?????. 例2：a,b,c?R，求证a?b?c?2c2a2bbccaab? 32

【思路分析】 应先将a、b、c三个不失一般性地规定为a?b?c?0. 【略解】由于不等式关于a、b、c对称，可设a?b?c?0. 于是a?b?c,2222111111111??.由排序不等式，得a2??b2??c2?(逆序和)?a2??b2??c2?abcbcacba（乱序和）.及a?

111111?b2??c2??a2??b2??c2?. abccab以上两个同向不等式相加再除以2，即得原式中第一个不等式.再考虑数组

111，仿上可证第二个不等式，请读者自己完成. ??bccaab111例6：设正数a,b,c的乘积abc?1，试证：(a?1?)(b?1?)(c?1?)?1.

bcaa3?b3?c3?0,及【略解】设a?

xyz,b?,c?，这里x,y,z都是正数，则原需证明的不等式化为 yzx(x?y?z)(y?z?x)(z?x?y)?xyz,显然x?y?z,y?z?x,z?x?y中最多只有一个非负数.若

x?y?z,y?z?x,z?x?y中恰有一个非正数，则此时结论显然成立.若x?y?z,y?z?x,z?x?y均为正数，

则x,y,z是某三角形的三边长.容易验证

1 (x?y?z)(y?z?x)(z?x?y)?[(x2(y?z?x)?y2(z?x?y)?z2(x?y?z)].

3

故得(x?y?z)(y?z?x)(z?x?y)?xyz.

【评述】 利用上述换元的方法可解决同类的问题.见下题：设正数a、b、c的乘积

abc?1,证明

1113???.

a2(b?c)b2(c?a)c2(a?b)2 证明：设a?111,b?,c?,则xyz?1，且所需证明的不等式可化为 xyzx2y2z23xyz???，现不妨设x?y?z，则?? ，据排序不等式 y?zz?xx?y2y?zz?xx?y

x2y2z2xyz???z??x??y?得 y?zz?xx?yy?zz?xx?yx2y2z2xyz???y??z??x? 及两式相加并化简可得 y?zz?xx?yy?zz?xx?y

x2y2z22(??)?x?y?z?33xyz?3. y?zz?xx?y例7：设实数x1?x2???xn,y1?y2???yn,z1,z2,?,zn是y1,y2,?,yn的一个置换，证明：

?(xi?1ni?yi)??(xi?zi)2.

2i?1n 33

【略解】 显然所需证不等式等价于

?xy??xz,这由排序不等式可直接得到.

iiiii?1i?1nn【评述】 应用此例的证法可立证下题：

nak1设ak是两两互异的正整数（k?1,2,?)，证明对任意正整数n，均有?2??.

i?1ki?1kn

证明：设b1,b2,?,bn是a1,a2,?,an的一个排列，使b1?b2???bn，则从条件知对每个1?k?n,bk?k，

nnnakbk1于是由排序不等式可知?2??2??.

i?1ki?1ki?1k

求不定方程x1?x2?x3?3x4?3x5?5x6?21的正整数解的组数．

解 令x1?x2?x3?x，x4?x5?y，x6?z，则x?3,y?2,z?1．先考虑不定方程x?3y?5z?21满足

x?3,y?2,z?1的正整数解．?x?3,y?2,z?1，?5z?21?x?3y?12，?1?z?2．

当z?1时，有x?3y?16，此方程满足x?3,y?2的正整数解为(x,y)?(10,2),(7,3),(4,4)． 当z?2时，有x?3y?11，此方程满足x?3,y?2的正整数解为(x,y)?(5,2)． 所以不定方程x?3y?5z?21满足x?3,y?2,z?1的正整数解为

(x,y,z)?(10,2,1),(7,3,1),(4,4,1),(5,2,2)．

又方程x1?x2?x3?x(x?N,x?3)的正整数解的组数为Cx?1，方程x4?x5?y(y?N,x?2)的正整数解的组数为Cy?1，故由分步计数原理知，原不定方程的正整数解的组数为

2121211C9C1?C6C2?C3C3?C2C41?36?30?9?6?81．

21

例题选讲

例1 100个正整数之和为101101，则它们的最大公约数的最大可能值是多少?证明你的结论.

注：看上去不好处理，实际比较容易，101101?101?1001，这样就好处理了，此时101为质数，比较好讨论了，

101为质数，可以取a1?a2?a3?2?a99?1001,a100?2

例2证明：对一切整数n,n?2n?12不是121的倍数. 注解：n?2n?12?(n?1)?11，分析可以得到 例3能否有正整数m、n满足方程m?2009?n

注解：2009?41?49

例4一个正整数不是42的正整数倍和合数（不为零）之和，这个数的最大值是多少？

34

2222解析：这个整数必定可以写成42n?p，其中p为1或素数，其中 p?1,2,3,5,7,11,13,17,19,23,29,31,37,41，因为可以从42(n?1)?p?42，所以先排除

p?2,3,7,13,23,再者，有42(n?2)?p?84，所以可以排除

p?1,11,17,31,37,41，最后42(n?3)?p?126，所以可以排除p?19,29,，只有p?5，n可以较大，通过尝试，

可以得到n?5

例5设a,b,c是三个互不相等的正整数。求证：在ab?ab，bc?bc，ca?ca三个数中,至少有一个能被10整除。

注：比较好考虑，分如下几类。

（1）三者中有10的倍数，则自然可以考虑。 （2）若无10的倍数，则

当三者均为偶数时，因为偶数的平方其个位数为4，6，a,b,c中必定有两个个位数相同，命题得证。

当三者均为奇数时，如果有个位数为5，则显然成立。如果没有5，则a,b,c中必定有两个个位数相同（为1，9），命题得证。

当三者为1偶2奇，或2偶1奇时，ab?ab，bc?bc，ca?ca均为偶数，只要考虑三个数中必定有5的倍数即可。a,b,c除以5的余数只有两种情形：1，4，所以其中必定有一个为10的倍数。 例6 证明：T?1?a33333322222233333322211??231?(n?1)不是整数 n,n中，有且仅有

???1注：k?2kpk，其中pk为奇数，令2?n的最大正整数为?，则2?n。这样在1,2,3,4,5,一个k其标准分解式中有2。从而2???1p1??pnT?2?p1??11?pn?1????231???，毫无疑问，有n?2?p1??pnT?整数＋

1p1p22pn，矛盾。

811n例7求所有这样的自然数n，使得2?2?2是一个自然数的平方. 解析：（1）当n?8时，N?2?2?2?(2数.逐一验证n?2,4,6,8知，N都不是平方数. 则2（2）当n?9时，N?2?2?2?2?11不是平方数. （3）当n?10时，N?2(9?2n?108n?82n?8n?8)，要N为平方数，9?2应为奇数的平方，不妨假设9?2=(2k?1),

811n8?n?211?n?1)，因（…）为奇数，所以要使N为平方数，n必为偶

81198?(k?1)?(k?2).由于k?1和k?2是一奇一偶，左边为2的幂，因而只能k?1=1，于是得k?2，由

2n?10?22知n?12为所求.

35

例1．求不定方程

解：先求

的整数解。

的一组特解，为此对37，107运用辗转相除法：

，

，

将上述过程回填，得：

由此可知，是方程的一组特解，于是，是方

程的一组特解，因此原方程的一 切整数解为：

例2．求不定方程

的所有正整数解。

。

解：用原方程中的最小系数7去除方程的各项，并移项得：

因为是整数，故也一定是整数，于是有，再用5去除比式的两边，得

，令

经观察得

为整数，由此得。

，所

是最后一个方程的一组解，依次回代，可求得原方程的一组特解：

以原方程的一切整数解为：

例3．求不定方程

。

的正整数解。

的取值范围，因为

的最小值为1，所以

解：显然此方程有整数解。先确定系数最大的未知数

。当时，原方程变形为，即，由上式知是偶数且

故方程组有5组正整数解，分别为，，，，；

当时，原方程变形为，即，故方程有3组正整数解，分别为：，，

；当时，原方程变形为，即，故方程有2组正整数解，分别为：，

；

36

当时，原方程变形为，即

8 4 1

10 1 1

，故方程只有一组正整数解，为2 9 2

4 6 2

6 3 2

2 5 3

4 2 3

2 1 4

。

故原方程有11组正整数解（如下表）：

2 4 6

13 10 7

1 1 1

例5．在直角坐标平面上，以（199，0）为圆心，以199为半径的圆周上的整点的个数为多少个？ 解：设显然但当

时，为圆

上任一整点，则其方程为：

为方程的4组解。

（因为199是质数），此时，。因为

这与199为

，可设型的质数矛盾！ 。

是一组勾股数，故199可表示为

，

；

两个正整数的平方和，即

则

因而圆O上只有四个整点于是

。

例8．求证：边长为整数的直角三角形的面积不可能是完全平方数。

证明：假设结论不成立，在所有的面积为平方数勾股三角形中选取一个面积最小的，设其边长为

，

则是平方数，则必有

是偶数）

。因为，故存在整数。

中一奇一偶，，使

得（不妨设

由于即因为

是奇数，易知

是完全平方数，而知

，所以，于是

得

与

即

两两互素，故它们是平方数，

，另一个是

，而

；

中有一个是

另一方面，

所以，以

为边的三角形都是直角三角形，其面积等于是平方数，

37

但是

，于是构造出了一个面积更小的勾股三角形，矛盾！

38

39

例3．设k证明：n?1是一个奇数，证明L对于任意正整数n，数1k?2k???nk不能被n?2整除。

?1时，结论显然成立。设n?2，记所说的和为A，则：

2A?2?(2k?nk)?(3k?(n?1)k)???(nk?2k)。

由k是正奇数，从而结于每一个i?2，数ik?(n?2?i)k被i?(n?2?i)?n?2整除，故2A被n?2除得余数为2，从而

。 2）

A不可能被n?2整除（注意n?2?例4．设m,n是正整数，m?mn（2?1）（2?1）。 2，证明：

证明：首先，当n?m时，易知结论成立。事实上，m出来（注意m?最后，n。 2）

?n时，结论平凡；当n?m时，结果可由2n?1?2m?1?1?2m?1推

?m的情形可化为上述特殊情形：由带余除法n?mp?r,0?r?m而q?0，由于2n?1?(2mq?1)2r?2r?1，从

n而由若n是正整数，则x?yn?(x?y)(xn?1?xn?2y???xyn?2?yn?1)知(2m?1)|(2mq?1)；而0?r?m，故由上面证明了的结论知

mn(2m?1) (2r?1)（注意r?0时结论平凡），从而当n?m时，也有（2?1）（2?1）。这就证明了本题的结论。

例5．设正整数a,b,c,d满足ab?cd，证明：a?b?c?d不是质（素）数。 证法一：由ab?cd，可设约分数

admama??其中(m,n)?1。由?意味着有理数cbncnc的分子、分母约去了某个正整数u后得既

mn，因此，a?mu,c?nu ①

同理，存在正整数v使得b?nv,d?mv

②

因此，a?b?c?d＝(m?n)(u?v)是两个大于1的整数之积，从而不是素数。

注：若正整数a,b,c,d适合ab?cd，则a,b,c,d可分解为①及②的形式，这一结果在某些问题的解决中很有作用。 证法二：由ab?cd，得b?cda，因此a?b?c?d?a?cd(a?c)(a?d)，因为a?b?c?d是整数，故?c?d?aa(a?c)(a?d)也是整数。

a若它是一个素数，设为可见

p，则由(a?c)(a?d)?ap

③

p整除(a?c)(a?d)，从而素数p整除a?c或a?d。不妨设p｜a?c，则a?c?p，结合③推出a?d?a，而

。 ?1）

这是不可能的（因为d例6．求出有序整数对（

m,n）的个数，其中

1?m?99，1?n?99，(m?n)2?3m?n是完全平方数。

（1999年美国数学邀请赛试题） 解：由于1?m?99，1?n?99可得：

(m?n)2?3m?n＜(m?n)2?4(m?n)?4?(m?n?2)2。

又(m?n)

2?(m?n)2?3m?n，于是(m?n)2?(m?n)2?3m?n?(m?n?2)2

40

若(m?n)然而

2?3m?n是完全平方数，则必有(m?n)2?3m?n＝(m?n?1)2。

(m?n)2?3m?n＝(m?n?1)2?n?m?1，于是必有n?m?1?0，即m?n?1，此时n?2,3,?,99，

m?1,2,?,98。所以所求的有序整数对（m,n）共有98对： (m,n)?(1,2),(2,3),(3,4),?,(98,99)。

例7．证明：若正整数a,b满足2a2?a?3b2?b，则a?b和2a?2b?1都是完全平方数。

（2006年山东省第二届夏令营试题）

证法一：已知关系式即为2a2?a?3b2?b?2(a2?b2)?(a?b)?b2

①

2（2a?2b?1）＝b ?（a?b）

若a，结论显然。 ?b?0（或者说a,b中有一个为0时）

不妨设a?b且ab?0，令(a,b)?d，则a?a1d,b?b1d，(a1,b1)?1

?b1)d，将其代入①得2a1d?a1?b1?3b1d

22从而a?b＝(a1因为d2 ②

|2a1d，所以d|(a1?b1)，从而d?a1?b1；

?b1)(2a1?2b1?1)?b1d2；

?1，所以(a1?b1,b1)?1?(a1?b1)

而②式又可写成(a1因为(a,b)所以(a1所以d?d且(a1,b1)?b1)|d，从而a1?b1?d。

?a1?b1，所以a?b＝(a1?b1)d?d2，从而a?b为完全平方数。

b2b2所以2a?2b?1?2?()也是完全平方数。

dd证法二：已知关系式即为2a2?a?3b2?b?2(a2?b2)?(a?b)?b2

①

2（2a?2b?1）＝b ?（a?b）

论证的关键是证明正整数a?b与2a?2b?1互素。 记d知

2。若d?1，则d有素因子p，从而由①知p|b。因为p是素数，故p|b，结合p|(a?b)?（a?b，2a?2b?1）

p|a，从而由p|2a?2b?1得p|1，这是不可能的。故d?1，从而由①推知正整数a?b与2a?2b?1都是完全平方数。

例8．证明不存在正整数n，使2n2+1，3n2+1，6n2+1都是完全平方数。

证明：假设存在这样的正整数n，使2n2+1，3n2+1，6n2+1都是完全平方数，那么 （2n2+1）（3n2+1）（6n2+1）也必定是完全平方数。 而（2n2+1）（3n2+1）（6n2+1）＝36n6+36n4+11n2+1；

41

(6n3?3n)2?36n6+36n4+9n2；(6n3?3n?1)2?36n6+36n4+12n3+9n2+6n+1；

332?3n)2?（2n2+1）（3n2+1）（6n2+1）＜(6n?3n?1)与（2n2+1）（3n2+1）（6n2+1）为完全平方数矛盾。

所以(6n1．证明：如果证明：因为p和p?2都是大于3的素数，则6是p?1的因子。

p是奇数，所以2是p?1的因子。又因为p，p?1，p?2除以3的余数各不相同，而p与p?2都不能被3整数。

于是6是

p?1的因子。

2．设m?n?0，证明：(22n?1)|(22m?1)；

解：由22m?1?(22n?1?1)[(22n?1)2m?n?1???22n?1?1]n?1，故(22?1)｜（22m?1）

。 又因为22n?1?1?(22n?1)(22n?1)，从而(22n?1)｜(22n?1?1)，于是由整除的性质知

(22n?1)|(22m?1)。

3．证明：对于任意正整数n，数12005?22005???n2005 不能被n?2整除。

证明：只需证2（n?2）2（12005?22005???n2005）即可。

因为若n是正整数，则xn?yn?(x?y)(xn?1?xn?2y???xyn?2?yn?1)；

若n是正奇数，则xn?yn?(x?y)(xn?1?xn?2y???xyn?2?yn?1)；

故n?2｜22005?n2005；n?2｜32005?(n?1)2005，……， n?2｜n2005?22005

所以n?2｜2（22005???n2005）

。 又因为n?2?3?2，所以n?2 2，所以n?2 2（22005???n2005）＋2

即（n?2）2（12005?22005???n2005）命题得证。

4．已知n为正奇数，求证：60|6n?3n?2n?1。

证明：因为若n是正整数，则xn?yn?(x?y)(xn?1?xn?2y???xyn?2?yn?1)； 若n是正奇数，则xn?yn?(x?y)(xn?1?xn?2y???xyn?2?yn?1)；

所以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；

又(3,4,5)?1且3?4?5?60，所以60|6n?3n?2n?1。

42

例1． 设x,y是正整数，x解：设(x,y)?y且x?y?667，它们的最小公倍数是最大公约数的120倍，求x,y。

?d，则x?md,y?nd，其中(m,n)?1且m?n，于是[x,y]?mnd。

?nd?667?(m?n)d?23?29??md所以?mnd即? 3?120?mn?2?3?5??d由m?n及（2）可得：

?m?1?m?2?m?3?m?4;?;?;?;?n?40n?30n?120n?60????由（1）可知只能取?(1)(2)

?m?5?m?6?m?8?m?10。 ;?;?;??n?24n?20n?15n?12?????m?5?m?8;?;

?n?24?n?15从而d?23或29，故x?115,y?552或x?232,y?435。

?0，mn|(m2?n2)，则m?n。

例2．设m,n证明：设(m,n)22?d，则m?m1d，n2?n1d，其中(m1,n1)?1。于是，已知条件转化为m1n1|(m1?n1)，故更有

22m1|(m1?n1)，从而转化为m1|n1因此m，但是(m1,n1)?1，故(m1,n1)?1，结合m1|n122，知必有m1?1，同时n1?1，

?n。

例3．设正整数a,b,c的最大公约数是1，并且证明：设(a,b)化为da1b1ab?c，证明a?b是一个完全平方数。

a?b?d，则a?a1d，b?b1d，其中(a1,b1)?1，由于(a,b,c)?1，故(b,c)?1，现在问题中的等式可以转

?ca1?cb1

①

由此可见a1整除cb1。因为(a1,b1)?1，故a1|c，同样可得b1|c，再由(a1,b1)?1便可以推出a1b1|c。设c?a1b1k，其

中k是一个正整数。一方面，显然k整除c；另一方面，结合①式，得d故k?k(a1?b1)，故k|d，从而k|(c,d)，但(c,d)?1，

?1。

?a1?b1，故a?b?d(a1?b1)?d2，这样就证明了a?b是一个完全平方数。

因此，d例4．

a,b都是正整数，是否存在整数p,q使得对任意的正整数n，p?na与q?nb互质？ ?[a,b]，r?解：令L令

LL,s?，则(r,s)?1，于是存在整数x,y使得rx?sy?1， abp?x,q??y，则对任意的正整数n，设dn?(p?na,q?nb)，有dn|(r(p?na)?s(q?nb))

所以dn|1?dn?1，即对任意的正整数n，（p?na，?rx?sy?1，ra?L?sb，

即dn|(rp?sq?n(ra?sb))，而rp?sqq?nb）＝1。

43

n3?1例6．求出所有的正整数对(m,n)，使得是一个整数。

mn?1（2006年山东省第二届夏令营试题）

解：由于(m3,mn?1)?1且mn?1|n3?1?mn?1|m3(n3?1)?mn?1|m3n3?1?m3?1

?mn?1|m3?1，所以m,n是对称的。不妨设m?n。

n3?1n2?n?11??n??N*?n?2，从而m?n＝2； 当m?n时，则2n?1n?1n?1当m?n时，若n?1时，则有m?1|2，所以m?2或3；

若

n?2时，由于

n3?1mn?1是一个整数，从而

?k?N*使得

n3?1?(kn?1)(mn?1) 即

1n3?1n3?11?2?n?，所以kn?1＜1?。 kn?1?n?1mn?1n?1n?1 又由于n?2，k?N*，所以k?1。

3

n2?12?n?1??N*得n?2或3，所以n?1?(n?1)(mn?1)?mn?n?mn?1，从而m?所以m?5；

n?1n?13综上知所有的(m,n)为（2,2）,(2,1),(1,2),(3,1),(1,3),(5,2),(2,5),(5,3),(3,5).

例7．已知a,b,m,n?N，且(a,b)*?1,a?2，试问an?bn|am?bm的充要条件是n|m吗？

（2006年山东省第二届夏令营试题）

分析：因为a又ark?bk?ak?n(an?bn)?bn(ak?n?bk?n)，所以an?bn|ak?bk?an?bn|ak?n?bk?n；

?br?ar?n(an?bn)?bn(ar?n?br?n)，所以an?bn|ar?br?an?bn|ar?n?br?n；

令m?nq?r(0?r?n)，则有an?bn|anq?r?bnq?r?an?bn|a(q?1)n?r?b(q?1)n?r

?an?bn|a(q?2)n?r?b(q?2)n?r???an?bn|ar?(?1)qbr

又因为n?r，所以ar?(?1)qbr?an?bn

从而上式?r?0且q为奇数，即an?bn|am?bm的充要条件是n|m且

3mn为奇数。

例8．我们知道2?1?9有1个质因子，且32|23?1；

2

23?1?513?33?19有2个质因子，且33|23?1

2 ………………

44

如此下去，我们可以猜想：k?N*, 23?1至少有k个质因子，且3k?1|23?1。试证明之。

（2006年山东省第二届夏令营试题）

kk

证明：令ak＝23k?1，则ak＝3k?1bk，即要证bk是整数且有k?1个质因子。下用数学归纳法证明bk是整数。

k?1时，结论显然； 假设n?k时，成立；

当n?k＋1时，因为ak?1因为3k?1?(ak－1)3+1=ak3－3ak2＋3ak；

|ak，所以3k?2|ak?1，即bk?1是整数。

下证bk?1至少有k个质因子。

ak?1?3k?2bk?1＝ak3－3ak2＋3ak＝(3k?1bk)3－3(3k?1bk)2＋3(3k?1bk).

因为bk?1＝bk(32k?1bk2?3k?1bk?1)，令ck?32k?1bk2?3k?1bk?1，则bk?1＝bkck

由于(ck,3)=1，所以(ck,bk)=1，从而ck必有异于bk质因子的质因子， 所以bk?1至少有k个质因子。 证毕！ 1．若n?N,m是奇数，则(2分析：要证明2我们可以想到2mm?1,2n?1)?1。

?1与2n?1互质，我们只需要证明它们的公因子为1即可，但是这对于m,n不好处理，由m为奇数这一条件，

|2mn?1从而找到思路。

nm证明：由于m为奇数，故2（2mn，而?1|2mn?1，又2m?1|2mn?1，从而（2m?1，2n?1）?（2mn?1,2mn?1）

?1,2mn?1）＝（2mn?1,2）＝1，故(2m?1,2n?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). 3．设n,a是正整数，若

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

ncc证明：设a是非整数的有理数，则可设na?,b?1,(b,c)?1，于是a?n。因为(b,c)?1

bbncn故可知(b,c)?1。但b?1，因而b|c。这与n?a是整数矛盾！证毕。

bnnnnn4．设a,b是不全为0的整数，一切形如ax+by(x,y?N)的数中，最小的正数是d，试证：d=(a,b). 5.记Fn＝22n＋1，试证：(Fn,Fm)=1,这里m?n.

例1．试解方程：

?5?6x?15x?7?。

??5?8?45

解：因为左边是整数，因而右边的分式也应该是整数，所以

15x?7?5?6x??5?6x15x?7???????0

???8558????于是

81?90x?81?90x??0，从而0??1，故0?81?90x?40。

??40?40?但是

15x?7是整数，故15x?5t?7，t?Z，代入前面的不等式，得0?39?30t?40,t?Z，直接观察即知t?0,1，于是574x?,。

155例2．数100！的十进位制表示中，未尾连续地有多少位全是零？

解：命题等价于100！最多可以被10的多少次方整除。因为10?2?5因而100！中2的指数大于5的指数，所以100！中5的指数就是所需求出的零的位数。 由??100??100?????2??20?4?24即可知100！的未尾连续地有24位全是数码零。

?5???5?33例3．试求(257解：由于(x33?46)26被50除所得的余数。

?46)26是关于x的整系数多项式，而257?7(mod50)，于是知

(25733?46)26?(733?46)26(mod50)。

又注意到72?49??1(mod50)，故(25733?46)26?(733?46)26(mod50)?((72)16?7?46)26

?((?1)16?7?46)26?(7?46)26?5326?326(mod50)

又35?243?250?7??7(mod50)，所以(25733?46)26?(35)5?3?(?7)5?3

??(72)2?7?3??21?29(mod50)

注意到0?29?50，因而29就是所求的余数。 说明：在上述过程中，我们已经看到7有用的。事实上，若

2?49??1(mod50)的作用。一般而言，知道一个整数的多少次幂关于模同余于?1是非常

，则对大的指数

ak?1(modm)n利用带余除法定理，可得

n?kq?r,0?r?k，于是有

an?akq?r?(ak)qar?ar(modm)，这里余数r是一个比n小得多的数，这样一来，计算an的问题，就转化成了计算余数r次

幂a的问题，从而使计算简单化。 例4．设ar?101010，计算某星期一后的第a天是6星期几？

2解；星期几的问题是被7除求余数的问题。由于10?3(mod7)，于是10?32?2(mod7)，

103?33?2?3?6??1(mod7)，因而106?1(mod7)。

为了把指数a的指数10

10写成6q?r的形式，还需取6为模来计算1010。为此我们有

46

10?4(mod6)，进而有

102?42?4(mod6)，

103?43?4(mod6)，依次类推，有

1010?4(mod6)，所以

1010?6q?4(mod6)

从而，a?106q?4?(106)q?104?1q?104?34?4(mod7)

这样，星期一后的第a天将是星期五。 例5．求所有的素数分析：要使4p2p，使4p2?1与6p2?1也是素数。

?1与6p2?1也是素数，应该是对p除以某个数素q的余数进行分类讨论，最后确定p只能是这个素数。由于只

有两个数，所以q不能太大，那样讨论起来也不会有什么效果，试验q解：设u若r若r即r?2,3发现对本题不起任何效果，现对q?5展开讨论。

?4p2?1，v?6p2?1，且p?5k?1,k?Z,r?{0,1,2,3,4}

?1或4时，p2?1(mod5)，u?4p2?1?4?1?0(mod5)； ?2或3时，p2?4(mod5)，v?6p2?1?24?1?0(mod5)； ?0时，u,v为5的倍数且比5大，不为质数。故r?0，此时p?5，

u?52?4?1?101；v?52?6?1?151都是素数。

即可题有唯一解

p?5。

p,p?2,p?4均为质数，可得p只能为

3，由

注：要使几个数同为质数，一般是对这几个数也合乎以某一质数的余数来确定，如于这是

p的一次式，故三个数就模3，而二次式对三个数就模5，四个数一般就模7了。

m例6．求满足|12分析：如果5n?5n|?7的全部正整数m,n。

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

m 如果12得?5n?5n?7，而m,n中有一个大于1，则另一个也大于1，mod3得?(?1)n?1(mod3)，故n为奇数，mod8，

??1(mod8)，而52?1(mod8)，n为奇数，从而?5??1(mod8)，矛盾！

所以m?n?1为唯一解。

27an?45an?36注：在解不定方程时，往往要分情况讨论，也常常利用同余来导出一些性质求出矛盾！

例7．数列{an}满足：a0?1,an?1?2,n?N.

?1为完全平方数。

（2005年全国高中数学联赛试题）

证明：（1）对任意n?N,an为正整数；(2)对任意n?N,anan?1证明：（1）由题设得

2a1?5,且{an}严格单调递增.将条件式变形得2an?1?7an?45an?36,两边平方整理得

22an?1?7anan?1?an?9?0

①

47

?a2?7a2nn?1an?an?1?9?0

②

①-②得(an?1?an?1)(an?1?an?1?7an)?0,an?1?an,?an?1?an?1?7an?0?

an?1?7an?ab?1.

③

由③式及a0?1,a1?5可知，对任意n?N,an为正整数.

（2）将①两边配方，得(an?1?a1ann)2?9(anan?1?1),?anan?1?1?(an?3)2. ④

由③式an?1?an?9an?(an?1?an)≡?(an?an?1)?mod3?

∴a?ann?1?ann?1n≡(?1)?a1?a0?≡0（mod3）∴

a3为正整数，④式成立.

?anan?1?1是完全平方数.

例8．若

3n?1n(2n?1)可以写成有限小数，那么自然数n的值是多少？

解：由于(n,3n?1)?1

若3n?1与2n?1互素，则分数p?3n?1n(2n?1)是既约分数；

若

3n?1与

2n?1不互素，设它们的公约数为

d，且

d?1，设

3n?1?da,2n?1?db，d(2a?3b)?2(3n?1)?3(2n?1)?5，故3n?1与2n?1的公约数是5，此时分数p的分子、分母只有公约数5。

由于

p可以写成有限小数，故约分之后p的分母除了2,5以外，没还有其它的公约数，因此n(2n?1)?2k?5m。

n?1)?1，故??n?2k因为2n?1是奇数，(n,2，即2k?1m?1。

?2n?1?5m?5由于5m?1?2(mod4)故2k?1?2(mod4)，从而k?0，即m?0,n?1， 故只有n?1,p才是有限小数。

练习

1． 试求方程

??5?6x?15x?74?8???75的实数解x。（答案：x?15,5） 2． 若?(n)?16，试出至少5个n的值。（答案：17，32，34，40，48） 3． 试求(199810?1999)50被25除所得的余数。（答案：24）

4． 设整数n使an?1(modm)，这些n中最小的正整数为?，试证：?|n。特别地，若(a,m)?1，则?|?(m)。

则

48

证明：设n??q?r,0?r??，则易知ar?(a?)qar?an?1(modm)，但?2是最小的正整数，故r只能为0，即n??q。

5． 设a是任意整数，试证下面形状的数都不是完全平方数：（1）5a?2；（2）5a解：（1）5a?2? （2）5a2?6。

2不同余x2(mod5)；

?6?a2?2?2或3(mod5)，但x2?0或1(mod5)。

x6． 求所有满足8?15y?17z的正整数三元组(x,y,z)。

127． 例1.设(91,ab)?1，求证：91|(a?b12)。

8． 证明：因为91?7?13，故由(91,ab)?1知(91,a)?1，从而(7,a)?1,(13,a)?1，但是?(7)?6,?(13)?12，故由

欧拉定理得：a9． 于是，a1212?(a6)2?12?1(mod7)，a12?1(mod13)，从而a12?1(mod91)；同理，b12?1(mod91)。

?b12?1?1?0(mod91)，即91|(a12?b12)。

n210．注明：现考虑整数a的幂a所成的数列：a,a,?,an,?若有正整数k使ak?1(modm)，则有an?ar(modm)，其中

n?kq?r,0?r?k；

11．因而关于mod(m)，数列a,a2,?,an,?的项依次同余于a,a2,?,ak,a,a2,?,ak,a,?这个数列相继的k项成一段，

各段是完全相同的，因而是周期数列。如下例： 12．下面我们着重对Fetmat小定理及其应用来举例： 13．例3．求证：对于任意整数x，14．证明：令

15137x?x?x是一个整数。 5315117f(x)?x5?x3?x，则只需证15f(x)?3x5?5x3?7x是15的倍数即可。

5315515．由3，5是素数及Fetmat小定理得x16．3x17．而（3，5）=1，故3x18．例4．求证：273019．证明：令20．所以

55?x(mod5)，x3?x(mod3)，则

?5x3?7x?3x?7x?0(mod5)；3x5?5x3?7x?2x?x?0(mod3)

?5x3?7x?0(mod15)，即15f(x)是15的倍数。所以f(x)是整数。

|n13?n（n为任意整数）。

f(n)?n13?n，则f(n)?n(n?1)(n?1)(n2?n?1)(n2?n?1)(n6?1)；

f(n)含有因式n7?n,n5?n,n3?n,n2?n

1321．由Fetmat小定理，知13|n?n,7|n7?n,5|n5?n,3|n3?n,2|n2?n

1322．又13，7，5，3，2两两互素，所以2730=13?7?5?3?2能整除n?n。

23．例5．设a,b,c是直角三角形的三边长。如果a,b,c是整数，求证：abc可以被30整除。

49

24．证明：不妨设c是直角三角形的斜边长，则c25．若2 a，2 b，2 c，则c26．所以2|abc.

27．若3 a，3 b，3 c，因为(3k22?a2?b2。

?a2?b2?1?1?0(mod2)，又因为c2?1(mod2)矛盾！

22?1)2?1(mod3)，(od则a?b?1?1?2m23)，(od又c?1m3)，矛盾！从而3|abc.

28．若 5 a，5 b，5 c，因为(5k29．所以a2?1)2?1(mod5)，(5k?2)2??1(mod5)，

?b2??2或0(mod5)与c2??1(mod5)矛盾！

30．从而5|abc.

31．又(2,3,5)=1，所以30|abc. 32．下面讲述中国剩余定理的应用

33．例6．证明：对于任意给定的正整数n，均有连续n个正整数，其中每一个都有大于1的平方因子。 34．证明：由于素数有无穷多个，故我们可以取n个互不相同的素数

① 35．因为

2p1,p2,?,pn，而考虑同余组x??i(modp),i?1,2,?,n

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

222n个数

x?1,x?2,?,x?n分别被平方数p1,p2,?,pn整除。

36．注：（1）本题的解法体现了中国剩余定理的一个基本功效，它常常能将“找连续n个正整数具有某种性质”的问题转化为“找n个两两互素的数具有某种性质”，而后者往往是比较容易解决的。

37． （2）本题若不直接使用素数，也中以采用下面的变异方法：由费尔马数Fk化为Fi2?22?1(k?0)两两互素，故将①中的pi2转

k(i?1,2,?,n)后，相应的同余式也有解，同样可以导出证明。

38．例7．证明：对于任意给定的正整数n，均有连续n个正整数，其中每一个都不是幂数。

39．分析：我们来证明，存在连续n个正整数，其中每一个数都至少有一个素因子，在这个数的标准分解中仅出现一次，从而这个数

不是幂数。

40．证明：取n个互不相同的素数41．因为

p1,p2,?,pn，考虑同余组x??i(modp2),i?1,2,?,n

p1,p2,?,pn222显然是两两互素的，故由中国剩余定理知，上述同余组有正整数解。

42．对于1?i?n因为x?i?pi(modpi2)，故pi2|(x?i)，但由①式可知pi2 (x?i)，即pi在(x?i)的标准分解中恰好出

现一次，故x?1,x?2,?,x?n都不是幂数。

43．例8． 设n,k是给定的偶数，n?0且k(n?1)是偶数。 44．证明：存在整数x,y使得(x,n)?(y,n)?1，且x?45．证明：我们先证明，当n为素数幂46．y?k(modn)。

p?时结论成立。实际上，能够证明，存在x,y使

p xy且x?y?k：

50

本文来源：https://www.bwwdw.com/article/6o9p.html