数论学习笔记
Lyrith_with_xQ
·
·
算法·理论
欧拉函数
欧拉函数的定义 (\varphi(x))
定义函数 \varphi(n) 为与 n 互质的数的个数 。
求欧拉函数的值
把一个数 n 按照算术基本定理分解为 P_1^{\alpha_1}\times P_2^{\alpha_2}\times \cdots\times P_k^{\alpha_k} 后，可以得出：
\varphi(n)= n\prod^k_{i=1}\frac {P_i-1} {P_i}
欧拉函数的线性推导
前置知识：素数的线性筛。
可以发现，\varphi(1)=1，一个素数 x 的欧拉函数 \varphi(x)=x-1。
这里定义一个素数 P_j，则：
当 i\bmod P_j=0 时，i\times P_j 的质因子数和 i 一样，所以 \varphi(i\times P_j)=i\times P_j\times\prod^k_{i=1}\frac {P_i-1} {P_i}=P_j\times \varphi(i)。
当 i\bmod P_j\ne0 时，i\times P_j 的质因子数比 i 多了个 P_j，所以 \varphi(i\times P_j)=i\times P_j\times \prod^k_{i=1}\frac {P_i-1} {P_i}\times \frac {P_j-1} {P_j}=(P_j-1)\times \varphi(i)。
可以把这两个性质应用进素数线性筛中实现 O(n) 复杂度推导出 \varphi(1) 到 \varphi(n) 的值。
因数和函数
因数和函数 (\sigma(x))
定义函数 \sigma(x)=\sum^x_{d\mid x} d。
求因数和函数的值
把一个数 n 按照算术基本定理分解为 P_1^{\alpha_1}\times P_2^{\alpha_2}\times \cdots \times P_k^{\alpha_k} 后，可以知道这个数 n 的所有因数都可以表示为 P_1^{\beta_1}\times P_2^{\beta_2}\times\cdots\times P_k^{\beta_k} 的形式 (0\le \beta_i\le \alpha_i)。
把这些因数的和进行几轮提取公因数，最后可以得到：
\sigma(x)=\prod_{i=1}^{k}\sum_{j=0}^{\alpha_i}P_i^j
欧拉定理
欧拉定理
当 a 和 n 互质时，有a^{\varphi(n)}\equiv1\pmod {n}。
证明：
设一个序列 A=\{a_1,a_2,a_3,\cdots,a_{\varphi(n)}\} 且 A 中所有数与 n 互质且小于 n。
设另一个序列 B=aA，可以发现这个序列有以下特点：
并且 aa_i\bmod n=a_i。
所以可以得到以下关系：
a\prod^{\varphi(n)}_{i=1}a_i&\equiv \prod^{\varphi(n)}_{i=1}a_i\pmod {n}\\
a^{\varphi(n)} &\equiv1\pmod {n}
\end{aligned}
证毕。
逆元
费马小定理
当 a 和 n 互质时且 n 是质数时，有a^{n-1}\equiv1\pmod {n}。
逆元
当 \frac a b\equiv ax\pmod {n} 时，称 x 为 b \bmod n 的逆元，记作 b^{-1}。
（在计算时可以把 b^{-1} 看成 \frac 1 b 但是 b^{-1} 真的不是 \frac 1 b）
当 b,n 不互质时，b \bmod n 的逆元不存在。
证明：
设 y=-\lfloor\frac b n\rfloor\times n，则可以把 \frac a b\equiv ax\pmod {n} 变形为 bx+ny=1。
设 g=\gcd(b,n)，则有 g \mid b 和 g \mid n，则有 g \mid bx+ny，即 g \mid 1。
因为 b,n 不互质，所以有 g>1，与前面的结论 g \mid 1 矛盾，所以当 b,n 不互质时，b \bmod n 的逆元不存在。
证毕。
逆元的求法
当 n 为质数时，b \bmod n 的逆元为 b^{n-2}。
证明：
首先把 \frac a b\equiv ax \pmod {n} 变形为 bx\equiv 1\pmod {n}。
把费马小定理变形为 a\times a^{n-2}\equiv 1\pmod {n} 后，设 a=b，则有 x=b^{n-2}。
证毕。
逆元的线性推导
可以发现，1^{-1} \equiv1\pmod{p}。
定义 p=ax+b，其中 a=\lfloor\frac p x\rfloor，b=p \bmod x，因为 p\equiv0 \pmod{p}，所以 ax+b\equiv0 \pmod{p}。
再把 ax+b\equiv0 \pmod{p} 两边同乘 x^{-1}b^{-1}，可以得到 x^{-1}\equiv-ab^{-1}\pmod{p}，因为 b=p\bmod x 且 p\bmod x<x，所以 b^{-1} 在推导 x^{-1} 之前已经被推导过，那么我们就可以用 x^{-1}\equiv-ab^{-1}\pmod{p} 作为递推式在 O(n) 的时间内推出 1 到 n 之间的所有膜 p 意义下的逆元了。
裴蜀定理
定义
对于任意数 a,b，一定存在一组不同时为 0 的数 x,y，使得 ax+by=\gcd(a,b)。
证明：
设 g=\gcd(a,b)，m=ax+by，则需要证明 g=m，即g\le m 和 g\ge m。
因为 $g=\gcd(a,b)$，所以有 $g\mid a$ 和 $g\mid b$。
因为有 $g\mid a$ 和 $g\mid b$，所以有 $g\mid ax+by$，即 $g\mid m$，所以 $g\le m$。
$g\ge m$ 的证明：
因为 $m=ax+by$，所以 $m\mid ax+by$。
因为 $m\mid ax+by$，所以有 $m\mid a$ 和 $m\mid b$，所以 $m$ 是 $a,b$ 的一个公约数，所以有 $m\mid g$，所以 $g\ge m$。
因为有 $g\le m$ 和 $g\ge m$，所以 $m=g$，即 $ax+by=\gcd(a,b)$。
证毕。
### 裴蜀定理的通解
设 $g=\gcd(a,b)$。
显然可知，裴蜀定理的通解为 $x=x_0+\frac b d\times k$ 和 $y=y_0-\frac a d\times k$。
只需要求出其中一组 $x_0$ 和 $y_0$ 即可求出 $ax+by=g$ 的所有解。
### 裴蜀定理的求解 (扩展欧几里得定理)
根据裴蜀定理，有 $ax+by=\gcd(a,b)$。
根据上面的式子，可以得出 $bx+y(a-\lfloor\frac a b\rfloor\times b)=\gcd(b,a \bmod b)$。
从这个式子可以推导出 $ay+b(x-\lfloor\frac a b\rfloor\times y)=\gcd(b,a \bmod b)$。
定义 $x'=y$，$y'=x-\lfloor\frac a b\rfloor\times y$ 后，可以得出 $ax'+by'=\gcd(b,a \bmod b)
我们可以把这个式子作为递推式，边界就是 b=0，b=0 时的答案为 x=1,y=0。
一元一次同余方程
定义
一元一次同余方程是形似 ax\equiv b\pmod {n} 的方程。
一元一次同余方程的求解
设 y=-\lfloor\frac x m\rfloor\times n，则可以把 ax\equiv b\pmod {n} 变形为 ax+my=b。
设 g=\gcd(a,m)，则根据裴蜀定理，ax_1+my_1=g 的解一定存在，用扩展欧几里得算法求出 x_1,y_1 的值后，根据裴蜀定理的通解，可以求出 x 的值。
当 b \bmod g\ne0 时，一元一次同余方程无解。
2024.3.24 记