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

定义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 mo …… 此处隐藏：2891字，全部文档内容请下载后查看。喜欢就下载吧 ……