清北學堂2012年暑假數(shù)學高端班(精品班、特訓一)數(shù)論導學

1、北京淸北學堂教ff科技冇限公訶 電話010-88400903 網(wǎng)址：數(shù)論導學同余問題與高斯函數(shù)知識點：一、同余問題1. 定義定義： 設加是大于1的正整數(shù)，a,方是整數(shù)，如果m |a-b,則稱a,方關于 模皿同余，記作a h b(niod m),讀作a同余b模m。當m a - b ,則稱a, b關于 模m不同余，記作a學b(mod m)。顯然，有如下事實：(1) 若 a = 0(moclm),則 in | a .(2) a三b(modm)U>a,b分別用也除,余數(shù)相同。2. 性質定理1設昂b, c, mg 1)是整數(shù)，則有(1)

2、 反身性:a = a (mod ni)；(2) 對稱性：若 a 三 b(mod in),則 b 三 a (mod in):(3) 傳遞性:若 a 三 b , b = c(mod m),則 a 三 c(mod ni).定理 2 設 a】三 0 (lnoclm), a?三 g (lnodm),則(1) .± a2 =±b2(niodni)(2) a-, = 0Q(modm)推論 1 若 =l(modm),k = l,2,-,n,則 三bjmodmk = h2,nnn仃)工心三工bk(modm),k=lk=l(2) fpk 三 flA (1110d 1U) k=lk=l推論 2?

3、'f a = b(mod m),則 an 三 bn(niodm).定理 3 若吋?三 bb->(niodii0，a2 三 b2(niodm), II. (a2,m) = 1,則 a】三耳(mod in).推論 若 a c 三 bc(moci m),且(m, c) = 1,則a = b(mod m).注 條件(m,c) = 1是不可缺少的，當(m,c)=l時，此性質不成立。例如2 X 4=4X6(mod 12),但24(modl2).定理 4 若a =b(modm),且(a,b) = d,d|m,則a bf mA=mod.dd)定理 5 若 a = b(modnij),a = b(

4、modm2), a = b(mod 叫),且 M = n y m2,mJ,則a 三 b(modM)二、高斯函數(shù)1. 定義設xwRJx表示不超過x的最大整數(shù),則y = x稱為高斯函數(shù)。函數(shù)y = x 的定義域為R,值域為Z。xgR由定義知，x<x,故x-x>0.稱x為整數(shù)部分，稱x-x為x的小數(shù) 部分，記作*例如，3.2 = 3,3.2 = 0.2;2.3 = -3,-2.3 = 0.7.2. 性質刃的應用范圍很廣，很多競賽題都耍應用刃的性質。性質1對任意xwR,都有x=x + x,且0<x<1.性質 2 對任 SxgR,都有 x-l<x<x<x + l

5、性質3對任意齊電丘只，且 <x,:有x;<Xj性質4 對任MneZ和xwR,都有n+x = n + x性質 5 對任意的x,ywR,都有x+y5x+y,x + y2x+y.性質 6 若 x",yno, WiJxy>xy.性質7對任意整數(shù)/7和任意實數(shù)x,有性質8-x =一 x,一 X -1,XG Z, xg Z3北京淸北學堂教ff科技冇限公訶 電話010-88400903 網(wǎng)址：#北京淸北學堂教ff科技冇限公訶 電話010-88400903 網(wǎng)址：www.topschool.o

6、rg性質9 X為正實數(shù),77為正整數(shù),則不超過*的所有正實數(shù)中,是刀的倍數(shù)的數(shù)共有個.#北京淸北學堂教ff科技冇限公訶 電話010-88400903 網(wǎng)址：#北京淸北學堂教ff科技冇限公訶 電話010-88400903 網(wǎng)址：性質10 <£n的質因數(shù)分解中，質數(shù)P的指數(shù)是#北京淸北學堂教ff科技冇限公訶 電話010-88400903 網(wǎng)址：#北京淸北學堂教ff科技冇限公訶 電話：010-8840

7、0806網(wǎng)址：模擬真題題1：求使1為7的倍數(shù)的所有l(wèi)E夠數(shù)77.分析： 易知23-1 = 7,即7|2S-1,從而知二3為所求的最小正整數(shù)。經(jīng)驗證 尸4, 5不滿足條件，當6時，滿足題所要求的條件，丁是猜測，滿足條件的刀 是3的倍數(shù)，下面證明這個猜測是正確的。解析： 72=3/7?時，有 2 三 l(mod 7),故 23m = l(mod 7),即2張 _ 1 三 0(mod 7),所以，當力二3加時，2一1是7的倍數(shù)。(2) 當72=3卅1時，23m+1 三 23叭2 三12 三 2(mod7),即2311曲一1 三 2-1 三

8、 l(mod7),所以，當於3卅1時，21不是7的倍數(shù)。(3) 當/?二3"2 時，23m+2 三 2加.2?三 1 4 三 4(mod 7),即23m+1 一1 三 4一1 三 3(mod7),5北京淸北學堂教ff科技冇限公訶 電話010-88400903 網(wǎng)址：所以，當77二3亦2時，2n-l不是7的倍數(shù)。 因此，滿足條件的門是所冇3的倍數(shù)的正幣數(shù)。2：設三角形的三邊長分別是整數(shù)l,m,n ,且1 >m>m已知,其中x= x-x,解三 3" (mod 24),而*表示不超過*的域大整數(shù)，求這種三角

9、形周長的最小值。9 所以 3、三 3"三 3"(mod 10°), J-是31 =3w=3n(mod54),由于(3, 2) = (3, 5)=1,由可知,31_n = 3m_n = l(mod 24).現(xiàn)在設u是滿足3U三l(iiiod 2°)的最小|-：榕數(shù)，則對任總的滿足3V三l(mod24) 的正整數(shù)“有Vo事實上，若y不能被u榕除，則由帶余除法可知，在非負整數(shù)日和方使得 v= au + b ,其中0 vbSu-l,從而可推得，3匕三 3b 三 三 l(mod24),顯然，這與u的定義矛盾，所以川匕經(jīng)計算可得,34l(mod24),從而可設m-n

10、 = 4k,其中k為正整數(shù)。同理,由推tg3m-nHl(mod54),故34kHl(mod54).現(xiàn)在求滿足34k = l(mod 5°)的iE整數(shù)k.因為 34 =5x24 +1 ,所以 34k -1 = (5 x 24 +l)k -1 = 0(mod 54),riMk(k l)(k 2)3 p k(k 1) o $十即 x5J X21- + x5- x2b +5kx26 2三 k(k - l)(k - 2) % §3 % 211 + 52k(k-l)x27+3+5k=0(niod 5°),或 k(k_l)(k_2) %52 %2" + 5k(k-l)

11、x27 +3+kn 0(mod53), 即有k = 5t,并代入該式得5t(5t -l)x 27 4-3+t = 0(mod52)t = 0(mod52).由此可得 t = 0(mod52),即t = 25s,其中s為正幣數(shù).于是故同理可證 由于k = 5t = 125s, s為正整數(shù). m-n = 500s, s為正整數(shù). l-n = 500r , /為正整數(shù).1 > m > n » 所以 r > s.這樣，三角形的三邊為500r + iH00s + MlhL由丁兩邊Z差小丁第三邊，故 a >500(r - s),因此,當s = l,r = 2,n = 50

12、1時三角形的周長最小。其值為(1000 + 501) + (500 + 501) + 501 = 3003.題3： 4444 4444的十進位數(shù)的數(shù)字和是A, A的數(shù)字和是B, B的數(shù)字和是多少？ 解析：設B的數(shù)字和是C,顯然，44444444 <10000 4444,所以4444縱的的位數(shù)不超過 4444 x 4 + 1 <20000.因為每一個數(shù)字都不大于9,所以，A<9x20000= 180000: 1999S,而 199999的數(shù)字和總比小丁 199999的數(shù)的數(shù)字和大。則A的數(shù)字和B <46。丁是，B的數(shù)字和CW12,這是因為12是小丁 46的正整數(shù)中最大的數(shù)

13、字和 (39的數(shù)字和是12)。由于一個正整數(shù)與其數(shù)字和關于模9同余，于是44444444 三 A三 B 三 C(mod 9)4,所以C 三 4444 4444 三(-Z)4444 三 2 (2?嚴】= 2.(-l)14Sl = -2 = 7(mod9).因為在CW12的正幣數(shù)中，只有7木身才能與7模9同余。所以C=7,這就 是說B的數(shù)字和是7。評注 本題首先對4444祕和A, B, C關于模9的余數(shù)估計，然后利用 44444444HC(mod9)計算C的值，即采取了 “先估后算”的解題方法。題4： x為實數(shù)，為正整數(shù)，求證：x 2xnxnx > + b + + -12ii證明：用數(shù)學歸納

14、法來證。顯然對77=1有X>X成立。設4十+列+凹；、2kA Sx，A <2x,，A_1 <(n-l)x.下面來證明Asi】x.由叭-叭-1 =網(wǎng)，(n -1)A-i -(n - !)A-2 = (n - l)x，2A-2A =2x,A = x,知，這門個等式的和為nA - (A + A + + A-】)=x+2x + +nx,則11A =x+2xnx +A+A T由門納假設知nA <x +2x + +iix+x+2x + +(n -l)x=x + (n -l)x + 2x + (n - 2)x + + (n -l)x + x + nx,由性質4知nA < x+(

15、n - l)x+2 + (n - 2)x卜(n- l)x + x+nx=nx + nx + + nx + nx = nnx,故有 At <nx.二、不定方程知識點：1. 一次不定方程整系數(shù)方程ax+b尸c (a>0, bHO)通常稱為二元一次不定方程。 対于二元一次不定方程，己經(jīng)解決是否有解及如何求解的問題。定理1二元一次不定方程axb尸c (a, b, cW乙 a>0,方H0)有整數(shù)解的充分必耍條件是(3, 6) |c。顯然，若d) =1,方程有解。定理2若乂，是的一組解(通常稱為的一組特解)，則方程的全部解 (通常稱為通解)為bx= % +1(:b)teZoy=Yo_(b

16、)t特別地，若(a，b) =1,則方程的通解為9北京淸北學堂教ff科技冇限公訶 電話010-88400903 網(wǎng)址：X=Xo+btteZoly=yo - at定理3 k元一次不定方程3Xi + a2x2 + +=c （c,al e Z、i =1,2,， 工 0）有整數(shù)解的充分必要條件是（ai,a2, - ,ak）|Ce2. 一次不定方程組一次不定方程組主耍手段是通過消元的方法來求解。3. 勾股數(shù)對于不定方程x2+y2=z2如果（X, y）二d,則右"即這樣方程兩邊可約去d。所以在討論 的解時,僅需在（x, y） =1時討論

17、。此時X, y, Z是兩兩互素的。這樣兩兩互 素的解（x, y, z）稱為方程的本原解。定理4不定方程滿足（x, y） =1, x>0, y>0, z>0, 2|y的全部解可表示成 y= 2ab其中a, b是滿足a>b>0, a, 0奇一偶，且（a,方）二1的任意整數(shù)。4 沛爾方程形如x2 dy2 = 1或 x，- dy2 = 1的二元二次不定方程稱為佩爾方程。其中丘2,的0且非平方數(shù)。定義 設正整數(shù)£和¥1是方程的所有正整數(shù)解中使X】+巫力最小的一組解，稱a，yj是方程或的基本解。定理5設（x】,yj是方程或的棊本解，則對丁或的任意一組止整數(shù)

18、解（X，y）,必有定理6方程有無窮多組正整數(shù)解，且全部正榕數(shù)解由下式給出：lxn=|(x1+Vdy1r+(x1-Vdy1r,= 3務(X1 + 巫)11 _(X】-。其中(“)是的基本解,n=b 2,。公式也可寫成 +=( + yx Vd)n .由公式可以推導出X，幾滿足線性遞推關系:= 2冷忑-“，%廠 2X】-y“定理7方程有無窮多組正整數(shù)解，且全部正整數(shù)解由下式給出: 卜=扌(X + 施比嚴 1 + * - V?Yi)2n+1 jyn =(X1 + 逅Y1)211*1 - (Xj - VdYi)2n+1. o其中(x】,yj是的基本解，/7=1, 2,。公式也可寫成 £ + y

19、n Vd = ±(Xj 4-YiVd)2x1+1模擬真題1：不存在整數(shù)x, y使方程x2 +3xy-2y =122成立(第14屆美國數(shù)學邀請賽題)。 證明：如果有格數(shù)x, y使方程成立，則17x29 5 = 488 = 4x2 +12xy-8y2 = (2x + 3y)2 -17y2,知(2a+37)祁5能被17整除。設 2a+3y=17z?+-a» 其中 a 是 0, ± 1» ±2> ±3, ±4, ±5, ±6, ±7, ±8 中的某個數(shù),但是這時(2a+3y) 2+5=

20、(17n) 2+34na+ (£+5) =a2+5 (modi：),而 £+5被17整除得的余數(shù)分別是5, 6, 9, 14, 4, 13, 7, 3, 1,即在任何情況 下(2a+37)牛5都不能被17整除,這與它能被17整除矛盾。故不存在整數(shù)x, y使成立。2：證明不定方程x3+y3+z3+t3=1999有無窮多組整數(shù)解。證明：注意到 W+10,+(-1)3+()3=1999,因此，方程冇幣數(shù)解。由上可知，我們可尋找如下形式的籟數(shù)解: x=Q-k,尸 10+女，z=T-加，t=m, (A,加WZ)。代入方程并化簡得加”1)二20”，即有(2m+1)2 -80k2 =1這

21、是佩爾方程,易知財4,人=1是其基本解,全部正整數(shù)解為(n = l,2< -)2叫+1 = 1(9 + 極廣+ (9- 儷)彳 2kn = =|(9+)n+(9-0)n所以原方程有無窮多組整數(shù)解。 題3：試求所有的正整數(shù)m使方程X3 + y3 + z3 = iix2y2z2有止整數(shù)解。解析：設x,y,z是其正整數(shù)解，由對稱性,不妨設顯然有z21 (x3 + /),故z2 <x3 + y3,但x3 <xz2, y3 <yz2» KP x3 + y1 <z2(x+ y) o乂 z=iix2y2 - X ,y >iix2y2 _(x+ y),x3 + y3 >z2 >(in2y2 - x- y)2 >n2x4y4 -2iix2y2(x+ y) 丁是 n2x4y4 <2iix2y2(x+y) + x3 + y3 ,13北京淸北學堂教ff科技冇限公訶 電話010-88400903 網(wǎng)址：#北京淸北學堂教ff科技冇限公訶 電