初等数论第二章同余第三节简化剩余系在模m的完全剩余系中，与m互素的整数所成的集合有一些特殊的性质，我们要在这一节中对它们做些研究。

定义1 设R是模m的一个剩余类，若有a∈R，使得(a, m) = 1，则称R是模m的一个简化剩余类。

显然，若R是模的简化剩余类，则R中的每个整数都与m互素。

例如，模4的简化剩余类有两个：R1(4) = { , -7 , -3, 1 , 5 , 9 , }，R3(4) = { , -5 , -1 , 3 , 7 , 11 , }。

定义2对于正整数k，令函数ϕ(k)的值等于模k的所有简化剩余类的个数，称ϕ(k)为Eule r函数，或Eule r—ϕ函数。

例如，容易验证ϕ(2) = 1，ϕ(3) = 2，ϕ(4) = 2，ϕ(7) = 6。

显然，ϕ(m)就是在m的一个完全剩余系中与m互素的整数的个数。

定义3对于正整数m，从模m的每个简化剩余类中各取一个数x i，构成一个集合{x1, x2, ,xϕ(m)}，称为模m的一个简化剩余系（或简称为简化系）。

显然，由于选取方式的任意性，模m的简化剩余系有无穷多个。

例如，集合{9, -5, -3, -1}是模8的简化剩余系，集合{1, 3, 5, 7}也是模8的简化剩余系，通常称最小非负简化剩余系。

定理1整数集合A是模m的简化剩余系的充要条件是(ⅰ) A中含有ϕ(m)个整数；(ⅱ) A中的任何两个整数对模m不同余；(ⅲ) A中的每个整数都与m互素。

证明留作习题。

定理2设a是整数，(a, m) = 1，B = {x1, x2, , xϕ(m)}是模m的简化剩余系，则集合A = {ax1, ax2, , axϕ(m)}也是模m的简化剩余系。

证明显然，集合A中有ϕ(m)个整数。

其次，由于(a, m) = 1，所以，对于任意的x i（1 ≤i≤ϕ(m)），x i∈B，有(ax i, m) = (x i, 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 是整数，集合{ax 1 + b , ax 2 + b ,, , ax ϕ(m ) + b }不一定是模m 的简化剩余系。

例如，取m = 4，a = 1，b = 1，以及模4的简化剩余系{1, 3}。

定理3 设m 1, m 2∈N ，(m 1, m 2) = 1，又设},,,{},,,{)(21)(2121m m y y y Y x x x X ϕϕ ==与分别是模m 1与m 2的简化剩余系，则A = { m 1y + m 2x ；x ∈X ，y ∈Y }是模m 1m 2的简化剩余系。

证明 由第二节定理3推论可知，若以X '与Y '分别表示模m 1与m 2的完全剩余系，使得X ⊂ X '，Y ⊂ Y '，则A ' = { m 1y + m 2x ；x ∈X '，y ∈Y ' }是模m 1m 2的完全剩余系。

因此只需证明A '中所有与m 1m 2互素的整数的集合R 是集合A 。

显然，A ⊆ A ’。

若m 1y + m 2x ∈R ，则(m 1y + m 2x , m 1m 2) = 1，所以(m 1y + m 2x , m 1) = 1，于是(m 2x , m 1) = 1，(x , m 1) = 1，x ∈X 。

同理可得到y ∈Y ，因此m 1y + m 2x ∈A 。

这说明R ⊆ A 。

另一方面，若m 1y + m 2x ∈A ，则x ∈X ，y ∈Y ，即(x , m 1) = 1，(y , m 2) = 1。

由此及(m 1, m 2) = 1得到(m 2x + m 1y , m 1) = (m 2x , m 1) = 1以及(m 2x + m 1y , m 2) = (m 1y , m 2) = 1。

因为m 1与m 2互素，所以(m 2x + m 1y , m 1m 2) = 1，于是m 2x + m 1y ∈R 。

因此A ⊆ R 。

综合以上，得到A = R 。

证毕。

定理4 设m , n ∈N ，(m , n ) = 1，则ϕ(mn ) = ϕ(m )ϕ(n )。

证明 这是定理3的直接推论。

证毕。

定理5 设n 是正整数，p 1, p 2, , p k 是它的全部素因数，则ϕ(n ) =∏-=---np k p n p p p n |21)()())((11111111 。

证明 设n 的标准分解式是n =∏=ki i i p 1α，由定理4得到ϕ(n ) =∏=ki i i p 1)(αϕ。

(1)对任意的素数p ，ϕ(p α)等于数列1, 2, , p α中与p α（也就是与p ）互素的整数的个数，因此ϕ(p α) = p α -)(][111p p p p p p -=-=-αααα， 将上式与式(1)联合，证明了定理。

证毕。

由定理5可知，ϕ(n ) = 1的充要条件是n = 1或2。

例1 设整数n ≥ 2，证明：∑=≤≤=1),(121n i n i i n ϕ(n )， 即在数列1, 2, , n 中，与n 互素的整数之和是21n ϕ(n )。

解 设在1, 2, , n 中与n 互素的ϕ(n )个数是a 1, a 2, , a ϕ(n )，(a i , n ) = 1，1 ≤ a i ≤ n - 1，1 ≤ i ≤ ϕ(n )，则(n - a i , n ) = 1，1 ≤ n - a i ≤ n - 1，1 ≤ i ≤ ϕ(n )，因此，集合{a 1, a 2, , a ϕ(n )}与集合{n - a 1, n - a 2, , n - a ϕ(n )}是相同的，于是a 1 + a 2 + + a ϕ(n ) = (n - a 1) + (n - a 2) + + (n - a ϕ(n ))，2(a 1 + a 2 + + a ϕ(n )) = n ϕ(n )，因此a 1 + a 2 + + a ϕ(n ) =21n ϕ(n )。

例2 设n 是正整数，则 ∑nd d |)(ϕ= n ，此处∑nd |是对n 的所有正约数求和。

解 将正整数1, 2, , n 按它们与整数n 的最大的公约数分类，则n =∑∑∑∑∑∑∑=≤≤=≤≤=====n i n d n i dn i n d d n d i d n d i n d nd d d n 1|1),(|11),(||)()(111ϕϕ。

例3 设n ∈N ，证明：(ⅰ) 若n 是奇数，则ϕ(4n ) = 2ϕ(n )；(ⅱ) ϕ(n ) =n 21的充要条件是n = 2k ，k ∈N ； (ⅲ) ϕ(n ) =n 31的充要条件是n = 2k 3l ，k , l ∈N ； (ⅳ) 若6∣n ，则ϕ(n ) ≤n 31； (ⅴ) 若n - 1与n + 1都是素数，n > 4，则ϕ(n ) ≤n 31。

解 (ⅰ) 我们有ϕ(4n ) = ϕ(22n ) = ϕ(22)ϕ(n ) = 2ϕ(n )；(ⅱ) 若n = 2k ，则ϕ(2k ) =n k k 21221121)(==--， 若ϕ(n ) =n 21，设n = 2k n 1，2|/n 1，则由 n 21= ϕ(n ) = ϕ(2k n 1) = ϕ(2k )ϕ(n 1) =2k - 1ϕ(n 1) =11111)(21)(221n n n n n n k ϕϕ= 推出ϕ(n 1) = n 1，所以n 1 = 1，即n = 2k ；(ⅲ) 若n = 2k 3l ，则ϕ(n ) = ϕ(2k )ϕ(3l ) =n l k 3131132112)()(=--。

若ϕ(n ) =n 31，设n = 2k 3l n 1，6|/n 1，则由 1111)(31)()3()2()32()(31n n n n n n n l k l k ϕϕϕϕϕϕ==== 推出ϕ(n 1) = n 1，所以n 1 = 1，即n = 2k 3l ；(ⅳ) 设n = 2k 3l n 1，6|/n 1，则ϕ(n ) = ϕ(2k )ϕ(3l )ϕ(n 1) =n n n l k l k 313231)(323111=≤ϕ； (ⅴ) 因为n > 4，所以n - 1与n + 1都是奇素数，所以n 是偶数。

因为n - 1 > 3，所以n - 1与n + 1都不等于3，当然不被3整除，所以3∣n ，因此6∣n 。

再由上面已经证明的结论(ⅳ)，即可得到结论(ⅴ)。

例4 证明：若m , n ∈N ，则ϕ(mn ) = (m , n )ϕ([m , n ])；解 显然mn 与[m , n ]有相同的素因数，设它们是p i （1 ≤ i ≤ k ），则。

，)())(()())((111111],[]),([111111)(2121kk p p p n m n m p p p mn mn ---=---= ϕϕ 由此两式及mn = (m , n )[m , n ]即可得证。

习 题 三1. 证明定理1。

2. 设m 1, m 2, , m n 是两两互素的正整数，x i 分别通过模m i 的简化剩余系（1 ≤ i ≤ n ），m = m 1m 2 m n ，M i =i m m ，则 M 1x 1 + M 2x 2 + + M n x n通过模m 的简化剩余系。

3. 设m > 1，(a , m ) = 1，x 1, x 2, ⋯, x ϕ(m )是模m 的简化剩余系，证明：∑==)(1)(21}{m i i m m ax ϕϕ。

其中{x }表示x 的小数部分。

4. 设m 与n 是正整数，证明：ϕ(mn )ϕ((m , n )) = (m , n )ϕ(m )ϕ(n )。

5. 设a ，b 是任意给定的正整数，证明：存在无穷多对正整数m 与n ，使得a ϕ(m ) =b ϕ(n )。

6. 设n 是正整数，证明：(ⅰ) ϕ(n ) >n 21； (ⅱ) 若n 是合数，则ϕ(n ) ≤ n -n 。