文档介绍：定义1 设是任意两个整数,其中。如果存在一个整数使得等式成立,就称整除或者被整除,记作,并把叫做的因数,把叫做的倍数。否则,就称不能整除或者不能被整除,记作。
由定义可知,0是任何非零整数的倍数;1是任何整数的因数;任何非零整数既是其自身的因数,又是其自身的倍数。由定义1及乘法运算的性质,立即可以得到整除关系具有下面性质
性质1 (ⅰ);
(ⅱ);
(ⅲ);
(ⅳ);
(ⅴ)设,则;
(ⅵ)若,则。
(ⅶ)若,且是的全体因数,则也是的全体因数。
例1 证明:若,,那么。;
例2 设是两个非零整数,且存在整数,使得。证明
(1)若,则有;
(2)若,则有。
例3 设为奇数,为偶数,且,则。
定义2 设整数。如果除了因数和外,没有其他因数,则称为素数(或质数)。否则称其为合数。
首先给出素数的一个判定定理。
定理1 设是一个大于1的正整数,如果对所有小于或等于的素数,都有,则一定是素数。
由定理1,对于比较小的整数,我们可以迅速的判断出它是否为素数。
例4 求出所有不超过100的素数。
(1) ;
(2) 如果,则不是素数,转到(7);
(3) 如果,则不是素数,转到(7);
(4) 如果,则不是素数,转到(7);
(5) 如果,则不是素数,转到(7);
(6) 输出的值;
(7)
(8) 如果,程序结束;
(9) 否则返回到(2)。
输出的结果为
2 3 5 7
11 13 17 19
23 29
31 37
41 43 47
53 59
61 67
71 73 79
83 89
91 97
从例4我们可以看出100以内的素数分布情况,进一步可以由上述例题求出以内的素数,这种求素数的方法称为爱拉托斯散(Eratosthenes)筛法。随着的增加,按照上述方法判断出是否为素数的时间复杂度为。
由定理1可以看出每个整数都有一个素因数,下面我们要证明每个整数一定可以表示成素数的乘积。
定理2 任一整数都可以表示成素数的乘积,即
, (1)
其中是素数。
定理3 素数有无穷多个。
定理4 形如素数有无穷多个。
上述两个定理都说明了一件事情:素数有无穷多个。若以表示不超过实数的素数个数,记为第个素数,我们很容易得到的一个很弱的下界估计和的一个很弱的上界估计。
定理5 设全体素数按大小顺序排成的序列是:
我们有
, (2)
和
(3)
进一步运用简单的微积分知识我们可以得到更强一些的Chebyshev不等式估计。
定理6 设实数。我们有
,
事实上,还可以得到如下的极限形式
,
,
这个结论也被称为素数定理。由素数定理可知,当很大时,,。
素数的分布
168

1229

9592

78498

664579

5761455

50847534

455052512

应用素数定理,我们可以分别估算出64