数学竞赛中的数论问题(3)

abm??q， kkk得

ab?m???mod?． kk?k?定理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?am．0?ai?1,a1?0（２进制）

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

数的顺序时，这种表示是唯一的

n?p11p22?pk???k，

其中p1?p2???pk为素数，?1,?2,?,?k为正整数． （分解唯一性） 证明1 先证明，正整数n可分解为素数的乘积

n?p1p2?pm． ①

如果大于1的正整数n为素数，命题已成立．

当正整数n为合数时，n的正约数中必有一个最小的，记为p1，则p1为素数，有

11

n?p1a1，1?a1?n．

如果a1为素数，命题已成立．当a1为合数时，a1的最小正约数p2为必为素数，有

n?p1a1?p1p2a2，1?a2?a1?n．

这个过程继续进行下去，由于n为有限数，而每进行一步ai就要变小一次，于是，经过有限次后，比如m次，n就变为素数的乘积

n?p1p2?pm．

下面证明分解式是唯一的．假设n还有另一个分解式

n?q1q2?qt， ② 则有 p1p2?pm?q1q2?qt． ③

因为等式的右边能被q1整除，所以左边也能被q1整除，于是q1整除p1,p2,?,pm中的某一个pi，但pi为素数，所以pi与q1相等，不妨设pi为p1，有

p1?q1．

把等式③两边约去p1?q1，得 p2p3?pm?q2q3?qt．

再重复上述步骤，又可得p2?q2，p3?q3，?，直到等式某一边的因数被全部约完，这时，如果另一边的因数没有约完，比如右边没有被约完（m?t），则有

1?qm?1qm?2?qt． ④

但qm?1,qm?2,?,qt均为素数，素数都大于1，有qm?1qm?2?qt?1，这表明等式④不可能成立，两个分解式的因数必然被同时约完，即分解式是唯一的． 将分解式按pi的递增排列，并将相同的pi合并成指数形式，即得

n?p1?1p2?2?pk?k．

其中p1?p2???pk为素数，?1,?2,?,?k为正整数． 证明2 用第二数学归纳法证明

n?p1p2?pm，p1?p2???pm．

（1）当n?2，因为2为素数，命题成立．

12

（2）假设命题对一切大于1而小于n的正整数已成立． 这时，若n为素数，命题成立；若n不为素数，必存在a,b，使 n?ab，1?a?n,1?b?n， 由归纳假设，小于n的a,b可分解为素数的乘积

//a?p1/p2?ps/, p1/?p2???ps/,

b?p/s?1/p//s?2?p, p////t/s?1?p//s?2???p,/t

得 n?p1p2?psqs?1qs?2?qt，

适当调整pi的顺序，可得命题对于正整数n成立．

由数学归纳法，命题对一切大于1的正整数n成立．

下面证明分解式是唯一的．假设n的分解式不唯一，则至少有两个分解式

/n?p1p2?pm，p1?p2???pm，

n?q1q2?qt，q1?q2???qt， 得 p1p2?pm?q1q2?qt． 有 p1|q1q2?qt且q1|p1p2?pm， 这就存在qi,pj，使

p1|qi且q1|pj，

但p1,qi,q1,pj均为为素数，所以

p1?qi,q1?pj，

又 p1?qi?q1?pj?p1， 所以 p1?q1．

把等式两边约去p1?q1，得 p2p3?pm?q2q3?qt．

再重复上述步骤，又可得p2?q2，p3?q3，?，直到等式某一边的因数被全部约完，这时，如果另一边的因数没有约完，比如右边没有被约完（m?t），则有

1?qm?1qm?2?qt．

13

但qm?1,qm?2,?,qt均为素数，素数都大于1，有qm?1qm?2?qt?1，这表明上述等式不可能成立，两个分解式的因数必然被同时约完，即分解式是唯一的． 将分解式按pi的递增排列，并将相同的pi合并成指数形式，即得

n?p1?1p2?2?pk?k．

其中p1?p2???pk为素数，?1,?2,?,?k为正整数． 定理13 若正整数n的素数分解式为 n?p11p22?pk???k则n的正约数的个数为

d?n???a1?1??a2?1???ak?1?，

n的一切正约数之和为

pk?k?1?1p1?1?1?1p2?2?1?1???? 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?．

考虑乘积

p1?p1???p1?01?1??p02?p21???p2?2??pk0?pk1???pk?k， ??展开式的每一项都是n的某一个约数（参见①），反之，n的每一个约数都是展开式

的某一项，于是，n的一切约数之和为

S?n???p10?p11???p1?1???pk0?pk1???pk?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???2???3???． ??p??p??p?14

证明 由于p为素数，故在n!中p的次方数是1,2,?,n各数中p的次方数的总和（注意，若p不为素数，这句话不成立）．

在1,2,?,n中，有??n??n??n?2个的倍数；在个的倍数的因式中，有个p的pp????2??p??p??p?倍数；在??n??n?23个的倍数的因式中，有个p的倍数；?，如此下去，在正整数n!p?2?3??p??p?的素因子分解式中，素数p作为因子出现的次数就为

??n??n??n????p2???p3???． p??????注 省略号其实是有限项之和．

画线示意50!中2的指数．

50!?2?13?25?37?411?513?617?719?823?929?31?37?41?43?47

定理15 （费玛小定理）如果素数p不能整除整数a，则pa证明1 考察下面的p?1个等式： a?pq1?r1，0?r1?p，

?p?1?1?．

2a?pq2?r2，0?r2?p

??

?p?1?a?pqp?1?rp?1，0?rp?1?p

由于素数p不能整除整数a，所以，p不能整除每个等式的左边，得r1,r2,?,rp?1均不为0，只能取1,2,?,p?1．下面证明r1,r2,?,rp?1各不相等．

若不然，存在t,s,1?t?s?p?1，使

sa?pqs?rs, ta?pqt?rt,

rs?rt,相减 ?s?t?a?p?qs?qt?．

应有素数p整除?s?t?a，但素数p不能整除a，所以素数p整除?s?t?，然而由

1?t?s?p?1可得

15

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数学竞赛中的数论问题(3)在线全文阅读。