数论

整除

整除的定义：设 $a,b\in\mathbf{Z}$，$a\ne 0$。如果 $\exists q\in\mathbf{Z}$，使得 $b=aq$，那么就说 $b$ 可被 $a$ 整除，记作 $a\mid b$；$b$ 不被 $a$ 整除记作 $a\nmid b$。

整除的性质：

• $a\mid b\iff-a\mid b\iff a\mid-b \iff|a|\mid|b|$。

• $a\mid b\land b\mid c\implies a\mid c$。

• $a\mid b\land a\mid c\iff\forall x,y\in\mathbf{Z}, a\mid(xb+yc)$。

• $a\mid b\land b\mid a\implies b=\pm a$。

• 设 $m\ne0$，那么 $a\mid b\iff ma\mid mb$。

• 设 $b\ne0$，那么 $a\mid b\implies|a|\le|b|$。

• 设 $a\ne0,b=qa+c$，那么 $a\mid b\iff a\mid c$。

同余

同余的定义：设整数 $m\ne0$。若 $m\mid(a-b)$，称 $m$ 为模数（模），$a$ 同余于 $b$ 模 $m$，$b$ 是 $a$ 对模 $m$ 的剩余。记作 $a\equiv b\pmod m$。

否则，$a$ 不同余于 $b$ 模 $m$，$b$ 不是 $a$ 对模 $m$ 的剩余。记作 $a\not\equiv b\pmod m$。

这样的等式，称为模 $m$ 的同余式，简称同余式。

根据整除的性质，上述同余式也等价于 $a\equiv b\pmod{(-m)}$。

如果没有特别说明，模数总是正整数。

同余的性质：

• 自反性：$a\equiv a\pmod m$。

• 对称性：若 $a\equiv b\pmod m$，则 $b\equiv a\pmod m$。

• 传递性：若 $a\equiv b\pmod m,b\equiv c\pmod m$，则 $a\equiv c\pmod m$。

• 线性运算：若 $a,b,c,d\in\mathbf{Z},m\in\mathbf{N}^*,a\equiv b\pmod m,c\equiv d\pmod m$ 则有：

  • $a\pm c\equiv b\pm d\pmod m$。

  • $a\times c\equiv b\times d\pmod m$。

• 若 $a,b\in\mathbf{Z},k,m\in\mathbf{N}^*,a\equiv b\pmod m$, 则 $ak\equiv bk\pmod{mk}$。

• 若 $a,b\in\mathbf{Z},d,m\in\mathbf{N}^*,d\mid a,d\mid b,d\mid m$，则当 $a\equiv b\pmod m$ 成立时，有 $\dfrac{a}{d}\equiv\dfrac{b}{d}\left(\bmod\;{\dfrac{m}{d}}\right)$。

• 若 $a,b\in\mathbf{Z},d,m\in\mathbf{N}^*,d\mid m$，则当 $a\equiv b\pmod m$ 成立时，有 $a\equiv b\pmod d$。

• 若 $a,b\in\mathbf{Z},d,m\in\mathbf{N}^*$，则当 $a\equiv b\pmod m$ 成立时，有 $\gcd(a,m)=\gcd(b,m)$。若 $d$ 能整除 $m$ 及 $a,b$ 中的一个，则 $d$ 必定能整除 $a,b$ 中的另一个。

分数gcd与lcm

设有$n$个分数分别为$c_1=\dfrac{a_1}{b_1},c_2=\dfrac{a_2}{b_2},\ ...\ c_n=\dfrac{a_n}{b_n}$，则

• $lcm(c_1,c_2\ ...\ c_n)=\dfrac{lcm(a_1,a_2,\ ...\ a_n)} {gcd(b_1,b_2,\ ...\ b_n)}$。

• $gcd(c_1,c_2\ ...\ c_n)=\dfrac{gcd(a_1,a_2,\ ...\ a_n)} {lcm(b_1,b_2,\ ...\ b_n)}$。