[指导]素数与同余

《[指导]素数与同余》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、1.3素数及算术基木定理知识扫描：1.素数的定义以及一•些基本性质。大于1的整数斤至少有两个不同的正约数：1和斤。如果没有大于1而小于72的约数，则称H是素数。如果〃有大于1而小于〃的约数，即斤可表示为d方的形式，则称斤为合数。(1)大于1的整数必有素因子(2)既为偶数又为素数的正整数只有一个，它就是2.(3)设p为素数，"是任意整数，则或者p幣除〃，或者〃与〃互素。(4)设°是素数，d上是整数，如果p丨ab,则d上中至少有一个被°整除。证明：如果p不整除,则p与Q和b均互素，从而p与db互素，矛盾！(5)素数有

2、无穷多个。用反证法证明这个命题，假设素数只有有限个，设Pi=2，z=3,…，Pk是全部素数,考虑N=PB…Pk+1,显然N>1故N有素因了卩因PM®…以是全部素数，故”必等于某个口(1GS)，从而"/I•这不可能，因此素数冇无穷多个。2.唯一分解定理：每个大于1的正整数均可分解成有限个素数的积。如果不计素因数在乘积屮的次序，则其分解方式是唯一的，即n=,其中门是质数，是正整数，lSiWR。(证明为推理说明性的，可自己来做)3.汕勺约数的标准分解，设n的标准分解为n=p^...则正整数〃是〃的约数的充分必要条件是其

3、标准分解为d=p町“2%…几加0

4、与选取方式相等)(2)d(n)的证明，只需要tEd(n)展开就可发现形如:d=…p｝的数恰恰出现一次，也就是左右两边相等，命题得证。5/为平方数的充耍条件：刃为平方数的充要条件是厂⑺)为奇数证明：因为厂(町=(a]+l)(a2+1)…(a&,+1),则厂(町为奇数等价于a【+l,a2+1…a“+1都是奇数，等价于a],a2…g都是偶数，等价于n为平方数6.素数的一个判別法：设77>1,且斤不被不超过乔的素数整除，则〃是素数。证明：若〃不是索数，贝=ab,a,b都大于1,不妨设aAb贝Ijb

5、,故b有素因了p,又b/斤,从而p/n,但pm时,［予卜0,故上式中的和只有有限多个项不为0补充：下面来求加的标准分解式。若素数p/n!,则可知必有p/k,k为某个正整数Sn;另一方面任一索数P5n必有p/n!・所以，由定理可知n!的标准索因数分解式必为n!二血82••-pk3k(2=

6、a.(1

7、4］.设/是给定的正整数，勺表示1,2,…,肿能被j=iLp」5=勺_勺+伸定理可知c产［了寸.因而dj=-p刃整除的数的个数,J表示1,2,…丿中恰被”的/•次方整除的数的个数，显见，召］.容易看出，当时P_5=(),以及a=ld1+2d2+..-+^dA,.(

8、注：只需将其展开，与原公式比较即可)后者是因为我们可以把1,2,…/分成这样两两不交的k个集合：第j个集合由1,2,…，〃屮恰被刃整除的数组成。这样，第/个集合的所有数的乘积恰被p的j5次方整除，由此可得：a=ld,+2d2+-+kd,2.例题分析例一.(2003年德国数学竞赛)证明：对任意六个连续正整数，存在一个质数，使得这个质数能且只能整除六个数之一。证明:记这六个数为〃，宛+1,•••,/?+5。若n不能被5整除，则n+1至n+4中确只有一个数能被5整除。若n能被5整除，则n+1至n+4中有两个整数不能被2

9、、5整除，其中至少有一个不能被3整除。因此，该数至少冇一个大于5的质因了，H.该质数不能整除另外五个整数。例二•求所冇这样的素数，它既是两素数Z和，同时又是两素数Z差。分析：考虑素数2是索数中唯一的偶数。解：设所求的索数是p,因它是两索数之和，故p〉2・从而卩是奇数，因此和为卩的两个素数屮冇一个为2,同时差为P的两个素数中,减数也是2,即p=q+2,p=r-2,其中q,r