第一单元 整数的可除性.pptVIP

litonghong 课程概况 本课程介绍了信息安全涉及 到数学理论，主要有三个方面 内容：数论、代数和椭圆曲线 论. 教学目标 要求能够掌握逻辑推理的数学方法，数 论、代数等的基本理论，并能运用这些理论 知识解决实际问题. 通过本课程的学习，不 仅能为学生的专业课学习及将来从事信息安 全方面开发和应用研究打下坚实的基础，同 时有助于培养抽象思维、严格的逻辑推理和 创新能力. 课程考核 1. 考试课. 2. 学时：一学期. 3.考核方式： 作业(30%) + 考试(70%) 作业= 平时作业(20%)+ 课堂小测验(10%) 4. 考试方式：闭卷考试. 作业要求 1. 一周一次。按时交。 2. 作业实行记分制。 3. 严禁抄袭作业。 联系方式 电话办公室:教研楼120(教研科) 第一章 整数的可除性 整除的概念 素数 欧几里得除法 整数的表示 最大公因数 广义欧几里得除法 整除的概念 定义1 设a、b是两个整数，其中b≠0 如果存在一个整数 q 使得等式 a=bq 成 立，就称b整除a或者a被b整除，记作 b|a ，并把b叫作a的因数，把a叫作b的 倍数.这时，q也是a的因数，我们常常 将q写成a／b或 整除的一些常用结论： 当b遍历整数a的所有因数时，-b也遍历整数a的所有因数. (2)当b遍历整数a的所有因数时，a/b也遍历整数a的所有因数. (3)设b，c都是非零整数， (i)若b|a，则|b|||a|. (ii)若b|a，则bc|ac. (iii)若b|a，则1|b|≤|a|. 例1 30 ＝ 2﹡15 ＝3﹡10 = 5﹡6 有2，3，5分别整除30或30被2，3，5 整除，记作2|30，3|30，5|30.这时， 2，3，5都是30的因数，30是2，3，5 的倍数. 问题： 是否存在这样的整数a，b，c，使得a|bc， a b，且a c? 定理1 设a，b≠0，c≠0是三个整数.若 c|b，b|a，则c|a. 定理2 设a，b，c≠0是三个整数，若c|a， c|b，则c|a±b. 证：设c|a，c|b，那么存在两个整数q1， q2分别使得 a=c q1 ，b=c q2 因此， a±b= c q1 ±c q2 =c(q1± q2 ) 因为q1± q2是整数，所以a±b被c整除. 定理3 设a，b，c是三个整数.若c|a，c|b 则对任意整数s，t，有c|sa+tb. 证：设c|a，c|b，那么存在两个整数q1， q2分别使得 a=cq1，b=c q2 因此， sa+tb=s(cq1) +t(c q2)=c(sq1+tq2) 因为sq1+tq2是整数，所以sa+tb被c整除. 例3 如果7|14，7|21，所以 7|(3*21-4*14)=7， 7|(3*21+4*14)=119 例4 设a，b，c≠0是三个整数，c|a，c|b. 如果存在整数s，t，使得sa+tb=1，则 c=±1. 证：设c|a，c|b，因为存在整数s，t使得 sa+tb=1， 根据定理3，我们有 c|sa+tb=1 因此，c=±1. 定理3的推广形式： 定理4 若整数a1，…，an都是整数c≠0的 倍数，则对任意n个整数s1，…，sn，整数 是c的倍数. 定理5 设a，b都是非零整数.若a|b， b|a，则a=±b. 证：设a|b，b|a，那么存在两个整数q1，q2 分别使得 a=bq1， b=aq2 从而，a = bq1=(aq2)q1 =a(q1q2) 这样，q1q2＝1，因为， q1，q2是 整数，所 以q1=q2=±1，进而，a=±b. 例5 证明：若3|n ，且7|n，则21|n. 证：由3|n，得 n=3m ，所以7|3m.由 此及7|7m ，得 7|(7m-2·3m)=m. 因此，有 21|n. 例6 设a ，b是两个给定的非零整数，且有 整数x，y使得ax + by = 1.证明：若a|n， b|n，则ab|n. 证：n=n (ax+ by)=(na) x +(nb) y. 由a| n，b| n可得ab | na ，ab | nb，所以 ab | n. 例7 证明：如果a是整数，则a3-a被3整除. 证： a3-a=(a-1)a(a+1).因为任意整数a 可以写成 a = 3n+b (a、b是整数，1