数论和基础数学

整除

定义：设 $a, b\in Z$，$a\neq 0$，如果存在 $q\in Z$ 使得 $b=aq$，那么就说 $b$ 可被 $a$ 整除，记作 $a\mid b$，且称 $b$ 是 $a$ 的倍数，$a$ 是 $b$ 的约数（也称除数、因数）。

带余数除法

设 $a, b$ 是 $2$ 个正整数，且 $b\neq 0$，则存在唯一整数 $q$ 和 $r$，使 $a=qb+r,\ 0\leqslant r<\left| b\right|$。这个式子叫做带余数除法，并记余数 $r=a\ \text{mod} \ b$。例如 $13\ \text{mod} \ 5=3$，$10\ \text{mod} \ 2=0$。当 $r=0$ 的时候，就出现了整除，$b$ 是 $a$ 的约数。

如果 $n$ 被 $2$ 除的余数为 $0$，称 $n$ 为偶数，如果 $n$ 被 $2$ 除的余数为 $1$，则称 $n$ 为奇数。

关于整除有下面这些性质：

1. 若 $a\mid b$ 且 $a\mid c$，则 $\forall x,y$，有$a\mid xb+yc$。
2. 若 $a\mid b$ 且 $b\mid c$，则 $a\mid c$。
3. 设 $m\neq 0$，则 $a\mid b$，当且仅当 $ma\mid mb$。
4. 若 $a\mid b$ 且 $b\mid a$，则 $a=\pm b$。
5. 若 $a\mid b$ 且 $b\neq 0$，则 $\left| a\right| \leqslant \left| b\right|$。

关于余数有下面这些性质：

1. $\left( a+b\right) \text{mod} \ p=(a\ \text{mod} \ p+b\ \text{mod} \ p)\text{mod} \ p$
2. $\left( a\times b\right) \text{mod} \ p=(a\ \text{mod} \ p+\times b\ \text{mod} \ p)\text{mod} \ p$