清北学堂2012年暑假数学高端班(精品班、特训一)数论导学

1、北京淸北学堂教ff科技冇限公诃 电话010-88400903 网址：数论导学同余问题与高斯函数知识点：一、同余问题1. 定义定义： 设加是大于1的正整数，a,方是整数，如果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分别用也除,余数相同。2. 性质定理1设昂b, c, mg 1)是整数，则有(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)二、高斯函数1. 定义设xwRJx表示不超过x的最大整数,则y = x称为高斯函数。函数y = x 的定义域为R,值域为Z。xgR由定义知，x<x,故x-x>0.称x为整数部分，称x-x为x的小数 部分，记作*例如，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对任意整数/7和任意实数x,有性质8-x =一 x,一 X -1,XG Z, xg Z3北京淸北学堂教ff科技冇限公诃 电话010-88400903 网址：#北京淸北学堂教ff科技冇限公诃 电话010-88400903 网址：www.topschool.o

6、rg性质9 X为正实数,77为正整数,则不超过*的所有正实数中,是刀的倍数的数共有个.#北京淸北学堂教ff科技冇限公诃 电话010-88400903 网址：#北京淸北学堂教ff科技冇限公诃 电话010-88400903 网址：性质10 <£n的质因数分解中，质数P的指数是#北京淸北学堂教ff科技冇限公诃 电话010-88400903 网址：#北京淸北学堂教ff科技冇限公诃 电话：010-8840

7、0806网址：模拟真题题1：求使1为7的倍数的所有lE够数77.分析： 易知23-1 = 7,即7|2S-1,从而知二3为所求的最小正整数。经验证 尸4, 5不满足条件，当6时，满足题所要求的条件，丁是猜测，满足条件的刀 是3的倍数，下面证明这个猜测是正确的。解析： 72=3/7?时，有 2 三 l(mod 7),故 23m = l(mod 7),即2张 _ 1 三 0(mod 7),所以，当力二3加时，2一1是7的倍数。(2) 当72=3卅1时，23m+1 三 23叭2 三12 三 2(mod7),即2311曲一1 三 2-1 三

8、 l(mod7),所以，当於3卅1时，21不是7的倍数。(3) 当/?二3"2 时，23m+2 三 2加.2?三 1 4 三 4(mod 7),即23m+1 一1 三 4一1 三 3(mod7),5北京淸北学堂教ff科技冇限公诃 电话010-88400903 网址：所以，当77二3亦2时，2n-l不是7的倍数。 因此，满足条件的门是所冇3的倍数的正幣数。2：设三角形的三边长分别是整数l,m,n ,且1 >m>m已知,其中x= x-x,解三 3" (mod 24),而*表示不超过*的域大整数，求这种三角

9、形周长的最小值。9 所以 3、三 3"三 3"(mod 10°), J-是31 =3w=3n(mod54),由于(3, 2) = (3, 5)=1,由可知,31_n = 3m_n = l(mod 24).现在设u是满足3U三l(iiiod 2°)的最小|-：榕数，则对任总的满足3V三l(mod24) 的正整数“有Vo事实上，若y不能被u榕除，则由带余除法可知，在非负整数日和方使得 v= au + b ,其中0 vbSu-l,从而可推得，3匕三 3b 三 三 l(mod24),显然，这与u的定义矛盾，所以川匕经计算可得,34l(mod24),从而可设m-n

10、 = 4k,其中k为正整数。同理,由推tg3m-nHl(mod54),故34kHl(mod54).现在求满足34k = l(mod 5°)的iE整数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为正幣数.于是故同理可证 由于k = 5t = 125s, s为正整数. m-n = 500s, s为正整数. l-n = 500r , /为正整数.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的十进位数的数字和是A, A的数字和是B, B的数字和是多少？ 解析：设B的数字和是C,显然，44444444 <10000 4444,所以4444纵的的位数不超过 4444 x 4 + 1 <20000.因为每一个数字都不大于9,所以，A<9x20000= 180000: 1999S,而 199999的数字和总比小丁 199999的数的数字和大。则A的数字和B <46。丁是，B的数字和CW12,这是因为12是小丁 46的正整数中最大的数

13、字和 (39的数字和是12)。由于一个正整数与其数字和关于模9同余，于是44444444 三 A三 B 三 C(mod 9)4,所以C 三 4444 4444 三(-Z)4444 三 2 (2?严】= 2.(-l)14Sl = -2 = 7(mod9).因为在CW12的正幣数中，只有7木身才能与7模9同余。所以C=7,这就 是说B的数字和是7。评注 本题首先对4444祕和A, B, C关于模9的余数估计，然后利用 44444444HC(mod9)计算C的值，即采取了 “先估后算”的解题方法。题4： x为实数，为正整数，求证：x 2xnxnx > + b + + -12ii证明：用数学归纳

14、法來证。显然对77=1有X>X成立。设4十+列+凹；、2kA Sx，A <2x,，A_1 <(n-l)x.下面來证明Asi】x.由叭-叭-1 =网，(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. 一次不定方程整系数方程ax+b尸c (a>0, bHO)通常称为二元一次不定方程。 対于二元一次不定方程，己经解决是否有解及如何求解的问题。定理1二元一次不定方程axb尸c (a, b, cW乙 a>0,方H0)有整数解的充分必耍条件是(3, 6) |c。显然，若d) =1,方程有解。定理2若乂，是的一组解(通常称为的一组特解)，则方程的全部解 (通常称为通解)为bx= % +1(:b)teZoy=Yo_(b

16、)t特别地，若(a，b) =1,则方程的通解为9北京淸北学堂教ff科技冇限公诃 电话010-88400903 网址：X=Xo+btteZoly=yo - at定理3 k元一次不定方程3Xi + a2x2 + +=c （c,al e Z、i =1,2,， 工 0）有整数解的充分必要条件是（ai,a2, - ,ak）|Ce2. 一次不定方程组一次不定方程组主耍手段是通过消元的方法來求解。3. 勾股数对于不定方程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的任意整数。4 沛尔方程形如x2 dy2 = 1或 x，- dy2 = 1的二元二次不定方程称为佩尔方程。其中丘2,的0且非平方数。定义 设正整数£和¥1是方程的所有正整数解中使X】+巫力最小的一组解，称a，yj是方程或的基本解。定理5设（x】,yj是方程或的棊本解，则对丁或的任意一组止整数

18、解（X，y）,必有定理6方程有无穷多组正整数解，且全部正榕数解由下式给出：lxn=|(x1+Vdy1r+(x1-Vdy1r,= 3务(X1 + 巫)11 _(X】-。其中(“)是的基本解,n=b 2,。公式也可写成 +=( + yx Vd)n .由公式可以推导出X，几满足线性递推关系:= 2冷忑-“，%厂 2X】-y“定理7方程有无穷多组正整数解，且全部正整数解由下式给出: 卜=扌(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：不存在整数x, y使方程x2 +3xy-2y =122成立(第14届美国数学邀请赛题)。 证明：如果有格数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 中的某个数,但是这时(2a+3y) 2+5=

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

21、是佩尔方程,易知财4,人=1是其基本解,全部正整数解为(n = l,2< -)2叫+1 = 1(9 + 極广+ (9- 俪)彳 2kn = =|(9+)n+(9-0)n所以原方程有无穷多组整数解。 题3：试求所有的正整数m使方程X3 + y3 + z3 = iix2y2z2有止整数解。解析：设x,y,z是其正整数解，由对称性,不妨设显然有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 网址：#北京淸北学堂教ff科技冇限公诃 电