数论笔记整理1

同余定理：

给定一个正整数 $ m $，如果两个整数 $ a $ 和 $ b $ 满足 $ a-b $ 能够被 $ m $ 整除，即 $\frac{a-b}{m} $ 为一个整数，那么就称整数 $ a $ 与 $ b $ 对模 $ m $ 同余，记作 $ a \equiv b \;(mod \; m) $。对模 $ m $ 同余是整数的一个等价关系。（自反、对称、传递）

性质与证明：

1、自反性：$ a \equiv a \;(mod\;m) $；

2、对称性：若 $ a \equiv b \; (mod \; m)$，则 $ b\equiv a \;(mod \; m) $；

3、传递性：若 $ a \equiv b \; (mod \; m) $，$ b \equiv c \; (mod \; m) $，则 $ a \equiv c \;(mod \; m) $；

4、同余式相加：若 $ a \equiv b \; (mod \; m) $，$ c \equiv d \; (mod \; m) $， 则 $ a \pm c \equiv b \pm d \; (mod \; m) $；

证明： $ a \equiv b \; (mod \; m) $，$ c \equiv d \; (mod \; m) \Rightarrow m | ( a - b ) $ , $ m | (c - d) $
$ \Rightarrow m|[(a - b) \pm (c - d)] \Rightarrow m | [(a \pm b) - (c \pm d)] \Rightarrow a \pm c \equiv b \pm d \; (mod \; m) $.

5、同余式相乘：若 $ a \equiv b \; (mod \; m) $，$ c \equiv d \; (mod \; m) $， 则 $ ac \equiv bd \; (mod \; m) $.

证明：因为 $ ac - bd = ac - bc + bc - bd = c(a - b) + b(c - d) $ ，且 $ m | ( a - b ) $ , $ m | (c - d) $，所以 $ m | (ac - bd) $ ，即 $ ac \equiv bd \; (mod \; m) $.

6、除法：若 $ ac \equiv bc \; (mod \; m) $ ，$ c \neq 0 $，则 $ a \equiv b \; (mod \; \frac{m}{gcd(c, m)}) $.

特殊地，若 $ gcd(c, m) = 1 $ 时，则 $ a \equiv b \; (mod \; m) $.
举个栗子：$ 14 \equiv 6 \;(mod \; 8) \Rightarrow 7 \equiv 3 \;(mod \;4) $，此时 $ gcd(14, 8) = 2 $。

7、幂运算：若 $ a \equiv b \; (mod \; m) $，则 $ a^n \equiv b^n \; (mod \; m) $.

说明：左边每个数取模m都同余于对应右边的每一个数，显然等式恒成立。

8、若 $ a \equiv b \; (mod \; m)$，$ n | m $，则 $ a \equiv b \; (mod \; n) $.

9、若 $ a \equiv b \; (mod \; m_i)$，$ (i = 1, 2, \cdots k) $, 则 $ a \equiv b \; (mod \; [m_1, m_2, \cdots, m_k])$。

其中 $ [m_1, m_2, \cdots, m_k] $ 表示 $ m_1, m_2, \cdots, m_k $ 的最小公倍数。

同余转换：

$ (a \pm b) \; mod \; p = (a \; mod \; p \pm b \; mod \; p) \; mod \; p $；

$(a * b) \; mod \; p = (a \; mod \; p * b \; mod \; p) \; mod \; p$；
除运算：$ (a / b) \; mod \; p = [(a \; mod \; p) / (b \; mod \; p)] \; mod \; p $，要用乘法逆元!!!
举个栗子：
$ (100 / 50) \; mod \; 20 == 2 \neq [(100 \; mod \; 20) / (50 \; mod \; 20)] \; mod \; 20 == 0 $.

欧几里德算法：（辗转相除法）

定义：求整数a和b的最大公约数，其中a、b不全为0.
定理：设 $ a = qb + r $， 其中 $ a, b, q, r \in \mathbb{Z} $， 则 $ gcd(a, b) = gcd(b, r)$.
证明：若d是a和b的公因子，即 $ d | a \land d | b $，则 $ d | b \land d | [r = (a - qb)]$；
若d是b和r的公因子，即 $ d | b \land d | r $，则 $ d | (qb + r) $，即 $ d | a $.
于是， a和b的公因子集合与b和r的公因子集合相同。继而，其最大公因子相同，即证。
备注：任意一个非0整数和0的约数是该整数的所有约数，最大公约数为其本身。因为0被任意一个非0整数整除，所以任意一个非0整数都是0的约数。

贝祖定理：

定理：$ \forall \; a, b \in \mathbb{Z} $，$ \exists \; x, y \in \mathbb{Z} $，使得 $ ax + by = gcd(a, b) $.
证明：若 $ ax + by = d = gcd(a, b) $，则 $ d | a, d | b $，
即 $ \forall \; x, y \in \mathbb{Z} $，都有 $ d | (ax + by) $。因此，一定存在整数解x、y。
设 $ s $ 是 $Q::=\{h \in \mathbb{Z}| h = ax + by$，其中 $a, b, x, y \in \mathbb{Z}\}$中的最小正整数，
即 $ \exists \; x_0, y_0 \in \mathbb{Z} $，有 $ s = ax_0 + by_0 $。
设 $ q = \left \lfloor \frac{a}{s} \right \rfloor $，则 $ r = a \; mod \; s = a - qs = a - q(ax + by) $
$= a(1 - qx) + b(-qy) \Rightarrow r \in Q $。又 $ 0 \leq r < s $，所以 $ r = 0 \Rightarrow s | a $。
同理 $ s | b $，说明s是a和b的公约数，则 $ s \leq d $。
因为 $ \forall \; x, y \in \mathbb{Z} $，都有 $ d | (ax + by) \Rightarrow d |(x_0 + y_0) = d | s $，则 $ d \leq s $，所以 $ s = d = gcd(a, b) $，即证。由此还可知 $ \forall \; a, b \in \mathbb{Z} $，$ gcd(a, b) $ 是线性组合 $ (ax + by) $ 的最小正整数。

裴蜀定理：

$ \forall \; a, b \in \mathbb{Z} $，方程 $ ax + by = c $ 有整数解，当且仅当 $ gcd(a, b)|c $。
证明：充分性：设 $ d = gcd(a, b) $，由贝祖定理可知一定有整数解 $ x_0, y_0 $ 使得 $ ax_0 + by_0 = d $。因为 $ d | c $，所以 $ \exists k \in \mathbb{Z} $，使得 $ c = kd = k(ax_0 + by_0) $
$ = a(kx_0) + b(ky_0) $，即方程有整数解 $ kx_0, ky_0 $。
必要性：$ \exists \; x_1, y_1 \in \mathbb{Z} $，使得 $ ax_1 + by_1 = c $，设 $ d = gcd(a, b) $，则 $ d | a, d | b $
$ \Rightarrow d | (ax_1 + by_1) \Rightarrow d | c $，即证。

扩展欧几里得算法：

定义：在已知a, b求解一组x，y，使它们满足贝祖等式： $ ax + by = gcd(a, b) = d $（解一定存在）。由欧几里德算法得 $ gcd(a, b) = gcd(b, a \; mod \; b) $，
则 $ax + by = bx_1 + (a - a / b * b)y_1 = ay_1 + b(x_1 - a / b * y_1)$，
即 $ x = y_1, y = x_1 - a / b * y_1 $。

乘法逆元：

若 $ ax \equiv 1(mod \; m) $，则称x是模m意义下a的乘法逆元。记 $ x =inv(a) $ 或 $ x = a^{−1} $。
注意：$ gcd(a, m) = 1 $ 。
求法：①将方程转化为 $ ax - my = 1 $，然后用扩展欧几里得算法求解即可。
②根据欧拉定理：若 $a,m \in \mathbb{N}^+ \land \gcd(a,m) =1 $，则 $ a^{\varphi(m)} \equiv 1\;(mod\;m)$；根据同余式可乘性质可得 $ a^{\varphi(m)} \times a^{-1} \equiv 1 \times a^{-1} \;(mod\;p) \Rightarrow a^{-1} \equiv a^{\varphi(m)-1} \;(mod\;p)$，即 $ inv(a) = a^{\varphi(m)-1} \;(mod\;p)$，然后用整数快速幂取模求解即可！
③线性求 $ 1\sim p-1 $ 的乘法逆元：时间复杂度是 $ O(p) $。注意：p是素数。
推导如下：首先，$1^{-1} \equiv 1\;(mod\;p)$。
那么 $ \forall \;i \in [2,p-1]$，必 $\exists\; k,r$，使得 $ p=k \times i + r$，其中 $ k,r \in \mathbb{Z} \land r < i$。
$\because p \equiv 0\;(mod\;p) $，$\therefore k \times i + r \equiv 0\;(mod\;p)$，
恒等式两边同乘以 $ i^{-1} \cdot r^{-1} $ 得 $ k\cdot r^{-1} + i^{-1} \equiv 0 \;(mod\; p) $
$ \Rightarrow i^{-1} \equiv -k\cdot r^{-1} \;(mod\; p) \Rightarrow i^{-1} \equiv (p-\left\lfloor\frac{p}{i}\right\rfloor)\cdot \left(p\bmod i\right)^{-1} \;(mod \;p) $（取正整数）。