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

数学竞赛中的数论问题

定理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|a1?b0?a，ax0?by0|a0?b1?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，则am,bn?1，其中m,n为正整数．

证明 据（6），由?a,b??1可得a,b?1．同样，由a,b?1可得am,bn?1．

mm????????定理7 素数有无穷多个，2是唯一的偶素数． 证明 假设素数只有有限多个，记为p1,p2,若p为素数，则与素数只有 n个p1,p2,若p为合数，则必有pi??p1,p2,,pn，作一个新数 p?p1p2pn?1?1．

,pn矛盾．

,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，再由

a为素数得a?|bc，与abc矛盾．

定义6 对于整数a,b,c，且c?0，若c(a?b)，则称a,b关于模c同余，记作a?b(modc)；若c?|?a?b?，则称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?．

?abn?2?bn?1?．

an?bn??a?b??an?1?an?2b?an?3b2?（2）若a??b，则?a?b?a?2n?1?b2n?1?．

a2n?1?b2n?1??a?b??a2n?2?a2n?3b?a2n?4b2?（3）若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的非负整数，且a1?0．若

定义7 设n为正整数，k为大于2的正整数, a1,a2, n?a1km?1?a2km?2??am?1k?am，则称数a1a2am为n的k进制表示．

定理11 给定整数k?2，对任意的正整数n，都有唯一的k进制表示．如

n?a110m?1?a210m?2?n?a12m?1?a22m?2??am?110?am，0?ai?9,a1?0（10进制） ?am?12?am．0?ai?1,a1?0（２进制）

定理12 （算术基本定理）每个大于1的正整数都可分解为素数的乘积，而且不计因数的顺序时，这种表示是

唯一的

n?p11p2??2pk?k，其中p1?p2??pk为素数，?1,?2,??2,?k为正整数． （分解唯一性） pk?k则n的正约数的个数为

定理13 若正整数n的素数分解式为 n?p11p2d?n???a1?1??a2?1??ak?1?，

pk?k?1?1． ?pk?1p1?1?1?1p2?2?1?1n的一切正约数之和为 S?n????p1?1p2?1证明 对于正整数n?p11p2 m?p11p2由于?i有0,1,2,

??2??2pk?k，它的任意一个正约数可以表示为

pk?k，0??i??i ， ①

,?i共?i?1种取值，据乘法原理得n的约数的个数为d?n???a1?1??a2?1??ak?1?．

3

考虑乘积p10?p11???p1?1??p20?p21??p2?2??p0k?pk1??pk?k，

?展开式的每一项都是n的某一个约数（参见①），反之，n的每一个约数都是展开式的某一项，于是，n的一切约数之和为S?n??p?p?0111??p1?1??p0k?pk?1?pk?1?p1?1?1?1p2?2?1?1???p1?1p2?1pk?k?1?1． ?pk?1注 构造法．

定义8 （高斯函数）对任意实数x，?x?是不超过x的最大整数．亦称?x?为x的整数部分，?x??x??x??1． 定理14 在正整数n!的素因子分解式中，素数p作为因子出现的次数是 ????证明 由于p为素数，故在n!中p的次方数是1,2,?n??n??n???3??2?pp?????p?．

,n各数中p的次方数的总和（注意，若p不为素数，这

句话不成立）．在1,2,?n??n??n??n?,n中，有??个p的倍数；在??个p的倍数的因式中，有?2?个p2的倍数；在?2??p??p??p??p??n?3p个的倍数；…，如此下去，在正整数n!的素因子分解式中，素数p作为因子出3??p?．注 省略号其实是有限项之和．

个p的倍数的因式中，有?2现的次数就为?????n??n??n???3??2??p??p??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,i,p?1?，故有

?k?1??k?Cpkp1pp?1?p?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?p11p2??2?1??1?pk?k，则 ??n??n?1???1??p1??p2???1?1?? …… 此处隐藏：3704字，全部文档内容请下载后查看。喜欢就下载吧 ……