定义1设a,b是任意两个整数,其中b≠0。如果存在一个 整数q使得等式a=bq成立,就称b整除a或者a被b整除, 记作ba,并把b叫做a的因数,把a叫做b的倍数。否则, 就称b不能整除a或者a不能被b整除,记作ba 由定义可知,0是任何非零整数的倍数;1是任何整数的因 数;任何非零整数既是其自身的因数,又是其自身的倍数 由定义1及乘法运算的性质,立即可以得到整除关系具有下 面性质 性质1(i)a|b分-a|b冷a|-bal‖b; (ⅱ)c|b,且ba→cla; (ii)c|a,且c|b分对任意的整数s,t有c|ax+by; (i)ba且a|b→a=±b; (v)设c≠0,则ba冷→bcac; (ⅵ)若a≠0,则ba→b图a (ⅶi)若b≠0,且{d,d2…d}是b的全体因数,则 b/dl,b/d2…b/d}也是b的全体因数。 例1证明:若3n,5|n,那么15|no 例2设a,b是两个非零整数,且存在整数s,t,使得 sa+tb=1。证明 (1)若ma,m|b,则有m=±1 (2)若an,b|n,则有ab|n
定义 1 设 a,b 是任意两个整数，其中 b 0。 如果存在一个 整数 q 使得等式 a = bq 成立，就称 b 整除 a 或者 a 被 b 整除， 记作 b | a ，并把 b 叫做 a 的因数，把 a 叫做 b 的倍数。否则， 就称 b 不能整除 a 或者 a 不能被 b 整除，记作 b | a。 由定义可知，0 是任何非零整数的倍数；1 是任何整数的因 数；任何非零整数既是其自身的因数，又是其自身的倍数。 由定义 1 及乘法运算的性质，立即可以得到整除关系具有下 面性质 性质 1 （ⅰ） a | b −a | b a | −b | a ||| b | ； （ⅱ） c | b,且b | a c | a ； （ⅲ） c | a,且c | b 对任意的整数s,t有c | ax + by ； （ⅳ） b | a且a | b a = b ； （ⅴ）设 c 0 ，则 b | a bc | ac ； （ⅵ）若 a 0 ，则 b | a | b || a |。 （ⅶ）若 b 0 ， 且 { , , , } d1 d2 dk 是 b 的全体因数，则 { / , / , , / } b d1 b d2 b dk 也是 b 的全体因数。 例 1 证明：若 3| n，5 | n ，那么 15 | n 。； 例 2 设 a,b 是 两 个非 零 整 数 ， 且存 在 整 数 s,t ， 使得 sa + tb =1 。证明 （1）若 m | a,m | b ，则有 m = 1 ； （2）若 a | n,b | n ，则有 ab | n
例3设a为奇数,b为偶数,且a|b,则a 定义2设整数n≠0,±1。如果除了因数±1和±n外,n没有 其他因数,则称n为素数(或质数)。否则称其为合数 首先给出素数的一个判定定理。 定理1设n是一个大于1的正整数,如果对所有小于或等 于n的素数p,都有pn,则n一定是素数。 由定理1,对于比较小的整数,我们可以迅速的判断出它是 否为素数 例4求出所有不超过100的素数。 算法1.1.1(1)i=2 (2)如果2|,则i不是素数,转到(7) (3)如果3i,则i不是素数,转到(7); (4)如果5i,则不是素数,转到(7) (5)如果7|i,则i不是素数,转到(7) (6)输出i的值; (7)i=i+1 (8)如果i>100,程序结束 (9)否则返回到(2)。 输出的结果为 2357 11131719 2329
例 3 设 a 为奇数， b 为偶数，且 a | b ，则 2 | b a 。 定义 2 设整数 n 0,1 。如果除了因数 1 和 n 外， n 没有 其他因数，则称 n 为素数（或质数）。否则称其为合数。 首先给出素数的一个判定定理。 定理 1 设 n 是一个大于 1 的正整数，如果对所有小于或等 于 n 的素数 p ，都有 p | n ，则 n 一定是素数。 由定理 1，对于比较小的整数，我们可以迅速的判断出它是 否为素数。 例 4 求出所有不超过 100 的素数。 算法 1.1.1 （1） i = 2 ; （2） 如果 2 | i ，则 i 不是素数，转到（7）； （3） 如果 3 | i ，则 i 不是素数，转到（7）； （4） 如果 5 | i ，则 i 不是素数，转到（7）； （5） 如果 7 | i ，则 i 不是素数，转到（7）； （6） 输出 i 的值； （7） i = i +1 （8） 如果 i 100 ，程序结束； （9） 否则返回到（2）。 输出的结果为 2 3 5 7 11 13 17 19 23 29
3137 414347 5359 6167 717379 8389 9197 从例4我们可以看出100以内的素数分布情况,进一步可以 由上述例题求出n=10000以内的素数,这种求素数的方法 称为爱拉托斯散( Eratosthenes)筛法。随着n的增加,按照 上述方法判断出n是否为素数的时间复杂度为O(n2) 由定理1可以看出每个整数都有一个素因数,下面我们要证 明每个整数一定可以表示成素数的乘积。 定理2任一整数n>1都可以表示成素数的乘积,即 n=PP2…p,P1≤P2s…Sp (1) 其中p是素数 定理3素数有无穷多个 定理4形如4k-1素数有无穷多个。 上述两个定理都说明了一件事情:素数有无穷多个。若以 丌(x)表示不超过实数x的素数个数,记p为第n个素数,我 们很容易得到丌(x)的一个很弱的下界估计和p的一个很弱 的上界估计
31 37 41 43 47 53 59 61 67 71 73 79 83 89 91 97 从例 4 我们可以看出 100 以内的素数分布情况，进一步可以 由上述例题求出 n =10000 以内的素数，这种求素数的方法 称为爱拉托斯散（Eratosthenes）筛法。随着 n 的增加，按照 上述方法判断出 n 是否为素数的时间复杂度为 ( ) 2 1 O n 。 由定理 1 可以看出每个整数都有一个素因数，下面我们要证 明每个整数一定可以表示成素数的乘积。 定理 2 任一整数 n 1 都可以表示成素数的乘积，即 n = p1 p2 pr， p1 p2 pr （1） 其中 i p 是素数。 定理 3 素数有无穷多个。 定理 4 形如 4k −1 素数有无穷多个。 上述两个定理都说明了一件事情：素数有无穷多个。若以 (x) 表示不超过实数 x 的素数个数，记 n p 为第 n 个素数，我 们很容易得到 (x) 的一个很弱的下界估计和 n p 的一个很弱 的上界估计
定理5设全体素数按大小顺序排成的序列是 P P2=3,P3=5,P2,P 我们有 (x)>log, log 2 和 p≤2,n=1,2, 进一步运用简单的微积分知识我们可以得到更强一些的 Chebyshev不等式估计 定理6设实数x≥2。我们有 6h2/mn<p<8 hlnn,n≥2 In 2 In 2x <丌(x)<6ln2 3丿lnx nx 事实上,还可以得到如下的极限形式 丌(x)lnx/x->1,x→+∞, p/(nlnn)→>1,n→>∞ 这个结论也被称为素数定理。由素数定理可知,当x很大时, 丌(x)≈ ,表1.1说明了此种估计公式在x越大时越准确 nx 表1.1素数的分布 丌(x) X/Inx (丌(x)lnx)/x 10 168 144.8 1.160
定理 5 设全体素数按大小顺序排成的序列是： 2, 3, 5, , , . p1 = p2 = p3 = p4 p5 我们有 (x) log log x, 2 x 2 2 ， （2） 和 2 , 1,2, , 1 2 = − p n n n （3） 进一步运用简单的微积分知识我们可以得到更强一些的 Chebyshev 不等式估计。 定理 6 设实数 x 2 。我们有 n n pn nln n ln 2 8 ln 6ln 2 1 ， n 2 x x x x x ln ( ) 6ln 2 3 ln ln 2 事实上，还可以得到如下的极限形式 (x)ln x / x →1, x → +， pn /(nln n) →1, n →， 这个结论也被称为素数定理。由素数定理可知，当 x 很大时， x x x ln ( ) ，表 1.1 说明了此种估计公式在 x 越大时越准确。 表 1.1 素数的分布 x (x) x /ln x ( (x)ln x)/ x 3 10 168 144.8 1.160
10 1229 1085.7 1.132 9592 86859 1.104 10° 78498 743824 1.085 10 664579 620420.7 1071 5761455 5428681.0 1061 10 50847534 4825494241.054 10° 45505251243429448191048 应用素数定理,我们可以分别估算出64位、128位的素数个 数分别为 2.05×107 In 2 ln 2 2 2 ln22a≈3.25×10 在64位奇数中任选一个奇数是素数的概率约为 2.05×107 ≈0.044 (2-2)/2 在128位奇数中任选一个奇数是素数的概率约为0.022,在 256位奇数中任选一个奇数是素数的概率约为0011,即素数 越大时,其分布越稀疏,因为数目越大时,比此数小的素数 越多,则此数被整除的概率越大。 素数的性质是数论的核心,也是现代密码学的一个重要内 容,素数的分布情况和产生模型一直是人们研究的一个重要 内容。几千年来,数学家对素数已有深入的研究。其中最有
4 10 1229 1085.7 1.132 5 10 9592 8685.9 1.104 6 10 78498 74382.4 1.085 7 10 664579 620420.7 1.071 8 10 5761455 5428681.0 1.061 9 10 50847534 48254942.4 1.054 10 10 455052512 434294481.9 1.048 应用素数定理，我们可以分别估算出 64 位、128 位的素数个 数分别为 17 63 63 64 64 2.05 10 ln 2 2 ln 2 2 − 74 127 127 128 128 3.25 10 ln 2 2 ln 2 2 − 在 64 位奇数中任选一个奇数是素数的概率约为 0.044 (2 2 )/ 2 2.05 10 64 63 17 − 在 128 位奇数中任选一个奇数是素数的概率约为 0.022，在 256 位奇数中任选一个奇数是素数的概率约为 0.011，即素数 越大时，其分布越稀疏，因为数目越大时，比此数小的素数 越多，则此数被整除的概率越大。 素数的性质是数论的核心，也是现代密码学的一个重要内 容，素数的分布情况和产生模型一直是人们研究的一个重要 内容。几千年来，数学家对素数已有深入的研究。其中最有