数论讲义-数论.pdfVIP

数论基础的教学设计 计算机系统与网络安全技术课题组 电子科技大学计算机科学与工程学院，四川成都 611731 一、诊断性练习的设计 1. 什么是最大公因子，什么是最小公倍数？ 2. 什么是同余？同余具有什么样的性质。 说明：数论部分虽然不是本课程的重点，但它却是学习其他部分，尤其是密码学部分的基础。 这部分对不同的学生可能差别很大，如信息安全专业的学生可能比较熟悉这部分内容，但计 算机科学与技术专业的学生对这部分内容可能比较陌生，所以我们要灵活掌握课程教学内 容，根据学生的反馈情况进行教学。第 1 题的目的是判断学生是否掌握公因子，最大公因子， 公倍数，最小公倍数。这是学习数论的基础。如果学生不是很清楚，应该先讲解这部分内容。 如果学生回答的很好，只需要引导学生简单的回忆一下就可以了。第 2 题的目的是判断学生 对同余理解情况，如果学生不是很清楚，应该重点对这部分内容进行讲解。如果学生回答的 很好，则可以将重点放在费马定理、欧拉定理和中国剩余定理等上。 二、学习目标 1. 能正确计算最大公因子和最小公倍数。 2. 能正确计算欧拉函数。 3. 掌握同余的重要性质，会求乘法逆元。 4. 掌握费马定理、欧拉定理和中国剩余定理。 三、学习重点 同余的性质，乘法逆元的求法、欧拉定理和中国剩余定理。 四、学习难点 求解乘法逆元，欧拉函数的计算，中国剩余定理的证明。 五、教学流程设计 1. 通过诊断性练习，摸清学生知识情况，这个阶段可以随机抽取一些同学来回答。 2. 向学生讲述这节课的学习目标、学习的重点和难点。 3. 讲解如下内容： 定义 1 对于整数 a, b(b ≠0)，若存在整数x 使得 b=ax ，则称a 整除 b ，或a 是 b 的因子， 记作 a|b 。 整除有如下性质： ①a|a 。 ②若 a|b, b|a，则a= ±b 。 ③若 a|b, b|c，则a|c 。 ④若 a|b, a|c，则对任意的整数x , y ，有a|bx+cy 。 定义 2 若 a, b, c 都是整数，a 和 b 不全为 0 且 c|a, c|b ，则称 c 是 a 和 b 的公因子。如果 整数 d 满足 ①d 是 a 和 b 的公因子； ②a 和 b 的任一公因子，也是d 的因子。 则称 d 是 a 和 b 的最大公因子，记作d=gcd(a, b) 。如果gcd(a, b)=1 ，则称a 和 b 互素。 定义 3 若 a, b, c 都是整数，a 和 b 都不为 0 且 a|c, b|c ，则称 c 是 a 和 b 的公倍数。如果 整数 d 满足 ①d 是 a 和 b 的公倍数； ②d 整除 a 和 b 的任一公倍数。 则称 d 是 a 和 b 的最小公倍数，记作d=lcm(a, b) 。 定义 4 对于任一整数p (p 1) ，若p 的因子只有±1 和±p ，则称p 为素数，否则称为合 数。 对于任一整数 a(a1) ，都可以惟一的分解为素数的乘积，即 a1 a2 at a p1 p2 pt 其中，p p …p 都是素数，a 0(i=1, 2, …, t) 。 1 2 t i 定义 5 设 n 是一正整数，小于 n 且与 n 互素的正整数的个数称为欧拉(Euler)函数，记 作φ(n) 。欧拉函数有如下性质： ①若 n 是素数，则φ(n) 1 。 ②若 m 和 n 互素，则φ(mn) φ(m)φ(n) 。 ③如果 a1 a2 at n p1 p2 pt 其中，p p …p 都是素数，a 0(i=1, 2, …, t) ，则 1 2 t i