b站视频链接：北京理工大学ACM冬季培训课程
 课程刷题地址 2020BIT冬训-简单数论 Password: easyshulun
本篇博文为看视频学习时的记录与自己的一些总结

简单数论

比较难，之后完善

¶整除

a % b == 0 一般被我们写作 $b \mid a$

有若干性质：

若 $a \mid b$，可知 $-a \mid b$，$a \ \mid-b$，$\left\vert a \right\vert \mid \left\vert b \right\vert$
若 $a \mid b$ 且 $b \mid c$，可知 $a \mid c$
若 $a \mid b$ 且 $a \mid c$，可知 $ a \mid (bx + cy) $，其中 $x$，$y$ 为任意整数
若 $a \mid b$，可知 $am \mid bm$，其中 $m$ 为非零整数
若 $a \mid b$，$b \mid a$，可知 $b=\pm a$，即 $\left\vert b \right\vert = \left\vert a \right\vert$
若 $a \mid bc$，且 $a$ 与 $c$ 互质，则 $a \mid b$
若 $a \mid b$，$a \mid c$，且 $b$ 与 $c$ 互质，则 $a \mid bc$
若 $a \mid b$，$c$ 为任意整数，则 $b \mid ac$
对任意整数 $a$，$b > 0$，存在唯一的数对 $q$，$r$，使 $a = bq + r$，其中 $0 \le r < b$，这个事实称为带余除法定理，是整除理论的基础
若 $c \mid a$，$c \mid b$，则称 $c$ 是 $a$，$b$ 的公因数。若 $d$ 是 $a$，$b$ 的公因数，$d \ge 0$，且 $d$ 可被 $a$，$b$ 的任意公因数整除，则 $d$ 是 $a$，$b$ 的最大公因数。若 $a$，$b$ 的最大公因数等于 $1$，则称 $a$，$b$ 互素，也称互质。累次利用带余除法可以求出 $a$，$b$ 的最大公因数，这种方法常称为辗转相除法。又称欧几里得算法。

当 a % b == c % b，可以说 $a \equiv c \pmod{b}$

有很多优秀的性质

同余的性质

反身性：$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 \equiv b \pmod{m}$，$c \equiv d \pmod{m}$，则 $a+c \equiv b+d \pmod{m}$；
同余式相乘：若 $a \equiv b \pmod{m}$，$c \equiv d \pmod{m}$，则 $a c \equiv b d \pmod{m}$。

欧拉定理

$\gcd(a,n) = 1$，则 $a^{\phi(n)} \equiv 1 \pmod{n}$

费马小定理

$p$ 为质数，$\gcd(a,p) = 1$，$a^{(p-1)} \equiv 1 \pmod{p}$

卢卡斯定理

威尔逊定理

$\gcd(a,b) = \gcd(b,a%b)$
辗转相除，写递归
另外
$\operatorname{lcm}(m,n) * \gcd(a,b) == a*b$

Gcd=d, A=cd, B=ed, Lcm=ced, Lcm*Gcd=A*B