|

楼主 |
发表于 2021-12-17 21:21
|
显示全部楼层
剩余类和完全剩余系:
定义1:取定m>0,任意的r∈Z,设r mod m ={qm+r|q=0,±1,±2,.....}
把r mod m 称为模m的一个剩余类,除以m后余数相等的记为一类,同余同类,不同于不同类。(只要取定一个m,那么就可以将所有的整数分为m个剩余类,任意的r只要是对m取模相同,则在同一个剩余类里面)
定理1 取定m>0,则
1)任意的a∈Z,a恰在模m的一个剩余类 r mod m,r=0,1,2,....m-1中。(即将所有整数分为m份,放入不同的剩余类中)
2)任意的x,y∈Z,x,y在模m的同一个剩余类(x≡y mod m)
特点:由定理1,给定模m,
·任意r,s∈Z, r mod m =s mod m或 r mod m ∩ s mod m = ∅
·恰有 m 个不同的模m的剩余类 0 mod m,1 mod m......(m-1) mod m。
·Z=∑ i mod m i∈【0,m-1】。
例子:
设S={a1,a2,....an},其中ai都是整数,证明存在S的一个非空子集,其各个元素的和被n整除。
证:(运用了鹊巢原理)考虑n个整数 S1=a1,S2=a1+a2,...... , Sn=a1+a2+...an,若Si被n整除,则Si符合,若没有是
被n整除(即Si∉0 mod n),那么S1,S2,....,Sn 中必有两数在模 n 的同一个剩余类中,那么这两数只差就是n的倍数。
不妨设 Si≡Sj(mod n),i<j, 则子集为{ai+1,ai+2,.....,aj}。
定义2:一组数a0,a1,.....,am-1 称为模m 的一个完全剩余系,如果 ai∈i mod m,i=0,1,2,...,m-1。(因为完全剩余系里面两两各不相同)
设 a1,a2,...,am 是模m的一个完全剩余系,则
·如果 ai≡aj(mod m), 就有 i=j,ai=aj 。
常用的完全剩余系
·0,1,.....,m-1称为模m的非负最小完全剩余系
· m 为奇数时,
-(m-1)/2 , -(m+1)/2 , ... , -1 , 0 , 1 , ... , (m-1)/2
· m为偶数时,
① -m/2, -m/2+1 , ... , -1 , 0 , 1 , ... , m/2-1
②-m/2+1 , ... , -1 , 0 , 1 , ... , m/2-1 , m/2
称为模m 的绝对最小完全剩余系。
完全剩余系的判定及构造:
定理2 一组数a1,a2 , ... , ak 是模m的一个完全剩余系
{k=m }
{a1 , a2 , ... , ak对模m两两互不同余}
定理3 若a1 , a2 , ... ,am 是模m的一个完全剩余系, 则ka1, ka2,...,kam 也是模
m的一个完全剩余系。
定理4 设(k,m)=1,b∈Z, 若a1,a2, ... , am 是模m的一个完全剩余系,则
ka1+b , ka2+b , ... , kam+b(运用了定理3,然后都加上b相当于同时全部元素移动了b步)
也是模m的一个完全剩余系。
定理5 设(m1,m2)=1,若x1,x2分别通过模m1,m2的一个完全剩余系,则m1x2+m2x1通过模m1m2的一个完全剩余系。
证:(m1x2+m2x1)%m1m2=x2%m2+x1%m1
|
|