数学竞赛中的数论问题(4)

0?s?t?p?2?p，

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

r1r2?rp?1?1?2????p?1???p?1?!．

再把上述p?1个等式相乘，有 ?p?1?!ap?1?Mp?r1r2?rp?1， 即 ?p?1?!ap?1?Mp??p?1?!， 其中M是一个整数．

亦即 ?p?1?!?ap?1?1??Mp．

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

p?ap?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?1pk???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?pkk，则

??n??n??1?1???p??1?1?????1?1??． 1??p2??pk? 于

16

由证明 用容斥原理．设S??1,2,?,n?，记Ai为S中能被pi整除的数所组成的集合（i?1,2?,k），用Ai表示Ai中元素的个数，有

Ai?nnn,?,A1?A2???Ak?，Ai?Aj?． pipjp1p2?pkpi易知，S??1,2,?,n?中与n互素的正整数个数为 A1?A2??Ak， 由容斥原理得

A1?A2??Ak?S?

1?i?k?Ai?1?i?j?kk?Ai?Aj

?1?i?j?m?k?Ai?Aj?Am?????1?A1?A2???Ak?n????1?i?k?nnnnk?????????1?pi1?i?j?kpipj1?i?j?m?kpipjpmp1p2?pk?1111k?????????1?? pi1?i?j?kpipj1?i?j?m?kpipjpmp1p2?pk?? ?n?1?1?i?k??1??1??1??n?1???1????1??.p1??p2??pk??注 示意n?3的容斥原理． 推论 对素数p有??p??p?1,?p???p???p??1．

定理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满足

17

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 （平面整点）在平面直角坐标系上，纵横坐标都是整数的点称为整点（也称格点）．类似地可以定义空间整点．

18

第二讲 数论题的范例讲解

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

一、奇数与偶数

整数按照能否被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,?,an是1,2,?,n的某种排列，证明：如果n是奇数，则乘积

?a1?1??a2?2???an?n? 是偶数．

解法1 （反证法）假设?a1?1??a2?2???an?n?为奇数，则ai?i均为奇数，奇

19

m222kk??n?2k?1?．

数个奇数的和还是奇数

奇数=?a1?1???a2?2?????an?n?

??a1?a2???an???1?2???n??0，

这与“奇数?偶数”矛盾． 所以?a1?1??a2?2???an?n?是偶数．

评析 这个解法说明?a1?1??a2?2???an?n?不为偶数是不行的，但没有指出为偶数的真正原因．体现了整体处理的优点，但掩盖了“乘积”为偶数的实质．

解法2 （反证法）假设?a1?1??a2?2???an?n?为奇数，则ai?i均为奇数，ai与

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

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

评析 这个解法揭示了?a1?1??a2?2???an?n?为偶数的原因是“n为奇数”．那么为什么“n为奇数”时“乘积”就为偶数呢？

解法3 1,2,?,n,a1,a2,?,an中有n?1个奇数，放到n个括号，必有两个奇数在同一个括号，这两个奇数的差为偶数，得?a1?1??a2?2???an?n?为偶数．

评析 这个解法揭示了?a1?1??a2?2???an?n?为偶数的原因是“当n为奇数时，． 1,2,?,n中奇数与偶数个数不等，奇数多，某个括号必是两个奇数的差，为偶数”

类似题：

例1-1（1986，英国）设a1,a2,?,a7是整数，b1,b2,?,b7是它们的一个排列，证明

?a1?b1??a2?b2???a7?b7?是偶数．

（a1,a2,?,a7中奇数与偶数个数不等）

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

20

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数学竞赛中的数论问题(4)在线全文阅读。