第三章--同余-4.pptVIP

第三章 同 余 同余是数论中的一个基本概念。本章除介绍同余的基础知识外，还要介绍它的一些应用。 第四节 Euler定理 本节中所介绍的Euler定理，在理论和应用两个方面都是很重要的。 定理1 ?Euler? 设m是正整数，(a, m) = 1，则 a??m) ? 1 (mod m)。 证明 由第三节定理2，设{x1, x2, ?, x?(m)}是模m的一个简化剩余系，则{ax1, ax2, ?, ax?(m)}也是模m的简化剩余系，因此 第四节 Euler定理 ax1ax2?ax?(m) ? x1x2, ?x?(m) (mod m)， a?(m)x1x2?x?(m) ? x1x2, ?x?(m) (mod m). (1) 由于(x1x2?x?(m), m) = 1，所以由式(1)得出 a?(m) ? 1 (mod m)。 证毕。 第四节 Euler定理 定理2(Fermat) 设p是素数，则对于任意的整数a，有 a p ? a (mod p)。 证明 若(a, p) ? 1，则由定理1得到 a p ? 1 ? 1 (mod p) ? a p ? a (mod p)。 若(a, p) 1，则p?a，所以 a p ? 0 ? a (mod p)。 证毕。 第四节 Euler定理 例1 设n是正整数，则5 1n ? 2n ? 3n ? 4n的充要条件是4?n。 证明 因为?(5) = 4，所以，由定理2 k4 ? 1 (mod 5)，1 ? k ? 4。 因此，若n = 4q ? r，0 ? r ? 3，则 1n ? 2n ? 3n ? 4n ? 1r ? 2r ? 3r ? 4r ? 1r ? 2r ? (?2)r ? (?1)r (mod 5)， (2) 用r = 0，1，2，3，4分别代入式(2)即可得出所需结论。 第四节 Euler定理 例2 设{x1, x2, ?, x?(m)}是模m的简化剩余系,则 (x1x2?x?(m))2 ? 1 (mod m)。 证明 记P = x1x2?x?(m)，则(P, m) = 1。又记 则{y1, y2,?, y?(m)}也是模m的简化剩余系, 因此 再由Euler定理, 推出 P2 ? P?(m) ? 1 (mod m). 第四节 Euler定理 例3 设(a, m) = 1，d0是使 a d ? 1 (mod m) 成立的最小正整数，则 (ⅰ) d0??(m)； (ⅱ) 对于任意的i, j, 0? i, j? d0?1, i ? j,有 a i a j (mod m). (3) 第四节 Euler定理 证明 (ⅰ) 由Euler定理，d0 ? ?(m)，因此，由带余数除法，有 ?(m) = qd0 ? r，q?Z，q 0，0 ? r d0。 因此，由上式及d0的定义，利用定理1，我们得到 1 ?(mod m)， 即整数r满足 a r ? 1 (mod m)，0 ? r d0 。 由d0的定义可知必是r = 0，即d0??(m)； 第四节 Euler定理 (ⅱ) 若式(3)不成立, 则存在i, j，0? i, j ?d0? 1, i ? j，使得 a i ? a j (mod m)。 不妨设i j。因为(a, m) = 1，所以 ai ? j ? 0 (mod m)，0 i ? j d0。 这与d0的定义矛盾，所以式(3)必成立。 第四节 Euler定理 例4 设a，b，c，m是正整数, m 1, (b, m) = 1, 并且 b a ? 1 (mod m)，b c ? 1 (mod m)， (4) 记d = (a, c)，则bd ? 1 (mod m)。 证明 利用辗转相除法可以求出整数x，y，使得ax ? cy = d，显然xy 0。 第四节 Euler定理 若x 0，y 0，由式(4)知 1 ? b ax = b db ?cy = b d(b c) ?y ? b d (mod m)。 若x 0，y 0，由式(4)知 1 ? b cy = b db ?ax = b d(ba) ?x ? b d (mod m)。 第四节 Euler定理 例5 设p是素数，p?bn ? 1，n?N，则下面的两个结论中