人教版B版高中数学选修4 6(B版)剩余系和欧拉函数课件

剩余系和欧拉函数剩余系和欧拉函数一、基本概念定义1设R是模m的一个剩余类，若有aR，使得(a,m)=1，则称R是模m的一个简化剩余类。即与模m互质的剩余类。

注：若R是模的简化剩余类，则R中的数都与m互素。例如，模4的简化剩余类有两个：R1(4)={,7,3,1,5,9,}，R3(4)={,5,1,3,7,11,}。一、基本概念定义1设R是模m的一个剩余类，若有aR，使定义2对于正整数k，令函数(k)的值等于模k的所有简化剩余类的个数，称(k)为Euler函数。容易验证：(2)=1，(3)=2，(4)=2，(7)=6。注：(m)就是在m的一个完全剩余系中与m互素的

整数的个数，且定义3对于正整数m，从模m的每个简化剩余类中

各取一个数xi，构成一个集合{x1,x2,,x(m)}，

称为模m的一个简化剩余系（或简称为简化系）。

定义2对于正整数k，令函数(k)的值等于模k的所有简化注：由于选取方式的任意性，模m的简化剩余系有无穷多个。例如，集合{9,5,3,1}是模8的简化剩余系；

集合{1,3,5,7}也是模8的简化剩余系.集合{1,3,5,7}称为最小非负简化剩余系。注：由于选取方式的任意性，模m的简化剩余系有无穷多个。例如，二、主要性质定理1整数集合A是模m的简化剩余系的充要条件是：①A中含有(m)个整数；②A中的任何两个整数对模m不同余；③A中的每个整数都与m互素。说明：简化剩余系是某个完全剩余系中的部分元素构成的集合，故满足条件2；

由定义1易知满足条件3；由定义3易知满足条件1。二、主要性质定理1整数集合A是模m的简化剩余系的充要条定理2设a是整数，(a,m)=1，B={x1,x2,,x(m)}

是模m的简化剩余系，则集合

A={ax1,ax2,,ax(m)}

也是模m的简化剩余系。证明显然，集合A中有(m)个整数。

由于(a,m)=1，

对于任意的xi（1

i

(m)），xiB，

有(axi,m)=(xi,m)=1。

故A中的每一个数都与m互素。

而且，A中的任何两个不同的整数对模m不同余。

因为，若有x

,x

B，使得ax

ax

(modm)，那么，

x

x

(modm)，

于是x

=x

。

由以上结论及定理1可知集合A是模m的一个简化系。

定理2设a是整数，(a,m)=1，B={x注：在定理2的条件下，若b是整数，集合{ax1

b,ax2

b,,,ax(m)

b}不一定是模m的简化剩余系。

例如，取m=4，a=1，b=1，

以及模4的简化剩余系{1,3}。但｛2，4｝不是模4的简化剩余系。注：在定理2的条件下，若b是整数，集合{ax1b,a定理3设m1,m2N，(m1,m2)=1，又设分别是模m1与m2的简化剩余系，

则

A={m1y

m2x；xX，yY}是模m1m2的简化剩余系。证明由第二节定理3推论可知，若以X

与Y

分别表示

模m1与m2的完全剩余系，使得X

X

，Y

Y

，

则A

={m1y

m2x；xX

，yY

}是模m1m2的完全剩余系。

因此只需证明A

中所有与m1m2互素的整数的集合R

即模m1m2的简化剩余系是集合A。

定理3设m1,m2N，(m1,m2)=1，若m1y

m2xR，则(m1y

m2x,m1m2)=1，

所以(m1y

m2x,m1)=1，

于是

(m2x,m1)=1，(x,m1)=1，xX。同理可得到yY，因此m1y

m2xA。

这说明R

A。

另一方面，若m1y

m2xA，则xX，yY，

即

(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

m1yR。因此A

R。

从而A=R。

若m1ym2xR，则(m1ym2x,m1m2推论设m,nN，(m,n)=1，则(mn)=(m)(n)。证由定理3知，若x,y分别通过m,n的简化剩余系，

则my

nx通过mn的简化剩余系，

即有my

nx通过(mn)个整数。

另一方面，x〔nx〕通过(m)个整数，

y〔my〕通过(n)个整数,

从而my

nx通过(m)(n)个整数。故有(mn)=(m)(n)。注：可以推广到多个两两互质数的情形。推论设m,nN，(m,n)=1，则(mn)定理4设n是正整数，p1,p2,,pk是它的全部素因数，

证设n的标准分解式是

由定理3推论得到对任意的素数p，

(p)等于数列1,2,

,p中与p互素的整数的个数，

从而定理得证。定理4设n是正整数，p1,p2,,pk是它的全部注：由定理4可知，(n)=1的充要条件是n=1或2。考虑有重素因子和没有重素因子的情形。

三、应用举例注意：有重素因子时，上述不等式中等号不成立！注：由定理4可知，(n)=1的充要条件是n=1或2例1设整数n2，证明：

即在数列1,2,,n中，与n互素的整数之和是

证设在1,2,,n中与n互素的个数是(n)，a1,a2,,a(n)，(ai,n)=1，1

ai

n1，1

i

(n)，则(n

ai,n)=1，1

n

ai

n1，1

i

(n)，因此，集合{a1,a2,,a(n)}故a1

a2

a(n)=(n

a1)

(n

a2)

(n

a(n))，从而，2(a1

a2

a(n))=n(n)，因此a1

a2

a(n)

与集合{n

a1,n

a2,,n

a(n)}是相同的，例1设整数n2，证明：即在数列1,2,,例2设nN，证明：1)若n是奇数，则(4n)=2(n)；的充要条件是n=2k，kN；的充要条件是n=2k3l，k,lN；4)若6n，则(n)

5)若n

1与n1都是素数，n>4，则(n)

例2设nN，证明：1)若n是奇数，则(4n)=1)若n是奇数，则(4n)=2(n)；(4n)=(22n)=(22)(n)=2(n)〔TH4〕1)若n是奇数，则(4n)=2(n)；(4n)的充要条件是n=2k，kN；若n=2k，

若(n)=

设n=2kn1，

由(n)=(2kn1)=(2k)(n1)

=2k

1(n1)

所以n1=1，即n=2k；的充要条件是n=2k，kN；若n=2k，若(n的充要条件是n=2k3l，k,lN；设n=2k3ln1，

所以n1=1，即n=2k3l；若n=2k3l，则(n)=(2k)(3l)的充要条件是n=2k3l，k,lN；设n=2k4)若6n，则(n)

设n=2k3ln1，

则(n)=(2k)(3l)(n1)

4)若6n，则(n)设n=2k3ln1，5)若n

1与n1都是素数，n>4，则(n)

因为n>4，且n

1与n1都是奇素数，

所以n是偶数，且n

1>3.所以n

1与n1都不等于3，所以3n，由结论4，也不能被3整除，因此6n。即可得到结论5。若6n，则(n)

5)若n1与n1都是素数，n>4，则(n例3证明：若m,nN，则(mn)=(m,n)([m,n])；证：显然mn与[m,n]有相同的素因数，

设它们是pi（1

i

k），则由此两式及mn=(m,n)[m,n]即可得证。例3证明：若m,nN，则(mn)=(m,n)剩余系和欧拉函数剩余系和欧拉函数一、基本概念定义1设R是模m的一个剩余类，若有aR，使得(a,m)=1，则称R是模m的一个简化剩余类。即与模m互质的剩余类。

注：若R是模的简化剩余类，则R中的数都与m互素。例如，模4的简化剩余类有两个：R1(4)={,7,3,1,5,9,}，R3(4)={,5,1,3,7,11,}。一、基本概念定义1设R是模m的一个剩余类，若有aR，使定义2对于正整数k，令函数(k)的值等于模k的所有简化剩余类的个数，称(k)为Euler函数。容易验证：(2)=1，(3)=2，(4)=2，(7)=6。注：(m)就是在m的一个完全剩余系中与m互素的

整数的个数，且定义3对于正整数m，从模m的每个简化剩余类中

各取一个数xi，构成一个集合{x1,x2,,x(m)}，

称为模m的一个简化剩余系（或简称为简化系）。

定义2对于正整数k，令函数(k)的值等于模k的所有简化注：由于选取方式的任意性，模m的简化剩余系有无穷多个。例如，集合{9,5,3,1}是模8的简化剩余系；

集合{1,3,5,7}也是模8的简化剩余系.集合{1,3,5,7}称为最小非负简化剩余系。注：由于选取方式的任意性，模m的简化剩余系有无穷多个。例如，二、主要性质定理1整数集合A是模m的简化剩余系的充要条件是：①A中含有(m)个整数；②A中的任何两个整数对模m不同余；③A中的每个整数都与m互素。说明：简化剩余系是某个完全剩余系中的部分元素构成的集合，故满足条件2；

由定义1易知满足条件3；由定义3易知满足条件1。二、主要性质定理1整数集合A是模m的简化剩余系的充要条定理2设a是整数，(a,m)=1，B={x1,x2,,x(m)}

是模m的简化剩余系，则集合

A={ax1,ax2,,ax(m)}

也是模m的简化剩余系。证明显然，集合A中有(m)个整数。

由于(a,m)=1，

对于任意的xi（1

i

(m)），xiB，

有(axi,m)=(xi,m)=1。

故A中的每一个数都与m互素。

而且，A中的任何两个不同的整数对模m不同余。

因为，若有x

,x

B，使得ax

ax

(modm)，那么，

x

x

(modm)，

于是x

=x

。

由以上结论及定理1可知集合A是模m的一个简化系。

定理2设a是整数，(a,m)=1，B={x注：在定理2的条件下，若b是整数，集合{ax1

b,ax2

b,,,ax(m)

b}不一定是模m的简化剩余系。

例如，取m=4，a=1，b=1，

以及模4的简化剩余系{1,3}。但｛2，4｝不是模4的简化剩余系。注：在定理2的条件下，若b是整数，集合{ax1b,a定理3设m1,m2N，(m1,m2)=1，又设分别是模m1与m2的简化剩余系，

则

A={m1y

m2x；xX，yY}是模m1m2的简化剩余系。证明由第二节定理3推论可知，若以X

与Y

分别表示

模m1与m2的完全剩余系，使得X

X

，Y

Y

，

则A

={m1y

m2x；xX

，yY

}是模m1m2的完全剩余系。

因此只需证明A

中所有与m1m2互素的整数的集合R

即模m1m2的简化剩余系是集合A。

定理3设m1,m2N，(m1,m2)=1，若m1y

m2xR，则(m1y

m2x,m1m2)=1，

所以(m1y

m2x,m1)=1，

于是

(m2x,m1)=1，(x,m1)=1，xX。同理可得到yY，因此m1y

m2xA。

这说明R

A。

另一方面，若m1y

m2xA，则xX，yY，

即

(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

m1yR。因此A

R。

从而A=R。

若m1ym2xR，则(m1ym2x,m1m2推论设m,nN，(m,n)=1，则(mn)=(m)(n)。证由定理3知，若x,y分别通过m,n的简化剩余系，

则my

nx通过mn的简化剩余系，

即有my

nx通过(mn)个整数。

另一方面，x〔nx〕通过(m)个整数，

y〔my〕通过(n)个整数,

从而my

nx通过(m)(n)个整数。故有(mn)=(m)(n)。注：可以推广到多个两两互质数的情形。推论设m,nN，(m,n)=1，则(mn)定理4设n是正整数，p1,p2,,pk是它的全部素因数，

证设n的标准分解式是

由定理3推论得到对任意的素数p，

(p)等于数列1,2,

,p中与p互素的整数的个数，

从而定理得证。定理4设n是正整数，p1,p2,,pk是它的全部注：由定理4可知，(n)=1的充要条件是n=1或2。考虑有重素因子和没有重素因子的情形。

三、应用举例注意：有重素因子时，上述不等式中等号不成立！注：由定理4可知，(n)=1的充要条件是n=1或2例1设整数n2，证明：

即在数列1,2,,n中，与n互素的整数之和是

证设在1,2,,n中与n互素的个数是(n)，a1,a2,,a(n)，(ai,n)=1，1

ai

n1，1

i

(n)，则(n

ai,n)=1，1

n

ai

n1，1

i

(n)，因此，集合{a1,a2,,a(n)}故a1

a2

a(n)=(n

a1)

(n

a2)

(n

a(n))，从而，2(a1

a2

a(n))=n(n)，因此a1

a2

a(n)

与集合{n

a1,n

a2,,n

a(n)}是相同的，例1设整数n2，证明：即在数列1,2,,例2设nN，证明：1)若n是奇数，则(4n)=2(n)；的充要条件是n=2k，kN；的充要条件是n=2k3l，k,lN；4)若6n，则(n)

5)若n

1与n1都是素数，n>4，则(n)

例2设nN，证明：1)若n是奇数，则(4n)=1)若n是奇数