第十一讲-初等数论-2.pptVIP

皖西学院 数理系 初等 数论 最大公约数 gcd（最大公因子） Euclidean算法求两个正整数a和b的gcd。先令r0为a，r1为b，接着执行如下运算： 最大公约数 GCD递归定理：对任意非负整数a和任意正整数b，gcd(a, b) = gcd(b, a mod b)。 Extended-Euclidean 算法 定理：对于不完全为0的非负整数a，b，gcd（a，b）表示a，b的最大公约数d，必然存在整数对x，y，使得gcd（a，b）=d=ax+by。 例2 设A = {x1, x2, ?, xm}是模m的一个完全剩余系， 以{x}表示x的小数部分，证明：若(a, m) = 1，则 证： 当x通过模m的完全剩余系时，ax ? b也通过 模m的完全剩余系， 因此对于任意的i（1 ? i ? m），axi ? b一定且只与某个整数j（1 ? j ? m）同余， 即存在整数k，使得 axi ? b = km ? j，（1 ? j ? m） 3、剩余系间的联系 定理4 设m1, m2?N，A?Z，(A, m1) = 1， 分别是模m1与模m2的完全剩余系， 则 R = { Ax ? m1y：x?X，y?Y }是模m1m2的一个 完全剩余系。 推论 若m1, m2?N，(m1, m2) = 1，当x1与x2分别通过 模m1与模m2的完全剩余系时，则 m2x1 ? m1x2通过模m1m2的完全剩余系。 定理5 设mi?N，Ai?Z（1 ? i ? n），并且满足： ① (mi, mj) = 1，1 ? i, j ? n，i ? j； ② (Ai, mi) = 1，1 ? i ? n； ③ mi?Aj ，1 ? i, j ? n，i ? j 。 则当xi（1 ? i ? n）通过模mi的完全剩余系Xi时， y = A1x1 ? A2x2 ? ? ? Anxn 通过模m1m2?mn的 完全剩余系。 §3.3 简化剩余系与欧拉函数 一、基本概念 定义1 设R是模m的一个剩余类，若有a?R，使得(a, m) = 1，则称R是模m的一个简化剩余类。 即与模m互质的剩余类。 注：若R是模的简化剩余类，则R中的数都与m互素。 例如，模4的简化剩余类有两个： R1(4) = { ?, ?7 , ?3, 1 , 5 , 9 , ? }， R3(4) = { ?, ?5 , ?1 , 3 , 7 , 11 , ? }。 定义2 对于正整数k，令函数?(k)的值等于模k的所有 简化剩余类的个数，称?(k)为Euler函数。 容易验证：?(2) = 1，?(3) = 2，?(4) = 2，?(7) = 6。 注：?(m)就是在m的一个完全剩余系中与m互素的 整数的个数，且 定义3 对于正整数m，从模m的每个简化剩余类中 各取一个数xi，构成一个集合{x1, x2, ?,x?(m)}， 称为模m的一个简化剩余系（或简称为简化系）。 注：由于选取方式的任意性，模m的简化剩余系 有无穷多个。 例如，集合{9, ?5, ?3, ?1}是模8的简化剩余系； 集合{1, 3, 5, 7}也是模8的简化剩余系. 集合{1, 3, 5, 7}称为最小非负简化剩余系。 二、主要性质 定理1 整数集合A是模m的简化剩余系的充要条件是： ① A中含有?(m)个整数； ② A中的任何两个整数对模m不同余； ③ A中的每个整数都与m互素。 说明：简化剩余系是某个完全剩余系中的部分元素 构成的集合，故满足条件2； 由定义1易知满足条件3； 由定义3易知满足条件1。 定理2 设a是整数，(a, m) = 1，B = {x1, x2, ?, x?(m)} 是模m的简化剩余系，则集合 A = {ax1, ax2, ?, ax?(m)} 也是模m的简化剩余系。 注：在定理2的条件下，若b是整数，集合 {ax1 ? b, ax2 ? b,, ?, ax?(m) ? b} 不一定是模m的简化剩余系。 例如，取m = 4，a = 1，b = 1， 以及模4的简化剩余系{1, 3}。 但｛2，4｝不是模4的简化剩余系。 定理3 设m1, m2?N，(m1, m2) = 1，又设 分别是模m1与m2的简化剩余系， 则 A = { m1y ? m2x；x?X，y?Y } 是模m1m2的简化剩余系。 推论 设m, n?N，(m, n) = 1，则?(mn) = ?(m)?(n)。 注：由定理4可知，?(n) = 1的充要条件是n = 1或2。 考虑有重素因子和没有重素因子的情形。 注意：有重素因子时，上述不等式中等号不成立！ 定理4 设n是正整数，p1, p2, ?, pk是它的全部素因数， 例1