数学竞赛中的数论问题题型全.docx

《数学竞赛中的数论问题题型全.docx》由会员分享，可在线阅读，更多相关《数学竞赛中的数论问题题型全.docx（116页珍藏版）》请在三一办公上搜索。

1、数学竞赛中的数论问题题型全 数学竞赛中的数论问题 定理4 a,b是两个不同时为0的整数，若ax0+by0是形如ax+by的数中的最小正数，则 ax0+by0|ax+by；ax0+by0=(a,b) 证明 由带余除法有ax+by=(ax0+by0)q+r，0rax0+by0， 得 r=a(x-qx0)x+b(y-qy0)1 ,pn矛盾 ,pn，使pi|p，从而pi|1，又与pi1矛盾 综上所述，素数不能只有有限多个，所以素数有无穷多个 2是素数，而大于2的偶数都是合数，所以2是唯一的偶素数 1 注：这个证明中，包含着数学归纳法的早期因素：若假设有n个素数，便有n+1个素数 定理8整数a,b,c通

2、常指非零整数 1a，-1|a；当a0时，a|a，a|0 若ba，a0，则ba;若ba，ba，则a=0;若ab0，且ba,ab，则a=b 证明 由ba，a0，有a=bq，得a=bqb逆反命题成立“若ba，ba，则a=0”; 由ba且ba得a=b，又ab0，得a=b 若(a,b)=1，且abc，则ac 证明 由(a,b)=1知存在整数s,t，使as+bt=1，有a(cs)+(bc)t=c， 因为aa，abc，所以a整除等式的左边，进而整除等式的右边，即ac 若(a,b)=1，且ac,bc，则abc 证明 由(a,b)=1知存在整数s,t，使as+bt=1，有acs+bct=c， 又由ac,bc有c

3、=aq1,c=bq2代入得ab(q2s)+ab(q1t)=c，所以abc 注意 不能由ac且bc得出abc如不能由630且10|30得出60|30 若a为素数，且abc，则ab或ac 证明 若不然，则a/|b且a/|c，由a为素数得(a,b)=1,(a,c)=1，由互素的性质得(a,bc)=1，再由a为素数得a/|bc，与abc矛盾 定义6 对于整数a,b,c，且c0，若c(a-b)，则称a,b关于模c同余，记作ab(modc)；若c/|(a-b)，则称a,b关于模c不同余，记作ab(modc) 定理9设a,b,c,d,m为整数，m0, 若ab(modm)且cd(modm)，则a+cb+d(m

4、odm)且acbd(modm) 证明 由ab(modm)且cd(modm)，有a-b=mq1,c-d=mq2， 对直接相加 ，有(a+c)-(b+d)=m(q1+q2)，得 a+cb+d(modm). 对分别乘以c,b后相加，有ac-bd=(ac-bc)-(bc-bd)=m(cq1+bq2)，得 acbd(modm) 若ab(modm)，则对任意的正整数n有a=b(modm)且anbn(modmn). 2 nn若ab(modm)，且对非零整数k有k(a,b,m)，则abm=mod kkk证明 由ab(modm)、，有 a=b+mq，又k(a,b,m)，有abm,均为整数，且 kkkabmabm

5、=+q，得 mod kkkkkk定理10 设a,b为整数，n为正整数， 若ab，则(a-b)a-bn(n) +abn-2+bn-1) an-bn=(a-b)(an-1+an-2b+an-3b2+若a-b，则(a+b)a(2n-1+b2n-1) a2n-1+b2n-1=(a+b)(a2n-2-a2n-3b+a2n-4b2-若a-b，则(a+b)a-ab2n-3+b2n-2) (2n-b2n) a2n-b2n=(a+b)(a2n-1-a2n-2b+a2n-3b2-+ab2n-2-b2n-1) ,am是小于k的非负整数，且a10若 定义7 设n为正整数，k为大于2的正整数, a1,a2, n=a1k

6、m-1+a2km-2+am-1k+am，则称数a1a2am为n的k进制表示 定理11 给定整数k2，对任意的正整数n，都有唯一的k进制表示如 n=a110m-1+a210m-2+n=a12m-1+a22m-2+am-110+am，0ai9,a10 +am-12+am0ai1,a10 定理12 每个大于1的正整数都可分解为素数的乘积，而且不计因数的顺序时，这种表示是唯一的 n=p11p2aa2pkak，其中p1p2pk为素数，a1,a2,aa2,ak为正整数 pkak则n的正约数的个数为定理13 若正整数n的素数分解式为 n=p11p2d(n)=(a1+1)(a2+1)(ak+1)， pkak+

7、1-1 pk-1p1a1+1-1p2a2+1-1n的一切正约数之和为 S(n)=p1-1p2-1证明 对于正整数n=p11p2 m=p11p2由于bi有0,1,2,bb2aa2pkak，它的任意一个正约数可以表示为 pkbk，0biai ， ,ai共ai+1种取值，据乘法原理得n的约数的个数为d(n)=(a1+1)(a2+1)(ak+1) 3 考虑乘积p10+p11+(+p1a1)(p20+p21+p2a2)(p0k+pk1+pkak， )展开式的每一项都是n的某一个约数，反之，n的每一个约数都是展开式的某一项，于是，n的一切约数之和为S(n)=p+p+0111(+p1a1)(p0k+pk+1

8、+pka1)p1a1+1-1p2a2+1-1=p1-1p2-1pkak+1-1 pk-1注 构造法 定义8 对任意实数x，x是不超过x的最大整数亦称x为x的整数部分，xxx+1 定理14 在正整数n!的素因子分解式中，素数p作为因子出现的次数是 +证明 由于p为素数，故在n!中p的次方数是1,2,nnn+3+2ppp ,n各数中p的次方数的总和在1,2,nnnn,n中，有个p的倍数；在个p的倍数的因式中，有2个p2的倍数；在2ppppn3p个的倍数；，如此下去，在正整数n!的素因子分解式中，素数p作为因子出3p注 省略号其实是有限项之和 个p的倍数的因式中，有2现的次数就为+nnn+3+2pp

9、p定理15 如果素数p不能整除整数a，则pap(p-1-1) 证明2 改证等价命题：如果素数p不能整除整数a，则aa(modp) 只需对a=1,2,p-1证明成立，用数学归纳法 a=1，命题显然成立 假设命题对a=k(1k1， 使 (21n+4,14n+3)=d， 21n+4=dp, 从而存在p,q,(p,q)=1，使 14n+3=dq, 消去n，(3)3-(2)2，得 1=d(3q-2p)， 7 的 d=1 由、矛盾，得d=1 解题分析：去掉反证法的假设与矛盾就是一个正面证法 式是实质性的进展，表明 1=3(14n+3)-2(21n+4)， 可见 (21n+4,14n+3)=1由此获得2个解

10、法 证明2 设(21n+4,14n+3)=d存在p,q,(p,q)=1，使 21n+4=dp, 14n+3=dq, 消去n，3-2，得 1=d(3q-2p) 得 d=1 证明3 由1=3(14n+3)-2(21n+4) 得 (21n+4,14n+3)=1 证明4 (21n+4,14n+3) =(7n+1,14n+3) =(7n+1,1) =1 解题分析：第 相当于 -；第 相当于-2=3-2；所以式与式的效果是一样的 例12 不存在这样的多项式 f(n)=amn+am-1nmm-1+a1n+a0， 使得对任意的正整数n，f(n)都是素数 证明 假设存在这样的多项式,对任意的正整数n，f(n)都

11、是素数，则取正整数n=b，有素数p使 f(b)=amb+am-1bmm-1+a1b+a0=p， mm-1进而对任意的整数k,有 f(b+kp)=am(b+kp)+am-1(b+kp)+a1(b+kp)+a0 =(ambm+am-1bm-1+a1b+a0)+Mp=P(1+M)，其中M为整数，这表明f(b+kp)为合数这一矛盾说明，不存在这样的多项式,对任意的正整数n，f(n)都是素数 三、平方数 若a是整数，则a就叫做a的完全平方数，简称平方数 1平方数的简单性质 平方数的个位数只有6个：0,1,4,5.6.9 平方数的末两位数只有22个：00，01，21，41，61，81，04，24，44，6

12、4，84，25，16，36，56，76，8 296，09，29，49，69，89 (2n)0(mod4),(2n-1)1(mod4)(2n-1)1(mod8) 凡是不能被3整除的数，平方后被3除余1在两个相邻整数的平方数之间，不能再有平方数 非零平方数的约数有奇数个 直角三角形的三边均为整数时，我们把满足a+b=c的整数(a,b,c)叫做勾股数勾股数的公式为 222222a=m2-n2, b=2mn, c=m2+n2,其中m,n为正整数，(m,n)=1且m,n一奇一偶这个公式可给出全部素勾股数 2平方数的证明方法 反证法恒等变形法分解法设a为平方数，且a=bc，(b,c)=1，则b,c均为平方

13、数 约数法证明该数有奇数个约数 3非平方数的判别方法 若nx1， 这一矛盾说明，3个连续正整数的积不是平方数 四整除 整除的判别方法主要有7大类 1定义法证baa=bq，有三种方式 假设a=qb+r，然后证明r=0具体找出q，满足a=bq论证q的存在 例18 任意一个正整数m与它的十进制表示中的所有数码之差能被9整除 证明 设m=ann-1n10+an-110+a110+a0，其中0ai9,an0，则 m-(an+an-1+a1+a0) =an-1n(10n-1)+an-1(10-1)+a1(10-1) =9an111-+an-1111+a211+a1n个1n-1个1,按定义 9m-(an+a

14、n-1+a1+a0) 2数的整除判别法 任何整数都能被1整除如果一个整数的末位能被2或整除，那么这个数就能被2或整除 如果一个整数的末两位能被或25整除，那么这个数就能被4或25整除 如果一个整数的末三位能被8或125整除，那么这个数就能被8或125整除 如果一个整数各数位上的数字之和能被3或9整除，那么这个数就能被3或9整除 证明 由101(mod3),101(mod9)，有 an-1n10+an-110n+a110+a0an+an-1+a1+a0(mod3)， 10 an10n+an-110n-1+a110+a0an+an-1+a1+a0(mod9) 如果一个整数的末三位数与末三位数以前的

15、数字所组成的数的差能被7或11或13整除，那么这个数就能被7或11或13整除 证明 由m=anan-1a2a1a0 =anan-1a31001-(anan-1a3-a2a1a0)， 知 1001anan-1a3a2a1a01001(anan-1a3-a2a1a0)， 又由1001=71113，而7,11,13均为素数知，m能被7或11或13整除 如果一个整数的奇位数字之和与偶位数字之和的差能被11整除，则这个数能被11整除 证明 由10-1(mod11)，有an10n+an-110n-1+a110+a0an1n(-1)+an-1(-1)n-+a1(-1)+a0(mod11).3分解法主要用乘法

16、公式如 an-bn=(a-b)(an-1+an-2b+an-3b2+abn-2+bn-1) a2n-1+b2n-1=(a+b)(a2n-2-a2n-3b+a2n-4b2-ab2n-3+b2n-2) a2n-b2n=(a+b)(a2n-1-a2n-2b+a2n-3b2-+ab2n-2-b2n-1) 例19 试证(1+2+9)(15+25+95) 证明 改证45(15+25+95)设S=15+25+95，则 S=(15+85)+(25+75)+(35+65)+(45+55)+95 =(1+8)m1+(2+7)m2+(3+6)m53+(4+5)m4+9 =9(m41+m2+m3+m4+9),得9S又

17、 S=(15+95)+(25+85)+(35+75)+(45+65)+55 =(1+9)m1+(2+8)m2+(3+7)m3+(4+6)m54+5=5(2m4得5S 1+2m2+2m3+2m4+5),但(9,5)=1，得45S，即(1+2+9)(15+25+95) 例20 (1979,IMO21-1)设p与q为正整数，满足 p1q=1-112+3-1318+11319，求证p可被1979整除 证明 pq=1-112+3-111318+13 19 =1+1112+13+1318+1131911-22+4-+131811 11=1+23+1111+-1+-1318131923+1 659=1111

18、 +66066113181319660+1319661+1318989+990 =+66013196611318989990M660661659!M=19791319!=19791319 得1979整除1319!p，但1979为素数，(1979,1319!)=1，得p可被1979整除 例20-1 XX年x月x日的年、月、日组成“长长久久、永不分离”的吉祥数字20090909，而它也恰好是一个不能再分解的素数若规定含素因子20090909的数为吉祥数，请证明最简分数子m是吉祥数 证明：由m1=1+n2+1的分20090908m1=1+n2+120090908111111=+12009090822

19、00909071004545410045455200909092009090920090909 =+1200909082200909071004545410045455p=20090909,122009090720090908其中p为正整数，有 20090909np=122009090720090908m， 这表明，20090909整除12200909072009m0，9但20090909为素数，不能整除，所以1220090907200920090909整除m，得m是吉祥数 4 余数分类法 例21 试证3n(n+1)(2n+1) 证明1 任何整数n被3除其余数分为3类 n=3k,n=3k+1,

20、n=3k+2,kZ， n=3k时，有 n(n+1)(2n+1)=3k(3k+1)(6k+1), 有3n(n+1)(2n+1)n=3k+1时，有n(n+1)(2n+1)=3(3k+1)(3k+2)(2k+1), 有3n(n+1)(2n+1)n=3k+2n(n+1)(2n+1)=3(3k+2)(k+1)(6k+5), 有3n(n+1)(2n+1)综上得，3n(n+1)(2n+1) 2n(2n+2)(2n+1)证明2 n(n+1)(2n+1)=，得 32n(2n+2)(2n+1)，又(3,4)=1，得412 3n(n+1)(2n+1) 5数学归纳法6反证法7构造法 例22 k个连续整数中必有一个能被

21、k整除 证明 设k个连续整数为a,a+1,a+2,a+k-1， ,k-1，共k-1种情况，必存在两个数 若这k个数被k除没有一个余数为0，则这k个数的余数只能取1,2, a+i,a+j,0i-jk ，使 a+i=kq1+r,a+j=kq2+r, 其中q1q2，相减 i-j=k(q1-q2)，有 i-j=kq1-q2k， 即 i-jk与i-jk矛盾故k个连续整数中必有一个能被k整除 也可以由i-j=k(q1-q2)得 0i-j=k(q1-q2)k，推出0q1-q21，与q1-q2为整数矛盾 例23 k个连续整数之积必能被k!整除 证明 设k个连续整数为n,n+1,n+2,若这k个连续整数为正整数

22、，则 ,n+k-1， n(n+1)(n+2)k!(n+k-1)=n!k!(n+k)!(=C) kn只须证明，对任何一个素数p，分子中所含p的方次不低于分母中所含p的方次，由高斯函数的性质x+yx+y，有 knk+(n-k)nkn-k=+pspspsps 得C为整数 若这k个连续整数中有0，则连乘积为0，必能被k!整除 若这k个连续整数为负整数，则 n(n+1)(n+2)(n+k-1)k!k(-n)(-n-1)(-n-2) =(-1)k!=(-1)kk(-n-k+1) Ck-n,n(n+1)(n+2)由知C-n为整数，故k!(n+k-1)为整数 例24 有男孩、女孩共n个围坐在一个圆周上，若顺序

23、相邻的3人中恰有一个男孩的有a组，顺序相邻的3人中恰有一个女孩的有b组，求证3a-b 证明 现将小孩记作ai(i=1,2,n)，且数字化 13 1,ai表示男孩时 ai=-1, ai表示女孩时则“3人组”数值化为 Ai=ai+ai+1+ai+23, ai,ai+1,ai+2均为男孩-3,ai,ai+1,ai+2均为女孩 =1, ai,ai+1,ai+2恰有一个女孩-1,a,a,a恰有一个男孩ii+1i+2其中an+j=aj又设取值为3的Ai有p个，取值为-3的Ai有q个，依题意，取值为1的Ai有b个，取值为-1的a1+a2+an)=a(1+a+)a(+2a+a+4)+an+(a+a1 )Ai有

24、a个，得 3(2a33 =3p+(-3)q+(-1)a+b=3(p-q)+(b-a)， 可见3a-b 例25 证明n+3321n+n-1对任何正整数n都是整数，并且用3除时余2 22n(3n-1)321分析 只需说明n+n=为整数，但不便说明“用3除时余2”，应说明222n(n+1)(2n+1)2n(2n+2)(2n+1)313213n3+n2+n=-1,(3,8)=1 ， 是3的倍数作变形 n+n+n-1=222228命题可证 n(n+1)(2n+1)321-1， 证明 已知即n+n+n-1=2223因为相邻2个整数n,(n+1)必有偶数，所以n+3321n+n-1为整数又可变为 222n(2n+2)(2n+1)31n3+n2+n-1=-1， 228因为相邻3个整数2n,(2n+2),(2n+1)必有3的倍数，故2n(2n+2)(2n+1)能被3整除；又(3,8)=1，所以2n(2n+2)(2n+1)3213能被3整除；得n+n+n-1用3除时余2 822五、同余 根据定义，同余问题可以转化