[第四节Euler定理.docVIP

第四节 Euler定理 本节中所介绍的Euler定理，在理论和应用两个方面都是很重要的。 定理1?Euler? 设m是正整数，(a, m) = 1，则 a??m) ? 1 (mod m)。 证明 由第三节定理2，设{x1, x2, ?, x?(m)}是模m的一个简化剩余系，则{ax1, ax2, ?, ax?(m)}也是模m的简化剩余系，因此 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)。 证毕。 定理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)。 证毕。 例1 设n是正整数，则51n ? 2n ? 3n ? 4n的充要条件是4?n。 解 因为?(5) = 4，所以，由定理2 k4 ? 1 (mod 5)，1 ? k ? 4。? 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)即可得出所需结论。 例2 设{x1, x2, ?, x?(m)}是模m的简化剩余系，则 (x1x2?x?(m))2 ? 1 (mod m)。 ?x?(m)，则(P, m) = 1。 yi =，1 ? i ? ?(m)， 则{y1, y2, ?, y?(m)}也是模m的简化剩余系，因此 (mod m)， 再由Euler定理，推出 P2 ? P?(m) ? 1 (mod m)。 例3 设(a, m) = 1，d0是使 a d ? 1 (mod m) 成立的最小正整数，则 (ⅰ) d0??(m)； (ⅱ) 对于任意的i，j，0 ? i, j ? d0 ? 1，i ? j，有 a ia j (mod m)。 (3) 解 (ⅰ) 由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)； (ⅱ) 若式(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)必成立。 例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。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)。 5 设p是素数，p?bn ? 1，n?N，则下面的两个结论中至少有一个成立： (ⅰ) p?bd ? 1对于n的某个因数d n成立； (ⅱ) p ? 1 ( mod n )。 2n，p 2，则(ⅱ)中的mod n可以改为mod 2n。 ? 1)，由b n ? 1，b p ? 1 ? 1 (mod p)，及例题4，有 b d ? 1 (mod p)。 若d n，则结论(ⅰ)得证。 若d = n，则n?p ? 1，即p ? 1 (mod n)，这就是结论(ⅱ)。 n，p 2，则p ?1 (mod 2)。由此及结论(ⅱ)，并利用同余的基本性质，得到p ? 1 (mod 2n)。 注：例5提供了一个求素因数的方法，就是说，整数bn ? 1的素因数p，是bd ? 1（当d?n时）的素因数，或者是形如kn ? 1的数（当2n，p 2时，是形如2kn ? 1的数)。 例6 将211 ? 1