奧數(shù)的幾個(gè)重要定理

奧數(shù)的幾個(gè)重要定理

費(fèi)馬小定理.

若(a,n)=l,n是質(zhì)數(shù)，則三l(mod〃)

例1、設(shè)正整數(shù)a,b,使15a+l6b和16a—15b都是正整數(shù)的平方，求這兩個(gè)平方數(shù)中較小的

一個(gè)最小值.

解：(式子化)由已知，可設(shè)

15a+16/?=r2..

r,teN+

16a-15。=產(chǎn)

(求min(min(廠2,t2)))

a-br-t

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

Y

16--15/=48仍②

481=13x37

猜想戶一都是13x37的倍數(shù)

即廠/都是13的倍數(shù)，且都是37的倍數(shù).

先證：廠子是13的倍數(shù)(*)

事實(shí)上，若廠/至少有一個(gè)不是13的倍數(shù)，則由15戶+16r=481。

可知都不是13的倍數(shù)，從而(/,13)=1,。,13)=1

又16r2三15『(mod13)(消元：用費(fèi)馬小定理)

16戶嚴(yán)三15嚴(yán)(mod13)

16/嚴(yán)=15x1

6

((4/)2)6=15

12三l(n?d13)

矛盾

嘟是13的倍數(shù)

若r,t至少有一個(gè)不是37的倍數(shù)，則r4都不是37的倍數(shù)，于是

16r2三15一(mod37)

16戶產(chǎn)三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的倍數(shù)

r,嘟是481的倍數(shù)

戶,戶都是48儼的倍數(shù)

猜想廣的最小值為I8F

證猜想：只需證，存在黃足已知條件的Z,。，使「=4812,事實(shí)上

在①，②中令/=產(chǎn)=48〃得

(15+16)-4812.

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

481

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

481

.?.當(dāng)a=31x4811=481時(shí)，滿足已知條件，并且r=48「，產(chǎn)=48〃

故，所求最小值為4812

高斯函數(shù)

這一講介紹重要的數(shù)論函數(shù)y=[x],稱為高斯函數(shù)，又稱取整函數(shù)。它是數(shù)學(xué)競賽熱

點(diǎn)之一。

定義一：對任意實(shí)數(shù)X,[幻是不超過X的最大整數(shù)，稱[X]為X的整數(shù)部分。與它相伴隨

的是小數(shù)部分函數(shù)y={%},{%}=x-[x].

由[幻、｛%｝的定義不難得到如下性質(zhì)：

(1)y=[x]的定義域?yàn)镽,值域?yàn)閆；y=｛x｝的定義域?yàn)镽,值域?yàn)椤?)

(2)對任意實(shí)數(shù)無，都有x=[x]+｛x｝,且0<｛尤｝<1。

(3)對任意實(shí)數(shù)尤,都有Lx]Kx<[x]+l,x-l<[x]Wx。

(4)y=[x]是不減函數(shù)，即若玉則以』《[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工區(qū)],七e七；特別地，

1=1Z=1

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

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

nn

取整函數(shù)或高斯函數(shù)在初等數(shù)論中的應(yīng)用是基于下面兩個(gè)

結(jié)論。

定理一：xeR+”N*,且1至尤之間的整數(shù)中，有百個(gè)是〃的倍數(shù)。

n

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

nnnnn

倍數(shù)的正整數(shù)只有這區(qū)個(gè)：

n

n,2n,???,[―]?n.

n

定理二：在〃！中，質(zhì)數(shù)p的最高方次數(shù)是

M…力+力+字+????

【證明】由于p是質(zhì)數(shù)，因此〃!含p的方次數(shù)p(〃!)一定是1,2,〃一各數(shù)中所

nn

含p的方次數(shù)的總和。由定理一知，1,2,…，〃中有[―]個(gè)p的倍數(shù)，有[f]個(gè)p2的

pp~

倍數(shù)，…,所以「("!)=[勺+[：]+-?

PP

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

772

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

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

nnn

【證法1】引入輔助函數(shù)

12〃277]]

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

nnnnn

=/(x)對一切尤eH成立，所以/(x)是一個(gè)以,為周期的周期函數(shù)，而當(dāng)時(shí),

nn

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

172—1

【證法2]等式等價(jià)于〃[%]+[{%}]+[{x}+—]+…+[{%}+---]=〃[%]+[幾{%}].消去

nn

過幻后得到與原等式一樣的等式，只不過是對X￡[0,l),則一定存在一個(gè)人使得

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

在這批不等式的右端總有一個(gè)等于1,設(shè)——=1,即:〃—左。這時(shí)，印=［%+與=…二

nn

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

nnn

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

【評述】證法2的方法既適用于證明等式，也適用于證明不等式。，這個(gè)方法是：第一步

“棄整”，把對任意實(shí)數(shù)的問題轉(zhuǎn)化為［0,1)的問題；第二步對［0,1)分段討論。

高斯函數(shù)在格點(diǎn)(又叫整點(diǎn))問題研究中有重要應(yīng)用。下面給出一個(gè)定理。

定理四：設(shè)函數(shù)y=/(x)在切上連續(xù)而且非負(fù)，那么和式⑺］。為以川內(nèi)的

a<t<b

整數(shù))表示平面區(qū)域<瓦0<yK/(x)內(nèi)的格點(diǎn)個(gè)數(shù)。特別地，有

(1)位于三角形：y=ax+b>0,c<x<d內(nèi)的格點(diǎn)個(gè)數(shù)等于￡［。工+加(且％為整數(shù));

c<x<d

(2)(p,q)=l,矩形域內(nèi)的格點(diǎn)數(shù)等于

］冉］

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

(3)r>0,圓域/+F內(nèi)的格點(diǎn)個(gè)數(shù)等于

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

0<x<r/V2

(4)n>0,區(qū)域：％>0,y>0,孫K〃內(nèi)的格點(diǎn)個(gè)數(shù)等于

2Z[-]-fV^]2o

0<x<4n1

格點(diǎn)

［賽點(diǎn)直擊］

L格點(diǎn)，是指方格紙上縱線和橫線的交點(diǎn)，如果取一個(gè)格點(diǎn)為原點(diǎn)，通過該點(diǎn)的橫線

與縱線為X軸和y軸，且設(shè)一個(gè)方格的邊長為1,那么，格點(diǎn)就是平面直角坐標(biāo)系

中宗橫坐標(biāo)都為整數(shù)的點(diǎn)。因此，格點(diǎn)又稱為整點(diǎn)。

2.坐標(biāo)平面內(nèi)頂點(diǎn)為格點(diǎn)的三角形稱為格點(diǎn)三角形，類似地也有格點(diǎn)多邊形的概念。

3.格點(diǎn)多邊形的面積必為整數(shù)或半整數(shù)（奇數(shù)的一半）。

4.格點(diǎn)關(guān)于格點(diǎn)的對稱點(diǎn)為格點(diǎn)。

5.設(shè)格點(diǎn)多邊形內(nèi)部有I個(gè)格點(diǎn)，邊界上有p個(gè)格點(diǎn)，則格點(diǎn)多邊形的面積為

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

2

［賽題精析］

54

例1平面上整點(diǎn)（縱、橫坐標(biāo)都是整數(shù)的點(diǎn)）到直線y=+?的距離中的最小值

35

是（）

思路點(diǎn)撥：可以引進(jìn)整點(diǎn)坐標(biāo)，利用點(diǎn)到直線的距離公式，建立整點(diǎn)到直線距離的二元

函數(shù)。通過對距離函數(shù)最值的探求獲得問題的解。而不同角度的探求又能得到不同的解法。

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

|25%-15%+12|

整點(diǎn)（x,%）到直線的距離為d=

05734

由%，%均可為整數(shù)知|25%—15%+12|必為整數(shù)，從而d為無理數(shù)，否定C,D.

若選A,貝425%-15%+12|=1

即25x0-15y0=±1

有25%0-15%=-13

或25%0-15%=-11

但25%—15治=5（5%—3%）是5的倍數(shù)，不會(huì)取-13,-11。故否定A,從而選B

解法二距離d的大小完全有|25%—15%+1］來確定，當(dāng)125Ao—15%+1［最小時(shí)，d

也相應(yīng)的取最小值。由于25%T5%=5（5%-3%）是5的倍數(shù)，故

|25x0-15y0