资源预览内容
第1页 / 共9页
第2页 / 共9页
第3页 / 共9页
第4页 / 共9页
第5页 / 共9页
第6页 / 共9页
第7页 / 共9页
第8页 / 共9页
第9页 / 共9页
亲,该文档总共9页全部预览完了,如果喜欢就下载吧!
资源描述
本文格式为Word版,下载可任意编辑数学竞赛中的数论问题题型全 数学竞赛中的数论问题 定理4 a,b是两个不同时为0的整数,若ax0?by0是形如ax?by(x,y是任意整数)的数中的最小正数,那么 (1)ax0?by0|ax?by;(2)ax0?by0?a,b? 证明 (1)由带余除法有ax?by?ax0?by0?q?r,0?r?ax0?by0, 得 r?a?x?qx0?x?b?y?qy0?ax0?by0, 知r也是形如ax?by的非负数,但ax0?by0是形如ax?by的数中的最小正数,故r?0,即ax0?by0|ax?by (2)由(1)有ax0?by0|a?1?b?0?a,ax0?by0|a?0?b?1?b, 得ax0?by0是a,b的公约数另一方面,a,b的每一个公约数都可以整除ax0?by0,所以ax0?by0是a,b的最大公约数,ax0?by0?a,b? 推论 若?a,b?1,那么存在整数s,t,使as?bt?1(很有用) 定理5 互素的简朴性质: (1)?1,a?1(2)?n,n?1?1(3)?2n?1,2n?1?1 (4)若p是一个素数,a是任意一个整数,且a不能被p整除,那么?a,p?1 推论 若p是一个素数,a是任意一个整数,那么?a,p?1或?a,p?p (6)若?a,b?1,?a,c?1,那么?a,bc?1 证明 由?a,b?1知存在整数s,t,使as?bt?1有 a?cs?bct?c,得 ?a,bc?a,c?1 (7)若?a,b?1,那么?a?b,a?1,?a?b,b?1, ?a?b,ab?1 证明 ?a?b,a?b,a?b,a?1,?a?b,b?a,b?1,由(6)?a?b,ab?1 (8)若?a,b?1,那么a,bm?n?1,其中m,n为正整数 ?mmn证明 据(6),由?a,b?1可得a,b?1同样,由a,b?1可得a,b?1 m?定理7 素数有无穷多个,2是唯一的偶素数 ?pn?1?1 证明 假设素数只有有限多个,记为p1,p2,?,pn,作一个新数 p?p1?p2?若p为素数,那么与素数只有 n个p1,p2,?,pn冲突 若p为合数,那么必有pi?p1,p2,?,pn?,使pi|p,从而pi|1,又与pi?1冲突 综上所述,素数不能只有有限多个,所以素数有无穷多个 2是素数,而大于2的偶数都是合数,所以2是唯一的偶素数 1 注:这个证明中,包含着数学归纳法的早期因素:若假设有n个素数,便有n?1个素数(构造法、反证法) 定理8(整除的性质)整数a,b,c通常指非零整数 (1)1a,?1|a;当a?0时,a|a,a|0 (2)若ba,a?0,那么b?a;若ba,b?a,那么a?0;若ab?0,且ba,ab,那么a?b 证明 由ba,a?0,有a?bq,得a?bq?b逆反命题成立“若ba,b?a,那么a?0”; 由b?a且b?a得a?b,又ab?0,得a?b (7)若?a,b?1,且abc,那么ac 证明 由?a,b?1知存在整数s,t,使as?bt?1,有a?cs?bc?t?c, 由于aa,abc,所以a整除等式的左边,进而整除等式的右边,即ac (8)若?a,b?1,且ac,bc,那么abc 证明 由?a,b?1知存在整数s,t,使as?bt?1,有acs?bct?c, 又由ac,bc有c?aq1,c?bq2代入得ab?q2s?ab?q1t?c,所以abc 留神 不能由ac且bc得出abc如不能由630且10|30得出60|30 (9)若a为素数,且abc,那么ab或ac 证明 若不然,那么a?|b且a?|c,由a为素数得?a,b?1,?a,c?1,由互素的性质(6)得?a,bc?1,再由 |bc,与abc冲突 a为素数得a?|?a?b?,定义6 对于整数a,b,c,且c?0,若c(a?b),那么称a,b关于模c同余,记作a?b(modc);若c?那么称a,b关于模c不同余,记作ab(modc) 定理9(同余的性质)设a,b,c,d,m为整数,m?0, 若a?b(modm)且c?d(modm),那么a?c?b?d(modm)且ac?bd(modm) 证明 由a?b(modm)且c?d(modm),有a?b?mq1,c?d?mq2, 对直接相加 ,有?a?c?b?d?m?q1?q2?,得 a?c?b?d(modm). 对分别乘以c,b后相加,有ac?bd?ac?bc?bc?bd?m?cq1?bq2?,得 ac?bd(modm) (3)若a?b(modm),那么对任意的正整数n有a?b(modm)且an?bn(modmn). 2 nn(4)若a?b(modm),且对非零整数k有k(a,b,m),那么 ab?m?mod? kk?k?证明 由a?b(modm)、,有 a?b?mq,又k(a,b,m),有 abm,均为整数,且 kkkab?m?abm?q,得 ?mod? kk?k?kkk定理10 设a,b为整数,n为正整数, (1)若a?b,那么?a?b?a?bn?n? ?b2n?1? an?bn?a?b?an?1?an?2b?an?3b2?abn?2?bn?1? (2)若a?b,那么?a?b?a?2n?1a2n?1?b2n?1?a?b?a2n?2?a2n?3b?a2n?4b2?ab2n?3?b2n?2? (3)若a?b,那么?a?b?a?2n?b2n? a2n?b2n?a?b?a2n?1?a2n?2b?a2n?3b2?ab2n?2?b2n?1? 定义7 设n为正整数,k为大于2的正整数, a1,a2,?,am是小于k的非负整数,且a1?0若 n?a1km?1?a2km?2?am?1k?am,那么称数a1a2?am为n的k进制表示 定理11 给定整数k?2,对任意的正整数n,都有唯一的k进制表示如 n?a110m?1?a210m?2?am?110?am,0?ai?9,a1?0(10进制) n?a12m?1?a22m?2?am?12?am0?ai?1,a1?0(进制) 定理12 (算术根本定理)每个大于1的正整数都可分解为素数的乘积,而且不计因数的依次时,这种表示是 唯一的 n?p11p22?pk?k,其中p1?p2?pk为素数,?1,?2,?,?k为正整数 (分解唯一性) ?k定理13 若正整数n的素数分解式为 n?p11p22?pk那么n的正约数的个数为 d?n?a1?1?a2?1?ak?1?, pk?k?1?1p1?1?1?1p2?2?1?1? n的一切正约数之和为 S?n?p1?1p2?1pk?1证明 对于正整数n?p11p22?pk m?p11p22?pk?k?k,它的任意一个正约数可以表示为 ,0?i?i , 由于?i有0,1,2,?,?i共?i?1种取值,据乘法原理得n的约数的个数为d?n?a1?1?a2?1?ak?1? 3 考虑乘积p1?p1?p1?01?1?p02?p21?p2?2?pk0?pk1?pk?k, ?开展式的每一项都是n的某一个约数(参见),反之,n的每一个约数都是开展式的某一项,于是,n的一切约数之和为S?n?p?p?p10111?1?p0k?pk?pk1?1?pk?k?1?1p1?1?1?1p2?2?1?1? p1?1p2?1pk?1注 构造法 定义8 (高斯函数)对任意实数x,?x?是不超过x的最大整数亦称?x?为x的整数片面,?x?x?x?1 定理14 在正整数n!的素因子分解式中,素数p作为因子展现的次数是 ?n?n?n?p2?p3? p?证明 由于p为素数,故在n!中p的次方数是1,2,?,n各数中p的次方数的总和(留神,若p不为素数,这 句话不成立)在1,2,?,n中,有?n?n?n?n?2个的倍数;在个的倍数的因式中,有个的倍数;在ppp?p2?p2?p?p?个p的倍数的因式中,有?2?n?3p个的倍数;?,如此下去,在正整数n!的素因子分解式中,素数p作为因子出3?p?现的次数就为?n?n?n?p2?p3?注 省略号其实是有限项之和 p?定理15 (费玛小定理)假设素数p不能整除整数a,那么pap?p?1?1? 证明2 改证等价命题:假设素数p不能整除整数a,那么a?a?modp? 只需对a?1,2,?,p?1证明成立,用数学归纳法 (1)a?1,命题鲜明成立 (2)假设命题对a?k?1?k?p?1?成立,那么当a?k?1时,由于p|Cp?i?1,2,?,p?1?,故有 i ?k?1?k?Cpkp1pp?1p?1?Cpk?1 ?kp?1?k?1?modp?(用了归纳假设) 这说明,命题对a?k?1是成立 由数学归纳法得a?a?modp? p又素数p不能整除整数a,有?a,p?1,得pa?p?1?1? 定义9 (欧拉函数)用?n?表示不大于n且与n互素的正整数个数 定理16 设正整数n?p11p22?pk?k,那么 ?n?n?1?1?1?1?1?1? ?p1?p2?pk?推论 对素数p有?p?p?1,?p ?p?p?1 4 其次讲 数论题的范例讲解 (12)?2n?0?mod4?,?2n?1?1?mod4?,?2n?1?1?mod8? (13)任何整数都可以表示为n?2m222?2k?1? b1,b2,?,b7是它们的一个排列,例1-1(1986,英国)设a1,a2,?,a7是整数,证明?a1?b1?a2?b2?a7?b7?是偶数(a1,a2,?,a7中奇数与偶数个数不等) 例1-2 ?的前24位数字为?3.14159265358979323846264,记a1,a2,?,a24为该24个数字的任一排列,求证?a1?a2?a3?a4?a23?a24?必为偶数 (暗藏3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4中奇数与偶数个数不等) 例2 能否从1,2,?,15中选出10个数填入图的圆圈中,使得每两个有线相连的圈中的数相减(大数减小数),所得的14个差恰好为1,2,?,14? 解 考虑14个差的和S,一方面 S?1?2?
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号