数论

整除

如果存在两个整数 $a$ 和 $b$(其中 $b \neq 0$),使得存在某个整数 $k$ 满足 $a = kb$, 则称 $b$ 整除 $a$,记作 $b|a$.

常见整除判断法则

• 被 2 整除:个位是 0、2、4、6、8 的整数能被 2 整除.
• 被 5 整除:个位是 0 或 5 的整数能被 5 整除.
• 被 4 整除:末两位能被 4 整除,该整数就能被 4 整除.
• 被 8 整除:末三位能被 8 整除,该整数就能被 8 整除.
• 被 3 整除:各位数字之和能被 3 整除,该整数就能被 3 整除.
• 被 9 整除:各位数字之和能被 9 整除,该整数就能被 9 整除.

同余

给定一个正整数 $m$,若两个整数 $a$ 和 $b$ 满足 $m|(a-b)$, 即 $(a-b)$ 能被 $m$ 整除,则称 $a$ 和 $b$ 对模 $m$ 同余,记为 $a \equiv b \pmod{m}$

余数范围

整数 $a$ 除以非零整数 $b$,余数 $r$ 满足 $0 \leq r \lt |b|$.如 $17 \div 5 = 3 \cdots \cdots 2$,$0 \leq 2 \lt 5$.

加法特性

$a$ 除以 $b$ 余 $r_1$,$c$ 除以 $b$ 余 $r_2$,那么 $(a + c)$ 除以 $b$ 的余数,等于 $r_1 + r_2$ 除以 $b$ 的余数.即余数可以分开加,最后再取余数.例如,$17$ 除以 $5$ 余 $2$,$13$ 除以 $5$ 余 $3$,$17 + 13 = 30$ 除以 $5$ 余 $0$,$2 + 3 = 5$ 除以 $5$ 也余 $0$.

乘法特性

$a$ 除以 $b$ 余 $r_1$,$c$ 除以 $b$ 余 $r_2$,$a \times c$ 除以 $b$ 的余数,等于 $r_1 \times r_2$ 除以 $b$ 的余数.也就是余数能分开乘,最后再取余.比如,$17$ 除以 $5$ 余 $2$,$13$ 除以 $5$ 余 $3$,$17 \times 13 = 221$ 除以 $5$ 余 $1$,$2 \times 3 = 6$ 除以 $5$ 同样余 $1$.

幂运算特性

$a$ 除以 $b$ 余 $r$,$a$ 的 $n$ 次方($n$ 为正整数)除以 $b$ 的余数,等于 $r$ 的 $n$ 次方除以 $b$ 的余数.即对余数进行幂运算,再取余结果相同.例如,$3$ 除以 $5$ 余 $3$,$3^2 = 9$ 除以 $5$ 余 $4$,$3$ 的平方(余数 3 的平方)除以 $5$ 也余 $4$.

最小公倍数(LCM, Least Common Multiple)

对于两个或多个整数 $a_1, a_2, ..., a_n$,它们的最小公倍数记作 $[a_1, a_2, ..., a_n]$ 或者 $\text{LCM}(a_1, a_2, ..., a_n)$,是最小的能够同时被所有这些整数整除的正整数.

最大公约数(GCD, Greatest Common Divisor)

对于两个或多个整数 $a_1, a_2, ..., a_n$,它们的最大公约数记作 $(a_1, a_2, ..., a_n)$ 或者 $\text{GCD}(a_1, a_2, ..., a_n)$,是最大的能够同时整除所有这些整数的正整数.