模运算与同余

2019-04-13 13:00发布

两个整数a,b,若它们除以整数m所得的余数相等,则称a,b对于模m同余  记作 a ≡ b (mod m)   读作a同余于b模m,或读作a与b关于模m同余。 同余关系满足以下规律:   1)(反身性) 2)(对称性)若,则 3)(传递性)若,则 4)(同余式相加)若,则 5)(同余式相乘)若,则   运算规则: 模运算与基本四则运算有些相似,但是除法例外。其规则如下:
        (a + b) % p = (a % p + b % p) % p            1
        (a - b) % p = (a % p - b % p) % p             2 
        (a * b) % p = (a % p * b % p) % p            3

整除的性质

(1)如果a与b都能被c整除,那么a+b与a-b也能被c整除.   (2)如果a能被b整除,c是任意整数,那么积ac也能被b整除.   (3)如果a同时被b与c整除,并且b与c互质,那么a一定能被积bc整除.反过来也成立.