初等数论§3同余1.ppt

第三章 同 余;§3.1　同余的概念及其基本性质 ;二、同余的定义;三、同余的性质;Date;TH4 下面的结论成立：;① a ? b (mod m)，d?m，d 0 ? a ? b (mod d)；;⑤ ac ? bc (mod m)，(c, m) = 1 ? a ? b (mod m);;⑥;四、一些整数的整除特征 ;(2) 7、11、13 的整除特征;(2) 7、11、13 的整除特征;Date;① 求出整数k，使ak ? 1 (mod m)；;例4　证明：若n是正整数，则13?42n + 1 ? 3 n + 2 。;例5 设n的十进制表示是 ;五、弃九法〔验算计算结果〕;例7. 求方程2x ? 3y = 1的正整数解。 ;习题讲解：;解：依次计算对模641的同余数;解：设a = 2m ? 1，;;§3.2 剩余类与完全剩余系 ;定理1 ;二、完全剩余系;完全剩余系举例：;2、完全剩余系的构造;检验：设{x1, x2, ?, xm}是模m的一个完全剩余系，;定理3 设m ? 1，a，b是整数，(a, m) = 1，{x1, x2, ?, xm};注意：;例1 设p ? 5是素数，a?{ 2, 3, ?, p ? 1}，则 在数列a，2a，3a，?，(p ? 1)a，pa中有且仅有 一个数b，满足 b ? 1 (mod p)；;例2 设A = {x1, x2, ?, xm}是模m的一个完全剩余系， 以{x}表示x的小数部分，证明：若(a, m) = 1，则 ;3、剩余系间的联系;定理4 设m1, m2?N，A?Z，(A, m1) = 1，;推论 若m1, m2?N，(m1, m2) = 1，当x1与x2分别通过 ;定理5 设mi?N，Ai?Z（1 ? i ? n），并且满足：;证： 由定理3只需证明，若xi?, xi???Xi，1 ? i ? n， ;例3 设m 0是偶数，{a1, a2, ?, am}与{b1, b2, ?, bm};例4 设mi?N（1 ? i ? n），则当xi通过模mi（1 ? i ? n） ;y = x2 ? m2x3 ? m2m3x4 ? ? ? m2?mkxk ? 1;三、与抽象代数的关系;Date;§3.3 简化剩余系与欧拉函数 ;定义2 对于正整数k，令函数?(k)的值等于模k的所有;注：由于选取方式的任意性，模m的简化剩余系;二、主要性质 ;定理2 设a是整数，(a, m) = 1，B = {x1, x2, ?, x?(m)} ;注：在定理2的条件下，若b是整数，集合;定理3 设m1, m2?N，(m1, m2) = 1，又设;若m1y ? m2x?R，则(m1y ? m2x, m1m2) = 1， ;推论 设m, n?N，(m, n) = 1，则?(mn) = ?(m)?(n)。;定理4 设n是正整数，p1, p2, ?, pk是它的全部素因数， ;注：由定理4可知，?(n) = 1的充要条件是n = 1或2。;例1 设整数n ? 2，证明： ;例2 设n?N，证明：;1) 若n是奇数，则?(4n) = 2?(n)；;的充要条件是n = 2k，k?N；;的充要条件???n = 2k3l，k, l?N；;4) 若6?n，则?(n) ;5) 若n ? 1与n ? 1都是素数，n 4，则?(n) ;例3 证明：若m, n?N，则?(mn) = (m, n)?([m, n])；;;§3.4欧拉定理 费马定理及其对循环小数的应用 ;一、两个基本定理;定理2(Fermat) 设p是素数， ;二、定理的应用举例;例2 设n是正整数，;例3 设{x1, x2, ?, x?(m)}是模m的简化剩余系， ;例4 设a，b，c，m是正整数，m 1，(b, m) = 1， ;例5 设n是正整数，记Fn = ;补充说明;例6 如果今天是星期一，再过101010天是星期几？;三、在分数与小数互化中的应用;定理3 有理数 ;定理3 有理数 ;定理4 设a与b是正整数，0 a b，(a, b) = 1， ;M = m110? ? 1 ? m210? ? 2 ? ? ? m?（0 ? mi ? 9，1 ? i ? ?）， ;由定理3有 ;证明：;证明：;Date;Date;§3.5　公开钥匙——RSA体制 ; 该算法于1977年由美国麻省理工学院mit (massachusetts institute of technology)的ronal rivest， adi shamir和len adleman三位年轻教授提出，并以三 人的姓氏rivest，shamir和adlernan命名为rsa算法。 该算法利