引言、整除的概念、带余数除法.ppt

初等数论 黎琳lilin 2015 03 11 授课教师 黎琳E mail lilin 办公地点 九教北310 电话 51688637课件 思源教学平台 教材闵嗣鹤 严士健 初等数论 第三版 高等教育出版社 参考教材 1 潘承洞 潘承彪 初等数论 第三版 北京大学出版社 2 罗森 KennethH Rosen 初等数论及其应用 ElementaryNumberTheory 6thEdition 机械工业出版社 3 科布茨 数论与密码学教程 第2版 世界图书出版社 课程设置 整数的可除性 6学时不定方程2学时同余 6学时同余式 4学时二次同余式与平方剩余 6学时原根与指标 4学时连分数2学时 考核方式 成绩评定主要包括平时成绩 含考勤 作业 随堂测试 占50 期末考试成绩占50 期末采取闭卷笔试 序言 数论是研究整数性质的一门很古老的数学分支 其初等部分是以整数的整除性为中心的 包括整除性 不定方程 同余式 连分数 素数 即质数 分布以及数论函数等内容 统称初等数论 elementarynumbertheory 初等数论是数论中不求助于其他数学学科的帮助 只依靠初等的方法来研究整数性质的分支 初等数论是信息安全专业的必修课 是密码学等课的基础 发展历史 初等数论的大部份内容早在古希腊欧几里德的 几何原本 公元前3世纪 中就已出现 欧几里得证明了素数有无穷多个 他还给出求两个自然数的最大公约数的方法 即所谓欧几里得算法 欧几里得 前330年 前275年 欧氏几何学的开创者 古希腊数学家 以其所著的 几何原本 闻名于世 我国古代在数论方面亦有杰出之贡献 现在一般数论书中的 中国剩余定理 正是我国古代 孙子算经 中的下卷第26题 我国称之为孙子定理 约成书于四 五世纪 作者生平和编写年代都不清楚 现在传本的 孙子算经 共三卷 卷下第31题 可谓是后世 鸡兔同笼 题的始祖 后来传到日本 变成 鹤龟算 近代初等数论的发展得益于费马 欧拉 拉格朗日 勒让德和高斯等人的工作 高斯1777 1855 德国数学家 物理学家 天文学家 大地测量学家 1801年 著有 算术探究 开始了现代数论的新纪元 高斯还提出 数学是科学之王 数论是数学之王 费马 法 1601 1665 是数学史上最伟大的业余数学家 提出了费马大 小定理 在坐标几何 无穷小 概率论等方面有巨大贡献 哥德巴赫1690 1764 德国数学家 曾担任中学教师 1725年到俄国 被选为彼得堡科学院院士 勒让德 法 1752 1833 在分析学 数论 初等几何与天体力学 取得了许多成果 是椭圆积分理论奠基人之一 对数论的主要贡献是二次互反律 还是解析数论的先驱者之一 雅可比 德 1804 1851 在偏微分方程中 引进了 雅可比行列式 对行列式理论作了奠基性的工作 在代数学 变分法 复变函数论 分析力学 动力学及数学物理方面也有贡献 欧拉1707 1783 瑞士数学家 自然科学家 是数学史上最多产的数学家 每年写出八百多页的论文 无穷小分析引论 微分学原理 积分学原理 等都成为数学中的经典著作 希尔伯特 德 1862 1943 他领导的数学学派是19世纪末20世纪初数学界的一面旗帜 希尔伯特被称为 数学界的无冕之王 著 数论报告 等 由于自20世纪以来引进了抽象数学和高等分析的巧妙工具 数论得到进一步的发展 从而开阔了新的研究领域 出现了代数数论 解析数论 几何数论等新分支 近年来初等数论在计算机科学 组合数学 密码学 代数编码 计算方法等领域内更得到了广泛的应用 无疑同时也促进着数论的发展 华罗庚1910 1985 是中国解析数论 矩阵几何学 典型群 自安函数论等多方面研究的创始人和开拓者 以华氏命名的数学科研成果很多 被列为芝加哥科学技术博物馆中当今世界88位数学伟人之一 陈景润1933 1996 主要研究解析数论 他研究哥德巴赫猜想和其他数论问题的成就 至今仍然在世界上遥遥领先 其成果也被称之为陈氏定理 王元1930 50年代至60年代初 首先在中国将筛法用于哥德巴赫猜想研究 并证明了命题3 4 1957年又证明2 3 这是中国学者首次在此研究领域跃居世界领先地位 潘承洞 在解析数论研究方面有突出贡献 主要成就涉及算术数列中的最小素数 哥德巴赫猜想研究 以及小区间上的素变数三角和估计等领域 几个著名数论难题 初等数论是研究整数性质的一门学科 历史上遗留下来没有解决的大多数数论难题其问题本身容易搞懂 容易引起人的兴趣 但是解决它们却非常困难 其中 非常著名的问题有 哥德巴赫猜想 费尔马大定理 孪生素数问题 完全数问题等 1742年 由德国中学教师哥德巴赫在教学中首先发现的 1742年6月7日 哥德巴赫写信给当时的大数学家欧拉 正式提出了以下的猜想 一个大于6的偶数可以表示为不同的两个质数之和 陈景润在1966年证明了 哥德巴赫猜想 的 一个大偶数可以表示为一个素数和一个不超过两个素数的乘积之和 所谓的1 2 是筛法的光辉顶点 至今仍是 哥德巴赫猜想 的最好结果 1 哥德巴赫猜想 2 费尔马大定理 费马是十七世纪最卓越的数学家之一 他在数学许多领域中都有极大的贡献 因为他的本行是专业的律师 世人冠以 业余王子 之美称 在三百七十多年前的某一天 费马正在阅读一本古希腊数学家戴奥芬多斯的数学书时 突然心血来潮在书页的空白处 写下一个看起来很简单的定理 经过8年的努力 英国数学家安德鲁 怀尔斯终于在1995年完成了该定理的证明 在密码学中应用 古典密码体制 代换密码定义代换如下 abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABC每个字母对应一个数字abcdefghijklm0123456789101112nopqrstuvwxyZ13141516171819202122232425凯撒密码如下 C Ek m m k mod 26 m Dk C C k mod 26 公钥密码体制 RSA算法 加解密 数字签名基于离散对数问题的公钥密码算法背包密码体制素性检测 第一章整数的可除性 整数的基本知识 I 整数集合中可以做加法运算 满足以下性质 i 结合律 ii 交换律 iii 相消律 iv v 对任意的 整数的基本知识 II 整数集合中可以做乘法运算 满足以下性质 i 结合律 ii 交换律 iii 相消律 iv v vi 分配律 整数的基本知识 III 整数集合中有大小关系 满足以下性质 i 对任意的 ii 自反性 iii 反对称性 iv 传递性 v 对任意的 1整除的概念 带余数除法 举例 注意 整除和除法的区别 证明思路 带余数除法的内涵