数论学习笔记
vvauted
·
·
个人记录
\text{Updated on 2021.11.26}
数论分块
（下面是还未更新完的）
\text{欧拉函数}
定义：
欧拉函数，即 \varphi(n)，代表小于等于 n 的正整数中与 n 互质的个数。
性质：
- 若 n 是质数， \varphi(n) = n - 1。
证明：显然，质数与所有小于它的数互质。
- 若 n 的质因数分解为 {p_1}^{k_1}{p_2}^{k_2}\dots {p_m}^{k_m} ，则
\varphi(n)=n\prod_{i=1}^m (1-\frac 1 {p_i})
证明：
设 S_i=\{x\mid x\leq n, p_i\mid x\}，则有：
\begin{aligned}
\varphi(n)&=n-|\bigcup_{i=1}^m S_i|\\
&= n-\sum_{Q\subset \{1,2,\cdots,m\}} (-1)^{|Q|+1}|\bigcap_{i\in Q}S_i|\\
&= n-\sum_{Q\subset \{1,2,\cdots,m\}} (-1)^{|Q|+1}n\frac{1}{\prod_{i\in Q}p_i}\\
&= n-n\sum_{Q\subset \{1,2,\cdots,m\}} (-1)^{|Q|+1}\frac{1}{\prod_{i\in Q}p_i}\\
&= n\Big(1-\sum_{Q\subset \{1,2,\cdots,m\}} (-1)^{|Q|+1}\frac{1}{\prod_{i\in Q}p_i}\Big)\\
&= n\Big(1+\sum_{Q\subset \{1,2,\cdots,m\}} (-1)^{|Q|}\frac{1}{\prod_{i\in Q}p_i}\Big)\\
&=n\prod_{i=1}^m (1-\frac 1 {p_i})
\end{aligned}
如果实在看不懂，可以感性理解下：
如果我们要求 \varphi(12)，12 = 2^2 \times 3，显然 12 的因数中有一些 2 的倍数，还有一些 3 的倍数，我们把这些删去：
\varphi(12)=12-\frac {12} 2-\frac {12} 3 = 2
显然与 \varphi(12) 不只这么多，因为我们在去掉 2 和 3 倍数时，把 6 的倍数去掉了两遍，如图：
所以我们再给它加回来:
\varphi(12)=12-\frac {12} 2-\frac {12} 3 + \frac{12}{6}= 4
我们稍微变形一下：
\varphi(12)=12(1-\frac 1 2-\frac 1 3 + \frac 1 6)= 4
再运用下数学经验：
\varphi(12)=12(1-\frac 1 2) (1 -\frac 1 3)= 4
就变成了刚才那个式子，所以这个式子是一个容斥的过程，大概理解下就好。
\varphi(xy)=\varphi(x)\varphi(y)
这个式子的证明很简单，利用刚才那个式子：
\varphi(xy)=xy\prod_{i=1}^m (1-\frac 1 {p_i})
因为他俩互质，所以没有公共质因数，分以下即可：
\varphi(xy)=xy\prod_{i=1}^{m_x} (1-\frac 1 {p_{xi}})\prod_{i=1}^{m_y} (1-\frac 1 {p_{yi}}) =\varphi(x)\varphi(y)
有一个更强的结论：
\varphi(xy)=\frac{\varphi(x)\varphi(y)\gcd(x,y)}{\varphi(\gcd(x,y))}
证明：
\begin{aligned}
\varphi(xy)&= xy\prod_{i=1}^{m_{(xy)}} (1-\frac 1 {p_{(xy)i}})\\
&= xy\frac{\prod_{i=1}^{m_x} (1-\frac 1 {p_{xi}})\prod_{i=1}^{m_y} (1-\frac 1 {p_{yi}})}{\prod_{i=1}^{m_{\gcd(x,y)}}(1-\frac 1 {p_{\gcd(xy)i}})}\\
&= \frac{\Big(x\prod_{i=1}^{m_x} (1-\frac 1 {p_{xi}})\Big)\Big(y\prod_{i=1}^{m_y} (1-\frac 1 {p_{yi}})\Big)\gcd(x,y)}{\gcd(x,y)\prod_{i=1}^{m_{\gcd(x,y)}}(1-\frac 1 {p_{\gcd(xy)i}})}\\
&=\frac{\varphi(x)\varphi(y)\gcd(x,y)}{\varphi(\gcd(x,y))}
\end{aligned}
-
n = \sum_{d\mid n}\varphi(d)
证明：
\begin{aligned}
n &= \sum_{d\mid n} \sum_{i=1}^n[\gcd(i,n)=d]\\
&= \sum_{d \mid n} \sum_{i=1}^n[\gcd(\frac i d, \frac n d)=1]\\
&= \sum_{d \mid n} \varphi(\frac n d)\\
&= \sum_{d \mid n} \varphi(d)
\end{aligned}