《数学竞赛中的数论问题题型全》由会员分享，可在线阅读，更多相关《数学竞赛中的数论问题题型全（9页珍藏版）》请在金锄头文库上搜索。
1、本文格式为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?by
2、0|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?b
3、t?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为合数
4、，那么必有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
5、?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
6、，由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
7、?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?b
8、n?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，都有唯一
9、的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的一切正约数之和为
10、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?1p
11、k?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?p
12、3?注 省略号其实是有限项之和 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?
13、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?
