1. 同余(congruence modulo)
同余是指两个整数a、b，若它们除以整数m所得的余数相等，则称a与b对于模m同余或a同余于b模m。同余的符号是$\equiv$。常用的记法是
$$
a\equiv c\space mod(n)
$$
一般默认$n$为非零整数，$a、c$为非负整数，当然，对于所有的整数，同余的定义和相关性质都是成立的。
$$
10\equiv 3\space mod\space 7\\
1\equiv 10\space mod\space 3
$$
2.同余的性质及证明方法
同余基本性质有反身性，对称性，传递性和线性可加性,分别如下:
$$
a\equiv a\space mod(n) \\
a\equiv b\space mod(n) \Leftrightarrow b\equiv a\space mod(n) \\
a\equiv b\space mod(n)，b\equiv c\space mod(n) \Rightarrow b\equiv c\space mod(n) \\
a\equiv b\space mod(n)，c\equiv d\space mod(n) \Rightarrow a\pm c\equiv b\pm d\space mod(n) \\
a\equiv b\space mod(n)，c\equiv d\space mod(n) \Rightarrow ac\equiv bd\space mod(n)
$$
证明方法大同小异，都是把同余写成乘法形式来证明，以同余乘法性质为例：
$$
\forall \space a\equiv b\space mod(n)，c\equiv d\space mod(n)\\
a = nx + b,c = ny+d \Rightarrow ac = (nx+b)\cdot（ny+d） = n(nxy+by+dx)+bd\\
\because \quad n(nxy+by+dx)能被n整除,\\
\therefore\quad ac\equiv bd\space mod(n)
$$
3.整除判定方法
当右侧和0同余时，根据2节的同余性质，我们可以得到如下公式:
$$
a_i\equiv 0\space mod(n)，k_i\equiv 0\space mod(n) \Rightarrow \sum{a_i*k_i}\equiv 0 \space mod(n)
$$
下面我们来利用该式做整除判定(对于2/5/10这些容易证明的略过)：
3.1 被3整除的数
我们知道被3整除的数，将其所有位数相加，也可以被3 整除，即
$$
\sum{a_i\cdot10^i}\equiv 0 \space mod(3) \Leftrightarrow \sum{a_i}\equiv 0 \space mod(3)
$$
证明如下：
$$
由\sum{a_i\cdot 10^i}\equiv 0 \space mod(3)\quad\quad （1）\\
将其拆分得到:\\
a_0+a_1+9a_1+a_2+99a_2+\dots \equiv 0\space mod(3)\quad\quad （2）\\
即:\sum{a_i}+\sum{（10^i-1)a_i}\equiv 0 \space mod(3),显然左边第二个式中(10^i-1)都是3(和9)的倍数，所以必定有：\\
\sum{a_i}\equiv 0 \space mod(3)
$$
根据上面证明方法，我们顺便可以推出可被9整除的数:
$$
\sum{a_i*10^i}\equiv 0 \space mod(9) \Leftrightarrow \sum{a_i}\equiv 0 \space mod(9)
$$
3.2 被7整除的数
被7整除的数计算方法有点复杂，网上给出的方法是:
将一个整数的个位数字截去，再从余下的数中，减去个位数的2倍，如果差是7的倍数，则原数能被7整除。如果差太大或心算不易看出是否7的倍数，就需要继续上述「截尾、倍大、相减、验差」的过程，直到能清楚判断为止。例如，判断133是否7的倍数的过程如下：13－3×2＝7，所以133是7的倍数；又例如判断6139是否7的倍数的过程如下：613－9×2＝595 ， 59－5×2＝49，所以6139是7的倍数，其余类推.
即:
$$
10a+b\equiv 0\space mod(7)\Leftrightarrow a-2b\equiv 0 \space mod(7)，b \in [0..9]\quad\quad\quad（3）
$$
我在计算中发现还有类似的公式也可以判断被7整除的数：
$$
10a+b\equiv 0\space mod(7)\Leftrightarrow 3a+b\equiv 0 \space mod(7)\quad\quad\quad（4）
$$
其实，根据同余性质，可以很容易推出：
$$
由10a+b\equiv 0\space mod(7) 可得:\\
10(a-2b)+21b\equiv0\space mod(7)\\
易知,21b可被7整除，所以有
10（a-2b）\equiv 0 \space mod (7)\\
将两边除以和7互质的数10，得到公式(3)\\
a-2b\equiv 0\space mod (7)
$$
同理我们也可以推导公式(4)
$$
由10a+b\equiv 0\space mod (7) 可得:\\
(3a+b)+7a\equiv0\space mod(7) \Rightarrow 3a+b\equiv 0 \space mod(7)
$$
依据相关证明方法，我们还可以发明很多类似的公式。
3.3 更多整除判定
根据3.2节里描述的方法，我们轻而易举可以得到11整除的判断方法：
$$
由10a+b\equiv 0\space mod (11) 可得:\\
11a-(a-b)\equiv0\space mod(11) \Rightarrow a-b\equiv 0 \space mod(11)
$$
用人可以读懂的方法就是：将一个整数的个位数字截去，再从余下的数中，减去个位数，如果差是11的倍数，则原数能被11整除。
类似的，若一个整数的个位数字截去，再从余下的数中，加上个位数的4倍，如果差是13的倍数，则原数能被13整除:
$$
由10a+b\equiv 0\space mod (13) 可得:\\
10(a+4b)-39b\equiv 0 \space mod(13) \Rightarrow a+4b\equiv 0 \space mod(13)
$$
若一个整数的个位数字截去，再从余下的数中，减去个位数的5倍，如果差是17的倍数，则原数能被17整除：
$$
由10a+b\equiv 0\space mod (17) 可得:\\
10(a-5b)+（17*3)b\equiv 0 \space mod(17)\Rightarrow a-5b\equiv 0 \space mod(17)
$$
3.4 4和8的整除判定
4的整除判定方法为：取整数后2位数字，如果其能被4整除，则原数字可被4整除(100a被4整除)：
$$
\forall x=100a+b\equiv 0\space mod(4) \Rightarrow b\equiv 0\space mod(4),\forall b \in [0,99)
$$
同理可得8的整除判定方法：取整数后3位数字，如果其能被8整除，则原数字可被8整除(1000a被8整除)：
$$
\forall x=1000a+b\equiv 0\space mod(8) \Rightarrow b\equiv 0\space mod(8),\forall b \in [0,999)
$$