定义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/mn1,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，即素数 越大时，其分布越稀疏，因为数目越大时，比此数小的素数 越多，则此数被整除的概率越大。 素数的性质是数论的核心，也是现代密码学的一个重要内 容，素数的分布情况和产生模型一直是人们研究的一个重要 内容。几千年来，数学家对素数已有深入的研究。其中最有
趣的一个问题是“是否有一个简单的方法或公式来产生素 数?”不幸的是,许多数学家的推测公式都是错误的,如 中国古代数学家曾提出下列测试法,以测试一个整数n 是否为素数。若n|2-2,则n为素数。事实上,对于所 有小于341的素数,上述测试法都成立。 2.梅森素数形如 M=22-1(p为素数) 的整数为素数者称为梅森( Mersenne)素数。至今只发现27 个,即 p=2,3,5,7,13,17,19,31,6189,107,1275212607,1279,2203,2281 3217,4253,4423,9689,99411213,21701,23209,44497 是否有无穷个梅森素数还未证明。M,=2047=23×89不 是素数。 费马素数形如 F=2+1(n为自然数) 的整数为素数者称为费马( Fermat)素数。至今只发现5个 费马素数 尽管如此,迄今为止仍然没有发现素数的模型或产生素数的 有效公式,因而寻找大的素数必须借助计算机一个一个地 找。用计算机算两个512位(二进制)的素数的乘积是一件 很容易的事情,但是如果给定一个1024位的数N,让你找出
趣的一个问题是“是否有一个简单的方法或公式来产生素 数？”不幸的是，许多数学家的推测公式都是错误的，如： 1． 中国古代数学家曾提出下列测试法，以测试一个整数 n 是否为素数。若 | 2 − 2 n n ，则 n 为素数。事实上，对于所 有小于 341 的素数，上述测试法都成立。 2．梅森素数 形如 = 2 −1 p M p （ p 为素数） 的整数为素数者称为梅森（Mersenne）素数。至今只发现 27 个，即 3217,4253,4423,9689,9941,11213,21701,23209,44497 p = 2,3,5,7,13,17,19,31,61,89,107,127,521,607,1279,2203,2281, 是否有无穷个梅森素数还未证明。 M11 = 2047 = 2389 不 是素数。 3．费马素数 形如 2 1 2 = + n F n （ n 为自然数） 的整数为素数者称为费马（Fermat）素数。至今只发现 5 个 费马素数 尽管如此，迄今为止仍然没有发现素数的模型或产生素数的 有效公式，因而寻找大的素数必须借助计算机一个一个地 找。用计算机算两个 512 位（二进制）的素数的乘积是一件 很容易的事情，但是如果给定一个 1024 位的数 N ，让你找出
它是哪两个素数的乘积就困难多了,数学家至今还没有找到 一种有效的方法去迅速分解一个合数。关于大合数因子分解 的时间复杂度下限目前尚没有一般的结果,到现在为止的各 种算法告诉人们这一时间下限将不低于 O(EXP( ninIn m)2),此结果明显比定理1给出的时间 复杂度O(N")低。 因为不是任意两个整数都具有整除关系,所以我们引进带余 数除法或欧几里得除法。 定理7(欧几里得除法)设a,b是两个给定的整数,其中 b≠0,则对任意的整数c,存在惟一的整数q,r,使得 a=bq+r,c≤r<b|+c。 称q为b除a的不完全商 在上式中取不同的c,就得到不同形式的带余数除法 (1)取c=0,则0≤r<b,称r为a被b除后的最小非负 余数,此时,可以看出,ba的充要条件是r=0 (2)取c=1,则1≤rsb|,称r为a被b除后的最小正余 数,此时,可以看出,ba的充要条件是r=b|; (3)取C=-|b+1,则-|b|+1≤r≤0,称r为a被b除 后的最大非正余数,此时,可以看出,ba的充要条件是 0; (4)取C=-|b|,则-|b≤r<0,称r为a被b除后的最 大负余数,此时,可以看出,ba的充要条件是r=-|b|;
它是哪两个素数的乘积就困难多了，数学家至今还没有找到 一种有效的方法去迅速分解一个合数。关于大合数因子分解 的时间复杂度下限目前尚没有一般的结果，到现在为止的各 种 算 法 告 诉 人 们 这 一 时 间 下 限 将 不 低 于 ( (ln ln ln ) ) 1/ 2 O EXP N N ，此结果明显比定理 1 给出的时间 复杂度 ( ) 1/ 2 O N 低。 因为不是任意两个整数都具有整除关系，所以我们引进带余 数除法或欧几里得除法。 定理 7（欧几里得除法） 设 a,b 是两个给定的整数，其中 b 0 ，则对任意的整数 c ，存在惟一的整数 q,r ，使得 a = bq + r ，c r | b | +c。 称 q 为 b 除 a 的不完全商。 在上式中取不同的 c ，就得到不同形式的带余数除法。 （1） 取 c = 0 ，则 0 r | b | ，称 r 为 a 被 b 除后的最小非负 余数，此时，可以看出， b | a 的充要条件是 r = 0 ； （2） 取 c =1 ，则 1 r | b | ，称 r 为 a 被 b 除后的最小正余 数，此时，可以看出， b | a 的充要条件是 r =| b | ； （3） 取 c = − | b | +1 ，则− | b | +1 r 0 ，称 r 为 a 被 b 除 后的最大非正余数，此时，可以看出， b | a 的充要条件是 r = 0 ； （4） 取 c = − | b | ，则− | b | r 0 ，称 r 为 a 被 b 除后的最 大负余数，此时，可以看出， b | a 的充要条件是 r = − | b | ；
(5)当b为偶数时,取c=-|b|/2,有 b|/2≤r<b|/2 取c=-|b|/2+1 b/2<FSb/2; 当b为奇数时,取c=-(b|-1)/2,有 -(b-1)2≤r≤(b|+1)/2-1=(b|-1)/2 这时,称r为绝对值最小余数 例5设b=6,C=-7,则对任意一个整数a, a被b除后的最小非负余数为 a被b除后的最小正余数为 a被b除后的最大非正余数为 a被b除后的最大负余数为 a被b除后的绝对值最小余数为 a被c除后的最小非负余数为 a被c除后的最小正余数为 a被c除后的最大非正余数为 a被c除后的最大负余数为 a被c除后的绝对值最小余数为 例6证明:设m,n,k是三个整数,则 (1)对任意的整数m,n,必有8m2-n2-2; (2)若2/m,则m2+n≠k2; (3)若3|m,则m2+n2≠k2; (4)若m2+n2=k,则6|mm
（ 5 ） 当 b 为 偶 数 时 ， 取 c = − | b | / 2 ， 有 − | b | / 2 r | b | / 2 ； 取 c = − | b | / 2 +1 ， 有 − | b | / 2 r | b | / 2 ； 当 b 为奇数时，取 c = −(| b | −1)/ 2 ，有 − (| b | −1)/ 2 r (| b | +1)/ 2 −1= (| b | −1)/ 2 这时，称 r 为绝对值最小余数。 例 5 设 b = 6,c = −7 ，则对任意一个整数 a， a 被 b 除后的最小非负余数为 a 被 b 除后的最小正余数为 a 被 b 除后的最大非正余数为 a 被 b 除后的最大负余数为 a 被 b 除后的绝对值最小余数为； a 被 c 除后的最小非负余数为 a 被 c 除后的最小正余数为 a 被 c 除后的最大非正余数为 a 被 c 除后的最大负余数为 a 被 c 除后的绝对值最小余数为 例 6 证明：设 m,n,k 是三个整数，则 （1）对任意的整数 m,n ，必有 8 | 2 2 2 m − n − ； （2）若 2 | mn ，则 2 2 2 m + n k ； （3）若 3 | mn ，则 2 2 2 m + n k ； （4）若 2 2 2 m + n = k ，则 6 | mn