《信息保障与安全》教学课件 第1章 整数的可除性.pptVIP

* 计算机科学与技术学院 * 证明可参考： 《素数定理的初等证明》 潘承洞 潘成彪 著 * 计算机科学与技术学院 * * 计算机科学与技术学院 * * 计算机科学与技术学院 * 问题：当n为素数时，2n-1一定是素数吗？ 211-1=2047=23*89 * 计算机科学与技术学院 * * 计算机科学与技术学院 * * 高斯函数[x]和{x}的定义及其性质 * * * 本章主要内容 * 本章重点： 整除的概念和性质 欧几里得除法及其应用（求最大公因子及线性表达式） 最大公因子和最小公倍数的性质 素数的判定方法 了解素数定理及素数的分布情况； 习题： 1,2,4,7,8,13,17,18,22,28,29,32,33,34,35,39,46,47,49,50,51,52,54,55,56 其他选作 * 计算机科学与技术学院 * * 计算机科学与技术学院 * * 计算机科学与技术学院 * * 称为整数集合。 这种数虽然看起来简单，但却有着极其有趣而深刻的性质。 这是一门历史悠久而至今还富有强大生命力的学科。 * 还有谁不知道什么叫整数？整数的一部分---最简单的数学模型就是自然数1，2，3，…的集合。 * 在一切自然语言中，都有自然数出现。有的语言中数目的名称多些，有的语言中少些，但是总有一些数目由于太大而没有名称。这种现象或许就是人们第一次碰到无穷大。 或者，更具体一些：地球上的沙粒是不是数不完的？ * 把加法和乘法添加到自然数模型当中去。这样它就具有许多非常有趣的性质。 使得这门古老的学科又焕发了青春。 * 它和有理数系统及实数系统等不一样 * 我们讲授这一章，一方面是由于其本身的重要性，一方面是为下面三章作准备，因为，下面三章里一些较抽象的内容很多都可以在数论中找到根源和实例。 * * * * * * * * * 1.5 素数 算术基本定理 * * * * 计算机科学与技术学院 * * * * * * * * * * * 每个正整数可表示成素数幂的乘积 素数是否有无穷多个？ 如果有无穷多个，那么作为无穷大量，素数个数具有怎样的形状？ 对正实数x，以?(x)表示不超过x的素数个数 例如：?(15) = 6，?(10.4) = 4，?(50) = 15 * 计算机科学与技术学院 * 定理1 素数有无限多个 * 计算机科学与技术学院 * * 计算机科学与技术学院 * * 计算机科学与技术学院 * 费尔马--业余数学家之王 * 计算机科学与技术学院 * 费尔马(Pierre de Fermat，1601～1665)法国著名数学家 1601.8.17出生于法国图卢兹。父亲开了一家大皮革商店，拥有相当丰厚的产业 小时候受教于他的叔叔 14岁时，才进入博蒙·德·洛马涅公学，毕业后先后在奥尔良大学和图卢兹大学学习法律 还没大学毕业，便买好了“律师”和“参议员”的职位。 1631年毕业返回家乡以后，便成为图卢兹议会的议员 直到去世都没失去官职，而且逐年得到提升 1646年，费马升任议会首席发言人，还当过天主教联盟的主席等职。费马的官场生涯没有突出政绩 费马生有三女二男，长子整理了费马的数学论著并积极出版费马的数学论著《数学论集》　　 对数论的贡献主要有： 费马大定理：n2的整数，则方程x^n+y^n=z^n没有满足xyz≠0的整数解。由英国数学家怀尔斯证明(1995年)，证明过程是相当艰深的！ 费马小定理：a^p-a≡0(mod p)，其中p是素数，a是正整数，证明比较简单 错误贡献 1640年，费马说他发现形如Fn=2^(2^n)+1的数全是素数，比如当n=0~4时，3，5，17，257，65537都是素数，不过从第五个数开始由于数字过大，费马并没有进行验算。但后来在1732年时，大数学家欧拉发现，n=5时，641*6700417=4294967297却是个合数。并且以后被发现的数都是合数，最大的是n=1495时的Fn * 计算机科学与技术学院 * * * * 计算机科学与技术学院 * * * * * * * * * * j a(r0) b(r1) 1 0 1 1 0 0 1 2 3 … … … … … … … … n * * j 0 1 2 3 4 5 6 * 是否也有(a，d)=1和(b，c)=1？？ * 计算机科学与技术学院 * * * * * * * 欧几里得除法的应用： * 计算机科学与技术学院 * * * * * * 1.4 整除的进一步性质及最小公倍数 一、整除的性质 * * * * 计算机科学与技术学院 * * 练习： 设k是正整数，证明： (1)(ak, bk)=(a, b)k (2)设a，b是正整数，若(a，b)=1，ab=ck，则a=(a, c)k，b=(b, c)k