整除与同余的常见推论
整除
1.若 a | b 且 b | c ，则 a | c。
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。解释：a | b ， 则 b = q*a， b | c ， 则 c = p*b
于是 c = p * q * a， 即 a | c。
2. a | b 且 a | c 等价于对任意的整数x、y， 有 a | （b*x + c*y）。
解释：由a | b 且 a | c 得到 b = q*a， c = p*a， 则b*x + c*y = a*（q*x + p*y）。
3.设 m ！= 0， 那么a|b 等价于 （m*a）|（m*b）。
解释：
b = p*a， m*b = m*a*p。
4.设整数x和y满足a*x + b*y = 1， 且a|n、b|n， 那么（a*b）|n。
解释，由a|n， 得（a*b）|（n*b）， 同理 （a*b）|（n*a）。
于是（a*b）|（x*（n*b）+ y*（n*a））， 分解括号得（a*b）|（n*（x*b + y*a））， 于是（a*b）| n.
5.若b = q*d + c， 那么 d|b 的充分必要条件是 d|c。
必要：若d|c的值为假， 则 b mod d = c， d|b 不成立。
充分：b mod d = （q*d） mod d + c mod d， 若 d|c， 则 b mod d = 0；
同余
一、
有两整数a、b，若abs（a-b） mod m == 0， 则a 恒等于 b （mod m）， 它意味着 a - b = m*k。
解释：若 a 与 b mod m的值相等， 则设这个值为 P， 于是 a = x*m + P， b = y*m + P， a-b == （x-y）*m。
二、
（以下文字中，恒等于用=代替）
对于整数a、b、c和自然数 m、n，对模m同余具有以下一些性质：
1.自反性：a = a （mod m）。
解释：a mod m 是1 ~ （m-1） 之间的一个定值。
2.对称性：若 a = b （mod m）， 则 b = a （mod m）。
解释：同上。
3.传递性：若a = b（mod m）， 且 b = c （mod m）， 则 a = c （mod m）。
解释：同上。
4.同加性：若 a = b （mod m）， 则 a + c = b + c （mod m）
解释：设P = a mod m， 则 b mod m = P。 于是a = k*m + P， b = z*m + P
于是，a + c = （k*m） + （c + P）， b + c = （z*m） + （c + P）。
由自反性得， c + P = c + P （mod m）。 于是 a + c = b + c （mod m）。
5.同乘性：（1）若a = b （mod m）， 则 a*c = b*c （mod m）
（2）若a = b （mod m），c = d （mod m）， 则 a * c = b * d （mod m）。
解释：{
（1）：
同上， a = k*m + P， b = z*m + P， 于是 a*c = c*k*m + c*P， b*c = c*z*m + c*P。
由自反性， c*P = c*P （mod m）， 于是 a*c = b*c （mod m）。
（2）：
同上， a = k*m + P， b = z*m + P， c = x*m + Q， d = y*m + Q，
a*b = （k*m + P）*（x*m + Q）， c*d = （z*m + P）*（y*m + Q），
则 a*b mod m = P*Q mod m， c*d mod m = P*Q mod m，
于是 a*c = b*d （mod m）。
}
6.同幂性：若 a = b （mod m）， 则 an = bn （mod m）。
解释：同上，a = k*m + P， b = z*m + P， 分解得 an mod m = Pn mod m， bn mod m = Pn mod m，
由自反性， 于是an = bn （mod m）。
推论{
（1）：
a*b mod k = （a mod k）*（b mod k） mod k。
解释：
设a mod k == P， b mod k == Q，
则 a = x*k + P， b = y*k + Q， 于是a*b mod k = （x*k + P）*（y*k + Q） mod k == P*Q mod k。
可知推论中两式相等。
（2）：
若 a mod p == x， a mod q == x， p、q 互质， 则 a mod （p*q） == x。
解释：
由 a mod p == x ， 则 a = m*p + x， 由 a mod q == x ， 则 a = n*q + x，
则 m*p == n*q， 由p、 q 互质， 则 m*p 中至少有一个 p*q 因子， 于是 m = k*q， 于是 n = k*p，
于是 a = k*p*q + x， 于是a mod （p*q） == x。
}
