一些算法小记录

同余定理

给定一个正整数\(m\)，如果两个整数 \(a\) 和 \(b\) 满足 \((a-b)\) 能够被m整除，即 \((a-b)/m\) 得到一个整数，那么就称整数 \(a\) 与 \(b\) 对模 \(m\) 同余，记作 \(a≡b(mod\ m)\)。

两个整数\(a、b\)，若它们除以整数\(m\)的余数相等，则称整数 \(a\) 与 \(b\) 对模 \(m\) 同余，记作 \(a≡b(mod\ m)\)。

即 \[ (a-b)\ mod\ m = 0\ ⇔\ a\ mod\ m\ =\ b\ mod\ m \] 定理适用于对一个表达式取模时拆括号。

费马小定理

整数 \(a\) 和素数 \(p\)，有： \[ a^{p-1}\ \equiv 1\ (mod\ p) \] ps. latex恒等于符号使用 \equiv，这部分latex代码没写过，可以看源码复习复习

定理适用于对幂取模时快速计算，如取\(2^{100}\)模\(13\)： \[ \begin{aligned} 2^{100} & \equiv 2^{12\times8+4} \\ & \equiv (2^{12})^8\cdot2^4 \\ & \equiv 1^8\cdot16 \\ & \equiv 16 \\ & \equiv 3 \pmod{13} \end{aligned} \] 余数就是\(3\)。