同余的基础性质

2019-04-13 21:21发布

在开始之前,我们要先了解一些数论的基本符号(a,b)表示a,b的最大公约数,[a,b]表示a,b的最小公倍数,b|a表示a%b=0。在数论中我们定义同余:设m!=0,若m|a-b,则a-b=km。称m为模,a同余于b模m以及b是a模m的剩余。记做a≡b(modm),也称作模m的同余式。例如对于偶数我们总可以除尽2,那么用同余式就可写为a≡0(mod2),同理对于奇数我们可以写成a≡1(mod2)。定理一:a同余b的充分必要条件是a和b能被m除后所得的最小非负数余数相等,即若a=q1+r1且b=q2+r2 (0<=r1同余的性质有:性质一:同余是一种等价关系a≡a(mod m) a≡b(mod m)<=>b≡a(mod m) a≡b(mod m),b≡c(mod m)=> a≡c(mod m)性质二:同余式可以相加,即若有a≡b(mod m),c≡d(mod m)则(a+c)≡(d+b)(mod m)性质三:同余式可以相乘,即若有a≡b(mod m),c≡d(mod m)则(ac)≡(db)(mod m)性质四:设d>=1,d|m,若a≡b(mod m),则a≡b(mod d)性质五:设d!=0,那么a≡b(mod m)等价于da≡db(mod |d|m)性质六:ca≡cb(mod m),等价于a≡b(mod m/(c,m))特别的当c(m,c)=1时,ca≡cb(mod m)等价于a≡b(mod m)在这里给出性质六的证明:m|c(a-b),这等价于m/(c,m)|(a-b)c/(c,m)。由(m/(c,m),c/(c,m))=1,可得m/(c,m)|a-b性质六得证。性质七:若m>=1,(a,m)=1,则存在c使ca≡1(mod m),我们把c称为a对m的逆,记做a^-1(mod m)或a^-1。性质八:同余式组a≡b(mod mj) (j=1,2,3......)同时成立的充要条件是 a≡b(mod [m1,m2,m3......])。