跟着《算法竞赛进阶指南》学习数论知识做的笔记

之前的那个数论定理只是单纯的记了一下公式，很多公式并不知道是怎么推出来的，所以重新学习一遍

算术基本定理的推论

推论

如果算数基本定理中$N = p_1^{b_1} p_2^{b_2} \cdots p_m^{b_m}$，其中$p$为质数，设$N$的约数和为$S$，则有

$S = (1 + p_1 + p_1^2 + \cdots + p_1^{b_1}) \times \cdots \times (1 + p_m + p_m^2 + \cdots + p_m^{b_m}) = \mathop{\Pi}_{i = 1}^m(\sum_{j = 0}^{c_i}(p_i)^j)$

证明类似于高中的二项式展开，这样展开从每个括号里选一个数出来相乘就包括了$N$的全部约数

题目

给出$1 \leq A, B \leq 5 \times 10^7$，求$A^B$的所有约数和 $mod \ 9901$

欧拉函数

$\phi()$

定义

$\phi(N)$为$1 \cdots N$中和$N$互质的数的个数，即$gcd(x, N) = 1, 1 \leq x \leq N$的$x$的个数

计算

如果算数基本定理中$N = p_1^{b_1} p_2^{b_2} \cdots p_m^{b_m}$，其中$p$为质数，则

$\phi(N) = \mathop{\Pi}_{i = 1}^m (1 - \frac{1}{p_i})$

证明

$1 \cdots N$中$p_1$的倍数有$\frac{N}{p_1}$个， $p_2$的倍数有$\frac{N}{p_2}$个，去掉这两个数的倍数得到的结果多除了既是$p_1$的倍数也是$p_2$的倍数的数，有$\frac{N}{p_1 \times p_2}$个，所以$1 \cdots N$中不和$N$含有共同质因子$p_1, p_2$的数的个数为

$N - \frac{N}{p_1} - \frac{N}{p_2} + \frac{N}{p_1 \times p_2} = N \times (1 - \frac{1}{p_1} - \frac{1}{p_2} + \frac{1}{p_1 \times p_2}) = N \times (1 - \frac{1}{p_1})(1 - \frac{1}{p_2})$

对于三个质因子及以上的情况要用到容斥原理，也类似于高中二项式的展开

一些性质

性质1

内容

任意$n > 1$， $1 \cdots n$中与$n$互质的所有数的和为$\phi(n) \times n / 2$

证明

由于$gcd(n, x) = gcd(n, n - x)$，与$n$互质的$x, n - x$是成对出现的，每一对的和为$n$，由于与$n$互质的数一共有$\phi(n)$个，所以总共的和为$\phi(n) \times n / 2$

性质二

内容

设$p$为质数，若$p | n, p^2 | n$，则$\phi(n) = \phi(n / p) \times p$；若$p | n$但是$p^2$不能整除$n$，则$\phi(n) = \phi(n / p) \times (p - 1)$

证明

$p^2 | n$

因为$p^2 | n$，所以$n / p$必然含有质因子$p$，所以$n$和$n / p$含有完全相同的质因子，那么有
$\phi(n) = n \times (1 - \frac{1}{p}) \cdots$

$\phi(\frac{n}{p}) = \frac{n}{p} \times (1 - \frac{1}{p}) \cdots$

显然有$\phi(n) = \phi(n / p) \times p$

$p^2$不整除$n$

这种情况下$n / p$和$p$是互质的，根据积性函数性质得$\phi(n) = \phi(n \times \frac{n}{p}) = \phi(\frac{n}{p}) \times \phi(p) = \phi(\frac{n}{p}) \times (p - 1)$

性质三

内容

$\sum_{d \mid n} \phi(d) = n$

证明

首先证明$f(n) = \sum\limits_{d \mid n} \phi(d)$是一个积性函数，设$n, m$互质，则有

$f(nm) = \sum_{d \mid nm} \phi(d) = (\sum_{d_1 \mid n} \phi(d_1)) \times (\sum_{d_2 \mid m} \phi(d_2)) = f(n) \times f(m)$

第二个等号的转换由乘法分配律得到，因为$n, m$互质，所以必然$gcd(d_1, d_2) = 1, \phi(d) = \phi(d_1) \times \phi(d_2)$， $nm$的所有因子$d$都可以由$d_1 \times d_2$得到，展开该式就能得到所有的$d$

对于$n$的一个质因子$p$，由性质二有

$\begin{align} f(p^m) & = \sum\limits_{d \mid p^m} \phi(d) = \phi(1) + \phi(p) + \phi(p^2) + \cdots + \phi(p^m) \\ & = 1 + (p - 1) + (p - 1) \times p + \cdots (p - 1) \times p^{m - 1} \\ & = p^m \end{align}$

若在算数基本定理中有$n = p_1^{m_1} p_2^{m_2} \cdots p_b^{m_b}$，则有

$\begin{align} f(n) & = f(p_1^{m_1} p_2^{m_2} \cdots p_b^{m_b}) \\ & = f(p_1^{m_1})f(p_2^{m_2}) \cdots f(p_b^{m_b}) \\ & = p_1^{m_1} p_2^{m_2} \cdots p_b^{m_b} \\ & = n \end{align}$

得证

同余类与剩余系

定义

对于$\forall a \in [0, m - 1]$，集合$\{a + km \}$的所有数模$m$同余，余数都是$a$。该集合称为一个模$m$的同余类，记为$\overline{a}$

模$m$同余类一共有$m$个，分别为$\overline{0}, \overline{1}, \cdots, \overline{m - 1}$，它们构成$m$的完全剩余系

$1 \cdots m$中与$m$互质的数代表的同余系有$\phi(m)$个，它们构成$m$的简化剩余系

简化剩余系

性质

简化剩余系关于模$m$乘法封闭

证明

若$a, b$均与$m$互质，则$a \times b(1 \leq a, b \leq m)$也必然与$m$互质，则$gcd(a \times b, m) = gcd(m, (a \times b) \% m) = 1$，即$(a \times b) \% m$也与$m$互质，即$(a \times b) \%m$也属于$m$的简化剩余系

欧拉定理

内容

若正整数$a, n$互质，则$a^{\phi(n)} \equiv 1 \ (mod \ n)$

证明

设$n$的简化剩余系为$\{\overline{a_1}, \overline{a_2}, \cdots \overline{a_{\phi(n)}} \}$，对$\forall a_i, a_j$，如果$a \times a_i \equiv a \times a_j \ (mod \ n)$，则有$a \times (a_i - a_j) \equiv 0 (mod \ n)$，因为$a, n$互质，得到$a_i - a_j \equiv 0 \ (mod \ n)$，即$a_i \equiv a_j \ (mod \ n)$。故当$a_i \neq a_j$时， $a \times a_i, a \times a_j$也代表了不同的同余类

又因为简化剩余系关于$n$乘法封闭，故$\overline{a a_i}$也在简化剩余系中，因此集合$\{\overline{a_1}, \overline{a_2}, \cdots, \overline{a_{\phi(n)}} \}$和$\{\overline{aa_1}, \overline{aa_2}, \cdots, \overline{aa_{\phi(n)}} \}$都能表示$n$的简化剩余系

由上可得

$a^{\phi(n)}a_1 a_2 \cdots a_{\phi(n)} \equiv (aa_1)(aa_2) \cdots (aa_{\phi(n)}) \equiv a_1 a_2 \cdots a_{\phi(n)} \ (mod \ n)$

所以$a^{\phi(n)} \equiv 1 \ (mod \ n)$得证

推论

内容

若正整数$a, n$互质，则对于任意正整数$b$，有$a^b \equiv a^{b \ mod \ \phi(n)} \ (mod \ n)$

证明

显然，因为之前证明过了$a^{\phi(n)} \equiv 1 \ (mod \ n)$

费马小定理

内容

若$p$是质数，则对于任意整数$a$，有$a^p \equiv a \ (mod \ p)$

证明

由欧拉函数得若$a, p$互质，则$a^{\phi(p)} \equiv 1 \ (mod \ p)$，现在$p$是质数， $\phi(p) = p - 1$，所以有$a^{p - 1} \equiv 1 \ (mod \ p)$，即$a^p \equiv a \ (mod \ p)$

拓展欧几里得算法

贝组定理

内容

对于$\forall a, b$，存在一对整数$x, y$，使得$a \times x + b \times y = gcd(a, b)$

证明

在欧几里得算法的最后一步有$b = 0$，此时显然有$a \times 1 + 0 \times 0 = gcd(a, 0)$

若$b > 0$，则有$gcd(a, b) = gcd(b, a \ mod \ b)$，假设存在一对正整数$x, y$满足$b \times x + (a \ mod \ b) \times y = gcd(b, a \ mod \ b)$

则有

$\begin{align} & b\times x + (a \ mod \ b) \times y \\ & = b \times x + (a - \lfloor \frac{a}{b} \rfloor \times b) \times y \\ & = a \times y + b \times (x - \lfloor \frac{a}{b} \rfloor \times b) \end{align}$

另$x_1 = y, y_1 = x - \lfloor \frac{a}{b} \rfloor \times b$就得到了$a \times x_1 + b \times y_1 = gcd(a, b)$了

推论

方程$a \times x + b \times y = c$有解，当且仅当$gcd(a, b) \mid c$
方程$a \times x + b \times y = c$的通解为
$x = \frac{c}{gcd(a, b)} x_0 + k \frac{b}{gcd(a, b)} \\ y = \frac{c}{gcd(a, b)} y_0 - k \frac{a}{gcd(a, b)}$
其中$x_0, y_0$为拓展欧几里得求出的一组特解

Zth's Blog

数论学习笔记1