同余方程（记录）

整除的相关概念

设a、b是两个整数，且b != 0，若存在一个整数q，使得a = q * b成立，则称b整除a 或 a被b整除（个人觉得有点容易搞混概念，做个强调），记作b|a，把b叫做a的因数，把a叫做b的倍数，同时q也为a的因数。

相关性质

设a、b、c是三个整数，均不为0

传递性：若c|b，且b|a，则c|a，即存在整数q使得a = q * c也成立

加法运算：若c|b，c|a，则c|(ab)，即存在整数q使得(ab) = q * c也成立

线性组合：若c|b，c|a，则存在整数x、y使得c|(x*a+y*b)，即存在整数q使得(x*a+y*b) = q * c也成立

相等性：若a|b，且b|a，则a=b

同余方程

概念：给定整数m，若用m去整除整数a、b得到的余数r相同（r同余，记作

a ≡ b mod m，当且仅当m|(a-b)

证明：由题a = q1 * m + r，b = q2 * m + r ，相减得a - b = (q1-q2) * m，记整数q = q1 - q2，即m|(a-b)

相关性质

自反性：a ≡ a mod n

对称性：若a ≡ b mod n，则有b ≡ a mod n

传递性：若c ≡ a mod n，且a ≡ b mod n，则有c ≡ b mod n

其它：

若a ≡ b mod n，c ≡ d mod n，则有

1、a  b ≡ b  c mod n

2、ac ≡ bd mod n

3、a*c ≡ b*d mod n

4、 ≡ 

（以上的’≡‘为同余符号）