数学竞赛辅导讲座：同余(4)

2010年中学数学竞赛辅导讲座(经典竞赛辅导资料)

都是模6的简化剩余类.

由此定义，不难得到：

定理三:a1,a2, ,a (m)是模m的简化剩余系 (ai,m) 1,且aiaj(modm)(i j,i,j 1,2, (m)). 定理四：在模m的一个完全剩余系中，取出所有与m互质的数组成的数组，就是一个模m的简化剩余系.

这两个定理，前者是简化剩余系的判别方法，后者是它的构造方法.显然，模m的简化剩余系有无穷多个，但常用的是“最小简化剩余系”，即由1，2， ，m－1中与m互质的那些数组成的数组.由定理不难证得简化剩余系的如下性质定理.

定理五：设a1,a2, ,a (m)是模m的简化剩余系.若（k,m）=1，则ka1,ka2, ,ka (m)也是模m的简化剩余系.

下面介绍两个有关欧拉函数的重要结论.其证明略.

定理六：（欧拉定理）若（a,m）=1，则a (m) 1(modm)

特别地，（费马小定理）若m=p为质数，，则ap 1 1(modp).

定理七：（威尔逊定理）设p素数，则（p－1）！ 1(modp).

定理八：（欧拉函数值计算公式）令m的标准分解式为

m p11p22 pkk，

则 (m) m (1

i 1k 1 ).pi

例如，30=2·3·5，则 (30) 30(1 )(1 )(1 ) 8.

读者应认识到：由于任何整数都属于模m的某一剩余类，所以，在研究某些整数性质时，选取适当的（模）m，然后在模m的每个剩余类中取一个“代表数”（即组成一个完全剩余系），当弄清了这些代表数的性质后，就可弄清对应的剩余类中所有数的性质，进而弄清全体整数的性质，这就是引入剩余类和完全剩余系的目的.

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新IT计算机数学竞赛辅导讲座：同余(4)全文阅读和word下载服务。