初等数论 2.3 剩余类

2019-04-13 21:45发布

定理:由同余关系是一种等价关系,对于给定的mZ+min^+,可以通过模mm对应Z的分拆.
定义:设mZ+min^+,对每个整数0rm10le r le m-1,称集合Cr=nnr(modm)nZdisplaystyle C_r={nmid nequiv rpmod m,nin}为模mm的一个剩余类.
C0,C1,,Cm1C_0,C_1,cdots,C_{m-1}构成Z的一个分拆.
定义:设mZ+min^+,从模mm的每个剩余类中任取一个数xi(0im1)displaystyle x_i(0le i le {m-1}),称集合{x0,x1,,xm1}displaystyle {x_0,x_1,cdots,x_{m-1}}为模mm的一个完全剩余类(complete residue system).
mm的完全剩余系有无穷多个.
一些常用的完全剩余系:
1.模mm的最小非负完全剩余系:{0,1,2,,m1}displaystyle {0,1,2,cdots,m-1}.
2.模mm的最小正完全剩余系:{1,2,,m}displaystyle {1,2,cdots,m}.
3.模mm的绝对最小完全剩余系:{{m12,,2,1,0,1,2,,m12}m{m2+1,,2,1,0,1,2,,m2}{m2,,2,1,0,1,2,,m2+1}mdisplaystyle egin{cases} {-dfrac{m-1}{2},cdots,-2,-1,0,1,2,cdots,dfrac{m-1}{2}} quad m为奇数 \ {-dfrac{m}{2}+1,cdots,-2,-1,0,1,2,cdots,dfrac{m}{2}}或{-dfrac{m}{2},cdots,-2,-1,0,1,2,cdots,dfrac{m}{2}+1} quad m为偶数 end{cases}
定理:mm个整数构成模mm的一个完全剩余系当且仅当它们两两模mm不同余.
定理:设mZ+a,bZ(a,m)=1min^+,a,bin,(a,m)=1,若{x1,x2,,xm}{x_1,x_2,cdots,x_m}是模mm的一个完全剩余系,则{ax1+b,ax2+b,,axm+b}{ax_1+b,ax_2+b,cdots,ax_m+b}也是模mm的一个完全剩余系.
定理:设m1,m2Z+kZm_1,m_2in^+,kin,且(k,m1)=1(k,m_1)=1.又设X={x1,x2,,xm1}Y={y1,y2,,ym2}displaystyle X={x_1,x_2,cdots,x_{m_1}} quad Y={y_1,y_2,cdots,y_{m_2}}分别是模m1m_1与模m2m_2的完全剩余系,则M={kx+m1yxX,yY}displaystyle M={kx+m_1ymid xin X,yin Y}