模运算与同余

模运算与同余

两个整数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整除．反过来也成立．