Number Theory - 数论

整除（Divisibility）。 对整数 a,b，其中 a\neq 0，若存在整数 k 使得 b=ak，则称 a 整除 b，记作 a\mid b。

1 到 n 中能被 d 整除的数一共有 \lfloor n / d \rfloor 个。（0<kd\leq{}n）。

以下 a,b,c 均为整数。性质：

• a\mid b,a\mid c\to{}a\mid (b+c)
• a\mid b\to a\mid bc
• a\mid b,b\mid c\to{}a\mid c
  结合这些性质，推出：
  a\mid b,a\mid c\to{}a\mid mb+nc
  （其中 m,n 为整数：整除两个数，那么也整除它们的整数线性组合）

标准除法：对整数 a 和正整数 d，存在唯一的整数 q,r 其中 0\leq{}r<d，使得 a=dq+r。d 是除数（divisor），q 是商（quotient），a 是被除数（dividend），r 是余数（remainder）。

• 记 q=a \,\mathrm{ div}\,d，r=a\bmod d

同余（Congruent）：设 a,b 为整数，m 为正整数。若 m \mid a-b，那么 a 与 b 模（modulo） m 同余，记作
a\equiv{}b\pmod{m}
这里 m 叫做模数（modulus）。
由定义：
a\equiv{}b\pmod{m}\Leftrightarrow{} \exists k\in\mathbb{Z},a=b+km
也可证：
a\equiv{}b\pmod{m}\Leftrightarrow{} a\bmod m=b\bmod m
若 a\equiv{}b \pmod{m} 和 c\equiv{}d \pmod{m}，那么有
a+c\equiv{}b+d \pmod{m}
ac\equiv{}bd\pmod{m}