奥数的几个重要定理

奥数的几个重要定理

费马小定理.

若(a,n)=l,n是质数，则三l(mod〃)

例1、设正整数a,b,使15a+l6b和16a—15b都是正整数的平方，求这两个平方数中较小的

一个最小值.

解：(式子化)由已知，可设

15a+16/?=r2..

r,teN+

16a-15。=产

(求min(min(厂2,t2)))

a-br-t

(变形)「15/+16/=481a①

Y

16--15/=48仍②

481=13x37

猜想户一都是13x37的倍数

即厂/都是13的倍数，且都是37的倍数.

先证：厂子是13的倍数(*)

事实上，若厂/至少有一个不是13的倍数，则由15户+16r=481。

可知都不是13的倍数，从而(/,13)=1,。,13)=1

又16r2三15『(mod13)(消元：用费马小定理)

16户严三15严(mod13)

16/严=15x1

6

((4/)2)6=15

12三l(n»d13)

矛盾

嘟是13的倍数

若r,t至少有一个不是37的倍数，则r4都不是37的倍数，于是

16r2三15一(mod37)

16户产三15户

(4AY17)2=15(mod37)

(4/)36=15i8(mod37)

1518=l(mod37)

2259=l(mod37)

39三l(mod37)

273=l(mod37)

(-10)3=l(mod37)

-1000=l(mod37)

-1000=(-27)-37-1

-1=l(mod37)

36=l(mod37)

矛盾

.,，,嘟是37的倍数

r,嘟是481的倍数

户,户都是48俨的倍数

猜想广的最小值为I8F

证猜想：只需证，存在黄足已知条件的Z,。，使「=4812,事实上

在①，②中令/=产=48〃得

(15+16)-4812.

a=----------------=3O11x481

481

^=(16-15).48P=481

481

.•.当a=31x4811=481时，满足已知条件，并且r=48「，产=48〃

故，所求最小值为4812

高斯函数

这一讲介绍重要的数论函数y=[x],称为高斯函数，又称取整函数。它是数学竞赛热

点之一。

定义一：对任意实数X,[幻是不超过X的最大整数，称[X]为X的整数部分。与它相伴随

的是小数部分函数y={%},{%}=x-[x].

由[幻、｛%｝的定义不难得到如下性质：

(1)y=[x]的定义域为R,值域为Z；y=｛x｝的定义域为R,值域为。1)

(2)对任意实数无，都有x=[x]+｛x｝,且0<｛尤｝<1。

(3)对任意实数尤,都有Lx]Kx<[x]+l,x-l<[x]Wx。

(4)y=[x]是不减函数，即若玉则以』《[4]，其图像如图I—4一5一1；

(5)[x+n]=n+[x]',{x+n\={%}0其中xeR,〃eN*。

(6)[x+y]>[x]+[y];{%{%}+{y}>{%+y};[^x,]>^[x,],xzeR；特别地，

i=li=l

rna^「小

_n

(7)[xy]>[JT]-[y],其中x,”R+；一般有[1[x[2工区],七e七；特别地，

1=1Z=1

[Vx]n<[x],xe7?+,〃£N*。

(8)[-]=[—],其中xeR+,〃eN*。

nn

取整函数或高斯函数在初等数论中的应用是基于下面两个

结论。

定理一：xeR+”N*,且1至尤之间的整数中，有百个是〃的倍数。

n

【证明】因[二]«二<[±]+1,即[二]•“<%<([3]+1)力，此式说明：不大于X而是〃的

nnnnn

倍数的正整数只有这区个：

n

n,2n,•••,[―]•n.

n

定理二：在〃！中，质数p的最高方次数是

M…力+力+字+•••・

【证明】由于p是质数，因此〃!含p的方次数p(〃!)一定是1,2,〃一各数中所

nn

含p的方次数的总和。由定理一知，1,2,…，〃中有[―]个p的倍数，有[f]个p2的

pp~

倍数，…,所以「("!)=[勺+[：]+-•

PP

此定理说明：n[=ppM-M,其中M不含p的因数。例如，由于7(2000!)=[理卬]+「驾^

772

+...=285+40+5=330,贝U2000!=7330.M,其中》M。

定理二：(厄米特恒等式)xeR,〃eN,BOt%]+[x+—]+[x+—]H---F[x+——-]=[nx\

nnn

【证法1】引入辅助函数

12〃277]]

f(X)—\nx\—[x]—[xH]—[%H]—,,,—H------]—[%H-----].因f(XH)=…

nnnnn

=/(x)对一切尤eH成立，所以/(x)是一个以,为周期的周期函数，而当时,

nn

直接计算知/(x)=o,故任意工£火，厄米特恒等式成立。

172—1

【证法2]等式等价于〃[%]+[{%}]+[{x}+—]+…+[{%}+---]=〃[%]+[几{%}].消去

nn

过幻后得到与原等式一样的等式，只不过是对X£[0,l),则一定存在一个人使得

klyxJ，IP(k-l)<nc<k,故原式右端=［九灯=左一1.另一方面，由上l〈x<A知，

nnnn

k1左+1左+12k+2k+i左+，+lk+n—2kn—1

—<x+—<---,----<x+—<----，…，----<x<------,•••,-------<x<-------

nnnnnnnnnn

在这批不等式的右端总有一个等于1,设——=1,即:〃—左。这时，印=［%+与=…二

nn

［x+--］=0,而［x+上」一］=■■-=［%+--］=1,因此原式的左端是左—1个1

nnn

之和，即左端=左—1.故左=右。

【评述】证法2的方法既适用于证明等式，也适用于证明不等式。，这个方法是：第一步

“弃整”，把对任意实数的问题转化为［0,1)的问题；第二步对［0,1)分段讨论。

高斯函数在格点(又叫整点)问题研究中有重要应用。下面给出一个定理。

定理四：设函数y=/(x)在切上连续而且非负，那么和式⑺］。为以川内的

a<t<b

整数)表示平面区域<瓦0<yK/(x)内的格点个数。特别地，有

(1)位于三角形：y=ax+b>0,c<x<d内的格点个数等于£［。工+加(且％为整数);

c<x<d

(2)(p,q)=l,矩形域内的格点数等于

］冉］

0<Zx<q/24Q+0<Ey<p/2PLL

(3)r>0,圆域/+F内的格点个数等于

l+4[r]+8£[7r2-x2]-

0<x<r/V2

(4)n>0,区域：％>0,y>0,孙K〃内的格点个数等于

2Z[-]-fV^]2o

0<x<4n1

格点

［赛点直击］

L格点，是指方格纸上纵线和横线的交点，如果取一个格点为原点，通过该点的横线

与纵线为X轴和y轴，且设一个方格的边长为1,那么，格点就是平面直角坐标系

中宗横坐标都为整数的点。因此，格点又称为整点。

2.坐标平面内顶点为格点的三角形称为格点三角形，类似地也有格点多边形的概念。

3.格点多边形的面积必为整数或半整数（奇数的一半）。

4.格点关于格点的对称点为格点。

5.设格点多边形内部有I个格点，边界上有p个格点，则格点多边形的面积为

S=/+“—1（见例5）。

2

［赛题精析］

54

例1平面上整点（纵、横坐标都是整数的点）到直线y=+?的距离中的最小值

35

是（）

思路点拨：可以引进整点坐标，利用点到直线的距离公式，建立整点到直线距离的二元

函数。通过对距离函数最值的探求获得问题的解。而不同角度的探求又能得到不同的解法。

解法一已知直线可写成25x—15y+12=0

|25%-15%+12|

整点（x,%）到直线的距离为d=

05734

由%，%均可为整数知|25%—15%+12|必为整数，从而d为无理数，否定C,D.

若选A,贝425%-15%+12|=1

即25x0-15y0=±1

有25%0-15%=-13

或25%0-15%=-11

但25%—15治=5（5%—3%）是5的倍数，不会取-13,-11。故否定A,从而选B

解法二距离d的大小完全有|25%—15%+1］来确定，当125Ao—15%+1［最小时，d

也相应的取最小值。由于25%T5%=5（5%-3%）是5的倍数，故

|25x0-15y0