同余的基础性质

2019-04-13 21:21发布

站内文章 / 模拟电子
15360 0 1789
在开始之前，我们要先了解一些数论的基本符号（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......])。

热门文章