1、第 19章 初等数论 81-2以整数集为典型代数系统的数论知识一直被认为是既神秘又古老。虽然绝大多数人自小学生起就开始认识它，而一些数学家却一辈子踏着它往皇冠上攀。现在，计算机终于给数论这门再纯洁不过的数学分支扬起了应用的帆。我们这里介绍的虽然只是初等数论的基础知识，但它们在计算机的数据表示、数据传输以及电子商务应用中的数据保密等方面起着非常重要的作用。 81-381-4第 19章 初等数论 19.1 素数19.2 最大公约数与最小公倍数19.3 同余19.4 一次同余方程19.5 欧拉定理和费马小定理 19.6 初等数论在计算机科学技术中的几个应用81-519.1 素数 整除、倍数和因子带余
2、除法素数与合数算术基本定理筛法81-6整除、倍数和因子今后只考虑正整数的正因子 .平凡因子 : 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.81-7整除的性质性质 19.1 若 a |b且 a |c, 则 x, y, 有 a | xb+yc.性质 19.2 若 a |b且 b |c, 则
3、 a |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.81-10例题例 1 21560有多少个正因子 ?解 21560=2357211由推论 , 21560的正因子的个数为 4232=48.例 2 10!的二进制表示中从最低位数起有多少个连续的 0?解 2, 3, 4=22, 5, 6=23, 7, 8=23, 9=32, 10=25.得 10!=2834527,故 10!的二进制表示中从最低位数起有 8个连续的 0.
