信息数学课件--讲义VIP免费

定义1设ba,是任意两个整数，其中0b。如果存在一个整数q使得等式bqa成立，就称b整除a或者a被b整除，记作ab|，并把b叫做a的因数，把a叫做b的倍数。否则，就称b不能整除a或者a不能被b整除，记作ab|。由定义可知，0是任何非零整数的倍数；1是任何整数的因数；任何非零整数既是其自身的因数，又是其自身的倍数。由定义1及乘法运算的性质，立即可以得到整除关系具有下面性质性质1（ⅰ）||||||||babababa；（ⅱ）acabbc||,|且；（ⅲ）byaxctsbcac|,|,|有对任意的整数且；（ⅳ）babaab||且；（ⅴ）设0c，则acbcab||；（ⅵ）若0a，则|||||abab。（ⅶ）若0b，且},,,{21kddd是b的全体因数，则}/,,/,/{21kdbdbdb也是b的全体因数。例1证明：若n|3，n|5，那么n|15。；例2设ba,是两个非零整数，且存在整数ts,，使得1tbsa。证明（1）若bmam|,|，则有1m；（2）若nbna|,|，则有nab|。例3设a为奇数，b为偶数，且ba|，则2|ba。定义2设整数1,0n。如果除了因数1和n外，n没有其他因数，则称n为素数（或质数）。否则称其为合数。首先给出素数的一个判定定理。定理1设n是一个大于1的正整数，如果对所有小于或等于n的素数p，都有np|，则n一定是素数。由定理1，对于比较小的整数，我们可以迅速的判断出它是否为素数。例4求出所有不超过100的素数。算法1.1.1（1）2i;（2）如果i|2，则i不是素数，转到（7）；（3）如果i|3，则i不是素数，转到（7）；（4）如果i|5，则i不是素数，转到（7）；（5）如果i|7，则i不是素数，转到（7）；（6）输出i的值；（7）1ii（8）如果100i，程序结束；（9）否则返回到（2）。输出的结果为235711131719232931374143475359616771737983899197从例4我们可以看出100以内的素数分布情况，进一步可以由上述例题求出10000n以内的素数，这种求素数的方法称为爱拉托斯散（Eratosthenes）筛法。随着n的增加，按照上述方法判断出n是否为素数的时间复杂度为)(21nO。由定理1可以看出每个整数都有一个素因数，下面我们要证明每个整数一定可以表示成素数的乘积。定理2任一整数1n都可以表示成素数的乘积，即rpppn21，rppp21（1）其中ip是素数。定理3素数有无穷多个。定理4形如14k素数有无穷多个。上述两个定理都说明了一件事情：素数有无穷多个。若以)(x表示不超过实数x的素数个数，记np为第n个素数，我们很容易得到)(x的一个很弱的下界估计和np的一个很弱的上界估计。定理5设全体素数按大小顺序排成的序列是：.,,,5,3,254321ppppp我们有xxx2,loglog)(22，（2）和,,2,1,212npnn（3）进一步运用简单的微积分知识我们可以得到更强一些的Chebyshev不等式估计。定理6设实数2x。我们有nnpnnnln2ln8ln2ln61，2nxxxxxln2ln6)(ln32ln事实上，还可以得到如下的极限形式xxxx,1/ln)(，nnnpn,1)ln/(，这个结论也被称为素数定理。由素数定理可知，当x很大时，xxxln)(，表1.1说明了此种估计公式在x越大时越准确。表1.1素数的分布x)(xxxln/xxx/)ln)((310168144.81.16041012291085.71.13251095928685.91.1046107849874382.41.085710664579620420.71.07181057614555428681.01.0619105084753448254942.41.0541010455052512434294481.91.048应用素数定理，我们可以分别估算出64位、128位的素数个数分别为17636364641005.22ln22ln2741271271281281025.32ln22ln2在64位奇数中任选一个奇数是素数的概率约为044.02/)22(1005.2636417在128位奇数中任选一个奇数是素数的概率约为0.022，在256位奇数中任选一个奇数是素数的概率约为0.011，即素数越大时，其分布越稀疏，因为数目越大时，比此数小的素数越多，则此数被整除的概率越大。素数的性质是数论的核心，也是现代密码学的一个重要内容，素数的分布情况和产生模型一直是人们研究的一个重要内容。几千年来，数学家对素数已有深入的研究。其中最有趣的一个问题是“是否有一个简单的方法或公式来产生素数？”不幸的是，许多数学家的推测公式都是错误的...