数学——数论--整除

设a是非零整数，b是整数。如果存在一个整数q，使得b=a*q，那么就说b可被a整除，记作alb，且称b是a的倍数，a是b的约数（因子）。

整除的一些性质：

• 如果a | b且b | c，那么a | c
• a | b且a | c等价于对于任意的整数x和y，又a | (b * x + c * y)。
• 设$m\neq 0$，那么$a | b$ 等价于$(m * a) | (m * b)$
• 设整数x和y，满足$ax+by = 1$，且$a|n, b|n$，证明$(ab)|n$

$$\begin{aligned} &(a * b)|(b * n) 且(a * b)|(a * n)\\ &(a * b) |(a * n * x+b * n * y) \\ & (a*b) | n \end{aligned}$$

• 若$b = q * d + c$，那么$d|b$的充要条件时$d|c$。

设$d|b$，则$b = d * m = d * q + (m - q)*d = d * q + c$，所以$c = (m -q)*d$，所以$d|c$，必要性证明同理。

• 若2能整除a的最末位（约定0可以被任何数整除），则2la；
• 若4能整除a的最后两位，则4|a；
• 若8能整除a的最后三位，则8|a；
• 若3能整除a的各位数字之和，则3la；
• 若9能整除a的各位数字之和，则9la；
• 若11能整除a的偶数位数字之和与奇数位数字之和的差，则11|a。
• 能被7、11、13整除的数的特征是：这个数的末三位数与末三位以前的数字所组成的数之差能被7、11、13整除，这个数就能被7、11、13整除。