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

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

等都是模的4的一个完全剩余系.

显然，模m的完全剩余系有无穷多个.但最常用的是下面两种：

（1）非负数最小完全剩余系：0，1，2， ，m－1；

（2）绝对值最小完全剩余系：它随m的奇偶性不同而略有区别.

当m 2k 1时,为 k, (k 1), , 1,0,1, ,(k 1),k.（对称式）

当m 2k时,为 (k 1), (k 2), , 1,0,1,(k 1),k.或 k, (k 1), , 1,0,1, ,(k 1). 由定义不难得到如下判别完全剩余系的方法：

定理一：m个整数a1,a2, ,am是模m的一个完系 当i j时,aiaj(modm) 定理二：设（b,m）=1，c为任意整数.若a1,a2, ,an为一个完系，则ba1 c,ba2 c, ,bam c也是模m的一个完全剩余系.

特别地，任意m个连续整数构成模m的一个完全剩余系.

【证明】只需证明：当i j时,bai c baj c(modm).而这可用反证法得证.下略. 设m为一正整数，由于在0，1， ，m－1中与m互质的数的个数是由m惟一确定的一个正整数，因此，可给出如下定义.

定义四：m为一正整数，把0，1， ，m－1与m互质的数的个数叫做m的欧拉函数，记为 (m).

显然， (m)的定义域是正整数N*，前n个值为：

(1) 0, (2) 1, (3) 2, (4) 2, (5) 4, (6) 2, (7) 6, ,当m=p为质数时， (p) p 1.

设k是模的一个剩余类.若a、b∈k，则a b(modm).于是由性质9知，（a,m）=（b,m）.因此，若（a,m）=1，则k中的任一数均与m互质.这样，又可给出如下定义

定义五：如果一个模m的剩余类kr中任一数与m互质，则称kr是与模m互质的剩余类；在与模m互质的每个剩余类中任取一个数（共 (m)个）所组成的数组，称为模m的一个简化剩余系.

例如，取m=6，在模6的六个剩余类中，

k1 , 11, 5,1,7,13, ,

k5 , 7, 1,5,11,17, 是与模6互质的剩余类.数组1，5；7，－7；1，－1；等等

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