1、第 19章 初等数论 54-2以整数集为典型代数系统的数论知识一直被认为是既神秘又古老。虽然绝大多数人自小学生起就开始认识它，而一些数学家却一辈子踏着它往皇冠上攀。现在，计算机终于给数论这门再纯洁不过的数学分支扬起了应用的帆。我们这里介绍的虽然只是初等数论的基础知识，但它们在计算机的数据表示、数据传输以及电子商务应用中的数据保密等方面起着非常重要的作用。 54-3第 19章 初等数论 19.1 素数19.2 最大公约数与最小公倍数19.3 同余19.4 一次同余方程19.5 欧拉定理和费马小定理 19.6 初等数论在计算机科学技术中的几个应用54-419.1 素数 整除、倍数和因子带余除法素数
2、与合数算术基本定理筛法54-5整除、倍数和因子今后只考虑正整数的正因子 .平凡因子 : 1和自身真因子 : 除 1和自身之外的因子例如 , 2, 3 是 6 的真因子设 a, b是两个整数，且 b0. 如果存在整数 c 使 a=bc， 则称 a 被 b 整除 ，或 b 整除 a， 记作 b|a. 此时 , 又称 a 是 b 的倍数 ， b是 a 的 因子 . 把 b 不整除 a 记作 b a.例如 , 6有 8个因子 1, 2, 3和 6.54-6整除的性质性质 19.1 若 a |b且 a |c, 则 x, y, 有 a | xb+yc.性质 19.2 若 a |b且 b |c, 则 a |
3、c.性质 19.3 设 m0, 则 a |b 当且仅当 ma | mb.性质 19.4 若 a | b且 b | a, 则 a= b.性质 19.5 若 a | b且 b0, 则 |a| |b|. 带余除法 : a=qb+r, 0r 1, p是素数且 d | p, 则 d=p.性质 19.7设 p是素数且 p | ab, 则必有 p | a 或者 p | b. 设 p是素数且 p | a1a2 ak, 则必存在 1 i k, 使得 p| ai.性质 19.8 a1是合数当且仅当 a=bc, 其中 11, 则 a= , 其中 p1,p2, pk是不相同的素数 , r1,r2, rk是正整数 ,
4、并且在不计顺序的情况下 , 该表示是惟一的 . 该表达式称作整数 a的素因子分解 . 例如 30=2 3 5, 117=32 13, 1024=210 推论 设 a= , 其中 p1,p2, pk是不相同的素数 , r1,r2, rk是正整数 , 则正整数 d为 a的因子的充分必要条件是 d= , 其中 0siri, i=1,2, k.54-9例题例 1 21560有多少个正因子 ?解 21560=2357211由推论 , 21560的正因子的个数为 4232=48.例 2 10!的二进制表示中从最低位数起有多少个连续的 0?解 2, 3, 4=22, 5, 6=23, 7, 8=23, 9=
5、32, 10=25.得 10!=2834527,故 10!的二进制表示中从最低位数起有 8个连续的 0.54-10素数的分布梅森数 (Marin Mersenne): 2p1, 其中 p为素数 当 n是合数时 , 2n1一定是合数 ,2ab1=(2a1)(2a(b1)+2a(b2)+2 a+1).梅森数可能是素数 , 也可能是合数 : 221=3, 231=7, 251=31, 271=127都是素数 , 而 2111=2047=2389是合数 .到 2002年找到的最大梅森素数是 2134669171, 有 4百万位 . 定理 19.2 有无穷多个素数 .证 用反证法 . 假设只有有穷多个素数 , 设为 p1,p2, pn,令 m=p1p2p n+1. 显然 , pi m, 1in. 因此 , 要么 m本身是素数，要么存在大于 pn的素数整除 m, 矛盾 .
