秦韶定理Euler函数(离散数学).pptVIP

§5.4 秦九韶定理 Euler函数 §5.4.1 一次同余式组 秦九韶定理 定理5.4.1 设[m1,m2]为m1，m2的最低公倍数。则同余式组 x?a1 (mod m1) x?a2 (mod m2) ……………..(1) 在mod[m1,m2]下有唯一解的充要条件为 (m1,m2)|(a1-a2) ……………………….(2) 证明： 必要性。记m1，m2的最高公因数和最低公倍数分别为d，m，即d=(m1,m2)，m=[m1,m2]。若(1)有解x0，则 x0?a1(mod d)，x0?a2(mod d)，从而d|(a1-a2)。 充分性。若d|(a1-a2)，往证(1)在模m下有唯一解。 证明： 因为x?a1(mod m1)解的形式为 x=a1+m1y，代入(1)的二式中，得 a1+m1y?a2(mod m2)，即 m1y?a2-a1 (mod m2)。于是 (m1/d)y? (a2-a1)/d (mod m2/d)，且(m1/d,m2/d)=1。由上节的定理5.3.1知，关于模m2/d，y有唯一解y1。因此，x有解 x1=a1+m1y1。 若x’，x”都是(1)的解，则x’-x” ?0(mod m1)，x’-x” ?0(mod m2)。即 m1|(x’-x”)，m2|(x’-x”)。从而m|(x’-x”)，即 x’ ?x”(mod [m1,m2])。 定理5.4.2(秦九韶定理) 证明 : 先不讨论普遍情形而先求li，i=1,…,k，使适合下列特殊的合同式：  li?1(mod mi)，  li?0(mod mj)，j?i (4) 证明 : 证明 : 现在证唯一性。若x，x?都适合(3)，则x≡x?(mod mi)，i=1,…,k，故由§5.2定理5.2.4， x≡x? (mod m1…mk) 使用了构造性证明方法，先构造一些满足局部合同式的局部解，再把这些局部解合起来构造成整体解。 证明 : 这里的局部合同式就是(3)中每一个同余式，即构造yi，使得yi≡ai(mod mi)，而yi对其余合同式无影响，即yi≡0(mod mj)，j?i。特别构造li使得(4)成立。若li已得到，则令yi=aili，于是yi满足 yi≡ai(mod mi) yi≡0(mod mj) j?i 再令 x=y1+…+yk，则x为所求。 例5.4.1 求x满足同余式组：x≡1(mod 4)x≡2(mod 5)x≡3(mod 7) 解：因为模4，5，7两两互质，所以可以用上述定理的构造性证明过程求解。先求l1，l2，l3使得 例5.4.1 l1≡1(mod 4) l2≡1(mod 5) l3≡1(mod 7) l1≡0(mod 5) l2≡0(mod 4) l3≡0(mod 4) l1≡0(mod 7) l2≡0(mod 7) l3≡0(mod 5) 得l1=35c1，l2=28c2，l3=20c3，c1满足35c1≡1(mod 4)，即 3c1≡1(mod 4)，从而 c1≡3(mod 4)。故l1=105。同理得l2=56， l3=120。 于是 x=1?105+2?56+3?120=577≡17(mod 140)。 §5.4.2 一元高次同余式的化简 不讲 §5.4.3 剩余系遍历 Euler函数 在(5)中，让a1经过mod m1的一个完全剩余系变化，…，ak经过mod mk的一个完全剩余系统变化，这样，我们共得到m1…mk个x 。设 x?=a1?l1+…+ak?lk， x ?=a1?l1+…+ak?lk。 是两个这样的x 。 §5.4.3 剩余系遍历 Euler函数 §5.4.3 剩余系遍历 Euler函数 这就是说，我们得到的m1…mk个x mod m1…m k 在不同的剩余类内，但mod m1…mk只有m1…mk个剩余类，所以下面的定理成立。 定理5.4.4（遍历定理） Euler函数 设n是任意正整数，试看mod n的任意剩余类A。设a?A。若a和n互质，则A中任意数和n互质。此时我们称剩余类A和n互质。 事实上，若b?a(mod n)，则a=b+qn，倘若b和n 有一个大于1的公因数d，则d也是a的因数，因而是a和n的公因数，此为矛盾。可见，若A中有一个数和n互质，则其中所有的数都和n互质。故A 中的数或者都和n互质，或者都和n不互质。 Euler函数 和n互质的剩余类的个数记为?(n)，称为Euler(欧拉)函数。从和n互质的每一个剩余类中取出一个数，这样得到的?(n)个数便称之为作成mod n的一个简化剩余系。 显然，从mod n的一个完全剩余系中取出与