初等数论教案7.doc

第二节 剩余类与完全剩余系
第三节 缩系
一、剩余类与完全剩余系
由上一节我们知道，同余关系满足自反性、对称性、传递性，即对于整数集来说，同余是一个等价关系. 这样，可以按同余关系将所有的整数分类.
1、定义1 给定正整数m，对于每个整数i，0 £ i £ m - 1，称集合 Ki(m) = { n；n º i (mod m)，nÎZ }
是模m的一个剩余类.
显然，每个整数必定属于且仅属于某一个Ki(m)（0 £ i £ m - 1），而且，属于同一剩余类的任何两个整数对模m是同余的，不同剩余类中的任何两个整数对模m是不同余的.
例如，模 5的五个剩余类是
K0(5) = { L , -10, -5, 0 , 5, 10, L }，
K1(5) = { L , -9 , -4 , 1 , 6 , 11, L }，
K2(5) = { L , -8 , -3 , 2 , 7 , 12, L }，
K3(5) = { L , -7 , -2 , 3 , 8 , 13, L }，
K4(5) = { L , -6 , -1 , 4 , 9 , 14, L }.
2、定义2 设m是正整数，从模m的每一个剩余类中任取一个数xi（0 £ i £ m - 1），称集合{x0, x1, L,xm - 1}是模m的一个完全剩余系（或简称为完全系）.
由于xi的选取是任意的，所以模m的完全剩余系有无穷多个，通常称
(ⅰ) {0, 1, 2, L, m - 1}是模m的最小非负完全剩余系；
(ⅱ) 或

是模m的绝对最小完全剩余系.
例如，集合{0, 6, 7, 13, 24}是模5的一个完全剩余系，集合{0, 1, 2, 3, 4}是模5的最小非负完全剩余系.
3、定理1 整数集合A是模m的完全剩余系的充要条件是
(ⅰ) A中含有m个整数；
(ⅱ) A中任何两个整数对模m不同余.
4、定理2 设m ³ 1，a，b是整数，(a, m) = 1，{x1, x2, L, xm}是模m的一个完全剩余系，则{ax1 + b, ax2 + b, L, axm + b}也是模m的一个完全剩余系.
证明：由定理1，只需证明：若xi ¹ xj，则
axi + baxj + b (mod m). (1)
事实上，若
axi + b º axj + b (mod m)，
则
axi º axj (mod m)，
由此得到 xi º xj (mod m)，
因此xi = xj. 所以式(1)必定成立. 证毕
5、定理3 设m1, m2ÎN，AÎZ，(A, m1) = 1，又设
，
分别是模m1与模m2的完全剩余系，则
R = { Ax + m1y；xÎX，yÎY }
是模m1m2的一个完全剩余系.
证明：由定理1只需证明：若x ¢, x ¢¢ÎX，y ¢, y ¢¢ÎY，并且
Ax ¢ + m1y ¢ º Ax ¢¢ + m1y ¢¢ (mod m1m2)， (2)
则 x ¢ = x ¢¢，y ¢ = y ¢¢.
事实上，由第一节定理5及式(2)，有
Ax ¢ º Ax ¢¢ (mod m1) Þ x ¢ º x ¢¢ (mod m1) Þ x ¢ = x ¢¢，
再由式(2)，又推出
m1y ¢ º m1y ¢¢ (mod m2) Þ y ¢ º y ¢¢ (mod m2) Þ y ¢ = y ¢¢ .
推论 若m1, m2ÎN，(m1, m2) = 1，则当x1与x2分别通过模m1与模m2的完全剩余系时，m2x1 + m1x2通过模m1m2的完全剩余系.
6、定理4 设miÎN（1 £ i £ n），则当xi通过模mi（1 £ i £ n）的完全剩余系时，
x = x1 + m1x2 + m1m2x3 + L + m1m2Lmn - 1xn
通过模m1m2Lmn的完全剩余系.
证明：对n施行归纳法.
当n = 2时，由定理3知定理结论成立.
假设定理结论当n = k时成立，即当xi（2 £ i £ k + 1）分别通过模mi的完全剩余系时，
y = x2 + m2x3 + m2m3x4 + L + m2Lmkxk + 1
通过模m2m3Lmk + 1的完全剩余系. 由定理3，当x1通过模m1的完全剩余系，xi（2 £ i £ k + 1）通过模mi的完全剩余系时，
x1 + m1y = x1 + m1(x2 + m2x3 + L + m2Lmkxk + 1)
= x1 + m1x2 + m1m2x3 + L + m1m2Lmkxk + 1
通过模m1m2Lmk + 1的完全剩余系. 即定理结论对于n = k + 1也成立.
7、定理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 + L + Anxn
通过模m1m2Lmn的完全剩余系.
证明：由定理1只需证明：若xi¢, xi¢¢ÎXi，1 £ i £ n，则由
A1x1¢ + A2x2¢ + L + Anxn¢ º A1x1¢¢ + A2x2¢¢ + L + Anxn¢¢ (mod m1Lmn) (3)
可以得到xi¢ = xi¢¢，1 £ i £ n.
事实上，由条件(ⅲ)及式(3)易得，对于任意的i，1 £ i £ n，有
Aixi¢ º Aixi¢¢ (mod mi).
由此并利用条件(ⅱ)和第一节定理5推得
xi¢ º xi¢¢ (mod mi)，
因此xi¢ = xi¢¢.
例1 设A = {x1, x2, L, 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）
从而
.
例2 设p ³ 5是素数，aÎ{ 2, 3, L, p - 2 }，则在数列
a，2a，3a，L，(p - 1)a，pa (4)
中有且仅有一个数b，满足
b º 1 (mod p). (5)
此外，若b = ka，则k ¹ a，kÎ{2, 3, L, p - 2}.
解：因为(a, p) = 1，所以由定理2，式(4)中的数构成模p的一个完全剩余系，因此必有数b满足式(5).
设b = ka，那么
(ⅰ) k ¹ a，否则，b = a2 º 1 (mod p)，即p½(a + 1)(a - 1)，因此p½a - 1或p½a + 1，这与2 £ a £ p - 2矛盾；
(ⅱ) k ¹ 1，否则，b = 1×a º 1 (mod p)，这与2 £ a £ p - 2矛盾；
(ⅲ) k ¹ -1，否则，b = -a º 1 (mod p)，这与2 £ a £ p - 2矛盾.
若又有k ¢，2 £ k ¢ £ p - 2，使得b º k ¢a (mod p)，则
k ¢a º ka (mod p).
因(a, p) = 1，所以k º k ¢ (mod p)，从而p½k - k ¢，这是不可能的. 这证明了唯一性.
8、定理6 (Wilson定理) 设p是素数，则
(p - 1)! º -1 (mod p).
证：不妨设p5. 由例2容易推出对于2, 3, L, p - 2，中的每个整数a，都存在唯一的整数k，2 £ k £ p - 2，使得
ka º 1 (mod p). (6)
因此，整数2, 3, L, p - 2可以两两配对使得式(6)成立. 所以
2×3×L×(p - 2) º 1 (mod p)，
从而
1×2×3×L×(p - 2)(p - 1) º p - 1 º -1 (mod p).
例3 设m > 0是偶数，{a1, a2, L, am}与{b1, b2, L, bm}都是模m的完全剩余系，证明：{a1 + b1, a2 + b2, L, am + bm}不是模m的完全剩余系.
解：因为{1, 2, L, m}与{a1, a2, L, am}都是模m的完全剩余系，所以
(mod m). (7)
同理
(mod m). (8)
如果{a1 + b1, a2 + b2, L, am + bm}是模m的完全剩余系，那么也有
(mod m).
联合上式与式(7)和式(8)，得到
0(mod m)，
这是不可能的，所以{a1 + b1, a2 + b2, L, am + bm}不能是模m的完全剩余系.
二、缩系
在模m的完全剩余系中，与m互素的整数所成的集合有一些特殊的性质，我们下面对它们做些研究.
1、定义1 设R是模m的一个剩余类，若有aÎR，使得(a, m) = 1，则称R是模m的一个简化剩余类.
显然，若R是模的简化剩余类，则R中的每个整数都与m互素.
例如，模4的简化剩余类有两个：
R1(4) = { L, -7 , -3, 1 , 5 , 9 , L }，
R3(4) = { L, -5 , -1 , 3 , 7 , 11 , L }.
2、定义2 对于正整数k，令函数j(k)的值等于模k的所有简化剩余类的个数，称j(k)为Euler函数，或Euler—j函数.
例如，容易验证j(2) = 1，j(3) = 2，j(4) = 2，j(7) = 6.
显然，j(m)就是在m的一个完全剩余系中与m互素的整数的个数.
3、定义3 对于正整数m，从模m的每个简化剩余类中各取一个数xi，构成一个集合{x1, x2, L,xj(m)}，称为模m的一个简化剩余系（或简称为简化系或缩系）.
显然，由于选取方式的任意性，模m的简化剩余系有无穷多个.
例如，集合{9, -5, -3, -1}是模8的简化剩余系，集合{1, 3, 5, 7}也是模8的简化剩余系，通常称最小非负简化剩余系.
4、定理1 整数集合A是模m的简化剩余系的充要条件是
(ⅰ) A中含有j(m)个整数；
(ⅱ) A中的任何两个整数对模m不同余；
(ⅲ) A中的每个整数都与m互素.
5、定理2 设a是整数，(a, m) = 1，B = {x1, x2, L, xj(m)}是模m的简化剩余系，则集合A = {ax1, ax2, L, axj(m)}也是模m的一个缩系.
证明 ：显然，集合A中有j(m)个整数. 其次，由于(a, m) = 1，所以，对于任意的xi（1 £ i £ j(m)），xiÎB，有(axi, m) = (xi, m) = 1. 因此，A中的每一个数都与m互素. 最后，我们指出，A中的任何两个不同的整数对模m不同余. 事实上，若有x ¢, x ¢¢ÎB，使得
a x ¢ º ax ¢¢ (mod m)，
那么，因为(a, m) = 1，所以x ¢ º x ¢¢ (mod m)，于是x ¢ = x ¢¢. 由以上结论及定理1可知集合A是模m的一个缩系.
注：在定理2的条件下，若b是整数，集合
{ax1 + b, ax2 + b,, L, axj(m) + b}
不一定是模m的简化剩余系.例如，取m = 4，a = 1，b = 1，以及模4的简化剩余系{1, 3}.
6、定理3 设m1, m2ÎN，(m1, m2) = 1，又设

分别是模m1与m2的缩系，则
A = { m1y + m2x；xÎX，yÎY }
是模m1m2的缩系.
证明：若以X ¢与Y ¢分别表示模m1与m2的完全剩余系，使得X Ì X ¢，Y Ì Y ¢，则
A ¢ = { m1y + m2x；xÎX ¢，yÎY ¢ }
是模m1m2的完全剩余系. 因此只需证明A ¢中所有与m1m2互素的整数的集合R是集合A. 显然，A Í A’.
若m1y + m2xÎR，则(m1y + m2x, m1m2) = 1，所以(m1y + m2x, m1) = 1，于是 (m2x, m1) = 1，(x, m1) = 1，xÎX.
同理可得到yÎY，因此m1y + m2xÎA. 这说明R Í A.
另一方面，若m1y + m2xÎA，则xÎX，yÎY，即
(x, m1) = 1，(y, m2) = 1.
由此及(m1, m2) = 1得到
(m2x + m1y, m1) = (m2x, m1) = 1
以及
(m2x + m1y, m2) = (m1y, m2) = 1.
因为m1与m2互素，所以(m2x + m1y, m1m2) = 1，于是m2x + m1yÎR. 因此A Í R. 综合以上，得到A = R.
7、定理4 设m, nÎN，(m, n) = 1，则j(mn) = j(m)j(n).
证明：这是定理3的直接推论.
8、定理5 设n是正整数，p1, p2, L, pk是它的全部素因数，则
j(n) =.
证明：设n的标准分解式是n =，由定理4得到
j(n) =. (1)
对任意的素数p，j(pa)等于数列1, 2, L, pa中与pa（也就是与p）互素的整数的个数，因此
j(pa) = pa -，
将上式与式(1)联合，证明了定理.
由定理5可知，j(n) = 1的充要条件是n = 1或2.
例1 设整数n ³ 2，证明：
nj(n)，
即在数列1, 2, L, n中，与n互素的整数之和是nj(n).
解：设在1, 2, L, n中与n互素的j(n)个数是
a1, a2, L, aj(n)，(ai, n) = 1，1 £ ai £ n - 1，1 £ i £ j(n)，
则 (n - ai, n) = 1，1 £ n - ai £ n - 1，1 £ i £ j(n)，
因此，集合{a1, a2, L, aj(n)}与集合{n - a1, n - a2, L, n - aj(n)}是相同的，于是 a1 + a2 + L + aj(n) = (n - a1) + (n - a2) + L + (n - aj(n))，
2(a1 + a2 + L + aj(n)) = nj(n)，
因此 a1 + a2 + L + aj(n) =nj(n).
例2 设n是正整数，则
= n，
此处是对n的所有正约数求和.
解：将正整数1, 2, L, n按它们与整数n的最大的公约数分类，则
n =.
例3 设nÎN，证明：
(ⅰ) 若n是奇数，则j(4n) = 2j(n)；
(ⅱ) j(n) =的充要条件是n = 2k，kÎN；
(ⅲ) j(n) =的充要条件是n = 2k3l，k, lÎN；
(ⅳ) 若6½n，则j(n) £；
(ⅴ) 若n - 1与n + 1都是素数，n > 4，则j(n) £.
解： (ⅰ) 我们有
j(4n) = j(22n) = j(22)j(n) = 2j(n)；
(ⅱ) 若n = 2k，则
j(2k) =，
若j(n) =，设n = 2kn1，2n1，则由
= j(n) = j(2kn1) = j(2k)j(n1) =2k - 1j(n1)
=
推出j(n1) = n1，所以n1 = 1，即n = 2k；
(ⅲ) 若n = 2k3l，则
j(n) = j(2k)j(3l) =.
若j(n) =，设n = 2k3ln1，6n1，则由

推出j(n1) = n1，所以n1 = 1，即n = 2k3l；
(ⅳ) 设n = 2k3ln1，6n1，则
j(n) = j(2k)j(3l)j(n1) =；
(ⅴ) 因为n > 4，所以n - 1与n + 1都是奇素数，所以n是偶数.
因为n - 1 > 3，所以n - 1与n + 1都不等于3，当然不被3整除，所以3½n，因此6½n.再由上面已经证明的结论(ⅳ)，即可得到结论(ⅴ).
例4 证明：若m, nÎN，则j(mn) = (m, n)j([m, n])；
解：显然mn与[m, n]有相同的素因数，设它们是pi（1 £ i £ k），则

由此两式及mn = (m, n)[m, n]即可得证.
三、Euler定理与Fermat小定理
1、定理1(Euler) 设m是正整数，(a, m) = 1，则
aj(m) º 1 (mod m).
证明：由第三节定理2，设{x1, x2, L, xj(m)}是模m的一个简化剩余系，则{ax1, ax2, L, axj(m)}也是模m的简化剩余系，因此
ax1ax2Laxj(m) º x1x2, Lxj(m) (mod m)，
aj(m)x1x2Lxj(m) º x1x2, Lxj(m) (mod m). (1)
由于(x1x2Lxj(m), m) = 1，所以由式(1)得出
aj(m) º 1 (mod m).
2、定理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.
解 因为j(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)即可得出所需结论.
例2 设{x1, x2, L, xj(m)}是模m的简化剩余系，则
(x1x2Lxj(m))2 º 1 (mod m).
解 记P = x1x2Lxj(m)，则(P, m) = 1.又记
yi =，1 £ i £ j(m)，
则{y1, y2, L, yj(m)}也是模m的简化剩余系，因此
(mod m)，
再由Euler定理，推出
P2 º Pj(m) º 1 (mod m).
例3 设(a, m) = 1，d0是使
a d º 1 (mod m)
成立的最小正整数，则
(ⅰ) d0½j(m)；
(ⅱ) 对于任意的i，j，0 £ i, j £ d0 - 1，i ¹ j，有
a ia j (mod m). (3)
解： (ⅰ) 由Euler定理，d0 £ j(m)，因此，由带余数除法，有
j(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½j(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.
解：记d = (n, p - 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)，这就是结论(ⅱ).
若2n，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 = 2047分解因数.
解：由例5，若p½211 - 1，则p º 1 (mod 22)，即p只能在数列
23，45，67，L，22k + 1，L
中.逐个用其中的素数去除2047，得到
23½2047，2047 = 23×89.
例7 将235 - 1 = 34359738367分解因数.
解：由例5，若p½235 - 1，则p是25 - 1 = 31或27 - 1 = 127的素因数，或者p º 1 (mod 70).由于31和127是素数，并且
235 - 1 = 31×127×8727391，
所以，235 - 1的另外的素因数p只可能在数列
71，211，281，L (5)
中. 经检验，得到8727391 = 71×122921.
显然，122921的素因数也在31，127或者数列(5)中.简单的计算说明，122921不能被31和127整除，也不能被数列(5)中的不超过< 351的数整除，所以122921是素数，于是
235 - 1 = 31×127×71×122921.
例8 设n是正整数，记Fn =，则º 2 (mod Fn).
证：容易验证，当n £ 4时Fn是素数，所以，由Fermat定理可知结论显然成立.
当n ³ 5时，有n + 1 < 2n，2n + 1½.记 = k2n + 1，则

其中Q1与Q2是整数.上式即是º 2 (mod Fn).
注1：我们已经知道，F5是合数，因此，例8说明，一般地，Fermat定理的逆定理不成立. 即若有整数a，(a, n) = 1，使得
a n -1 º 1 (mod n)， (6)
并不能保证n是素数.
注2：设n是合数，若存在整数a，(a, n) = 1，使得式(6)成立，则称n是关于基数a的伪素数.
四、小结
五、作业
补充：证明Wilson定理的逆定理.
P60：ex3、ex6、ex9、ex12、ex14、ex17、ex18