哈哈哈还是数论

这个系列到4了dxd的责任(bushi)

请先阅读[前言]后再阅读本博客

前言

积性函数

定义

在数论中，若函数 $f(n)$ 满足 $f(1)=1$，且 $f(xy)=f(x)f(y)$ 对任意互质的 $x$,$y \in\mathbf{N}^*$ 都成立，则 $f(n)$为 积性函数。

在数论中，若函数 $f(n)$ 满足 $f(1)=1$ 且 $f(xy)=f(x)f(y)$ 对任意的 $x$,$y \in\mathbf{N}^*$ 都成立，则 $f(n)$ 为 完全积性函数。

性质

若 $f(x)$ 和 $g(x)$ 均为积性函数，则以下函数也为积性函数：

$$\begin{aligned} h(x)&=f(x^p)\\ h(x)&=f^p(x)\\ h(x)&=f(x)g(x)\\ h(x)&=\sum_{d\mid x}f(d)g\left(\dfrac{x}{d}\right) \end{aligned} $$

对正整数 $x$，设其唯一质因数分解为 $x=\prod p_i^{k_i}$，其中 $p_i$ 为质数。

若 $F(x)$ 为积性函数，则有 $F(x)=\prod F(p_i^{k_i})$。

若 $F(x)$ 为完全积性函数，则有 $F(x)=\prod F(p_i^{k_i})=\prod F(p_i)^{k_i}$。

例子

• 单位函数：$\varepsilon(n)=[n=1]$。（完全积性）
• 恒等函数： $\operatorname{id}_k(n)=n^k$，$\operatorname{id}_{1}(n)$ 通常简记作$\operatorname{id}(n)$。（完全积性）
• 常数函数：$1(n)=1$。（完全积性）
• 除数函数： $\sigma_{k}(n)=\sum_{d\mid n}d^{k}$。$\sigma_{0}(n)$ 通常简记作 $d(n)$ 或 $\tau(n)$，$\sigma_{1}(n)$ 通常简记作 $\sigma(n)$。
• 欧拉函数：$\varphi(n)=\sum_{i=1}^n[(i,n)=1]$。
• 莫比乌斯函数：$\mu(n)=\begin{cases}1&n=1\\0&\exists d>1,d^{2}\mid n\\(-1)^{\omega(n)}&\text{otherwise}\end{cases}$，其中 $\omega(n)$ 表示 $n$的本质不同质因子个数。

铺垫完毕，接下来是正题:

欧拉函数

定义

欧拉函数（Euler's totient function），即 $\varphi(n)$，表示的是小于等于 $n$ 和 $n$ 互质的数的个数。 比如说 $\varphi(1) = 1$。 当 $n$是质数的时候，显然有 $\varphi(n) = n - 1$。

性质

• 欧拉函数是积性函数。

即对任意满足 $\gcd(a, b) = 1$ 的整数 $a,b$，有 $\varphi(ab) = \varphi(a)\varphi(b)$。

特别地，当 $n$ 是奇数时 $\varphi(2n) = \varphi(n)$。

• $n = \sum_{d \mid n}{\varphi(d)}$。

===================================

证明

利用莫比乌斯反演相关知识可以得出。

也可以这样考虑：如果 $\gcd(k, n) = d$，那么$\gcd(\dfrac{k}{d},\dfrac{n}{d}) = 1, ( k < n )$。

如果我们设 $f(x)$ 表示 $\gcd(k, n) = x$的数的个数，那么 $n = \sum_{i = 1}^n{f(i)}$。

根据上面的证明，我们发现，$f(x) = \varphi(\dfrac{n}{x})$，从而$n = \sum_{d \mid n}\varphi(\dfrac{n}{d})$。注意到约数$d$和$\dfrac{n}{d}$ 具有对称性，所以上式化为 $n = \sum_{d \mid n}\varphi(d)$。

=====================================

• 若$n = p^k$，其中$p$ 是质数，那么 $\varphi(n) = p^k - p^{k - 1}$。 （根据定义可知）

• 由唯一分解定理，设 $n = \prod_{i=1}^{s}p_i^{k_i}$，其中 $p_i$ 是质数，有 $\varphi(n) = n \times \prod_{i = 1}^s{\dfrac{p_i - 1}{p_i}}$。

=====================================

证明

引理：设 $p$为任意质数，那么$\varphi(p^k)=p^{k-1}\times(p-1)$。

证明：显然对于从 1 到 $p^k$ 的所有数中，除了 $p^{k-1}$个 $p$ 的倍数以外其它数都与 $p^k$ 互素，故 $\varphi(p^k)=p^k-p^{k-1}=p^{k-1}\times(p-1)$，证毕。

接下来我们证明 $\varphi(n) = n \times \prod_{i = 1}^s{\dfrac{p_i - 1}{p_i}}。由唯一分解定理与 \varphi(x) $函数的积性

$$\begin{aligned} \varphi(n) &= \prod_{i=1}^{s} \varphi(p_i^{k_i}) \\ &= \prod_{i=1}^{s} (p_i-1)\times {p_i}^{k_i-1}\\ &=\prod_{i=1}^{s} {p_i}^{k_i} \times(1 - \frac{1}{p_i})\\ &=n~ \prod_{i=1}^{s} (1- \frac{1}{p_i}) &\square\end{aligned}$$

===================================

• 对任意不全为 $0$ 的整数 $m$,$n$，$\varphi(mn)\varphi(\gcd(m,n))=\varphi(m)\varphi(n)\gcd(m,n)$。 可由上一条直接计算得出。

实现:

c++代码：

int euler_phi(int n) {
  int ans = n;
  for (int i = 2; i * i <= n; i++)
    if (n % i == 0) {
      ans = ans / i * (i - 1);
      while (n % i == 0) n /= i;
    }
  if (n > 1) ans = ans / n * (n - 1);
  return ans;
}

py代码:

import math


def euler_phi(n):
    ans = n
    for i in range(2, math.isqrt(n) + 1):
        if n % i == 0:
            ans = ans // i * (i - 1)
            while n % i == 0:
                n = n // i
    if n > 1:
        ans = ans // n * (n - 1)
    return ans