欧拉函数

Author Avatar
2U Aug 13, 2019
  • Read this article on other devices

欧拉函数

本文转载自 Wikipedia

在数论中,对正整数n,欧拉函数 ${\displaystyle \varphi (n)}$ 是小于或等于n的正整数中与n互质的数的数目。此函数以其首名研究者欧拉命名,它又称为φ函数(由高斯所命名)或是欧拉总计函数(totient function,由西尔维斯特所命名)。

例如 ${\displaystyle \varphi (8)=4}$ ,因为1,3,5,7均和8互质。

欧拉函数实际上是模n的同余类所构成的乘法群(即环 ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ 的所有单位元组成的乘法群)的阶。这个性质与拉格朗日定理一起构成了欧拉定理的证明。

历史:欧拉函数与费马小定理

1736年,欧拉证明了费马小定理:

假若 ${\displaystyle p}$ 为质数, ${\displaystyle a}$ 为任意正整数,那么 ${\displaystyle a^{p}-a}$ 可被 ${\displaystyle p}$ 整除。

然后欧拉予以一般化:

假若 ${\displaystyle a}$ 与 ${\displaystyle n}$ 互质,那么 ${\displaystyle a^{\varphi (n)}-1}$ 可被 ${\displaystyle n}$ 整除。亦即,${\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}}$ 。其中 ${\displaystyle \varphi (n)}$ 即为欧拉总计函数。如果 ${\displaystyle n}$ 为质数,那么 ${\displaystyle \varphi (n)=n-1}$ ,因此,有高斯的版本:

假若 ${\displaystyle p}$ 为质数, ${\displaystyle a}$ 与 ${\displaystyle p}$ 互质( ${\displaystyle a}$ 不是 ${\displaystyle p}$ 的倍数),那么 ${\displaystyle a^{p-1}\equiv 1{\pmod {p}}}$ 。

欧拉函数的值

${\displaystyle \varphi (1)=1}$ (小于等于1的正整数中唯一和1互质的数就是1本身)。

若n是质数p的k次幂, ${\displaystyle \varphi (n)=\varphi (p^{k})=p^{k}-p^{k-1}=(p-1)p^{k-1}}$ ,因为除了p的倍数外,其他数都跟n互质。

欧拉函数是积性函数,即是说若m,n互质, ${\displaystyle \varphi (mn)=\varphi (m)\varphi (n)}$ 。证明:设A, B, C是跟m, n, mn互质的数的集,据中国剩余定理, ${\displaystyle A\times B}$ 和 ${\displaystyle C}$ 可建立双射(一一对应)的关系。(或者也可以从初等代数角度给出欧拉函数积性的简单证明)因此 ${\displaystyle \varphi (n)}$ 的值使用算术基本定理便知,

若 ${\displaystyle n=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}}}$

${\displaystyle \varphi (n)=\prod _{i=1}^{r}p_{i}^{k_{i}-1}(p_{i}-1)=\prod _{p\mid n}p^{\alpha _{p}-1}(p-1)=n\prod _{p|n}\left(1-{\frac {1}{p}}\right)}$ 。

其中 ${\displaystyle \alpha _{p}}$ 是使得 ${\displaystyle p^{\alpha }}$ 整除 ${\displaystyle n}$ 的最大整数 ${\displaystyle \alpha }$ (这里 ${\displaystyle \alpha _{p_{i}}=k_{i}}$ )。

例如

${\displaystyle \varphi (72)=\varphi (2^{3}\times 3^{2})=2^{3-1}(2-1)\times 3^{2-1}(3-1)=2^{2}\times 1\times 3\times 2=24}$

性质

n的欧拉函数 ${\displaystyle \varphi (n)}$ 也是循环群 Cn 的生成元的个数(也是n阶分圆多项式的次数)。Cn 中每个元素都能生成 Cn 的一个子群,即必然是某个子群的生成元。而且按照定义,不同的子群不可能有相同的生成元。此外, Cn 的所有子群都具有 Cd 的形式,其中d整除n(记作d | n)。因此只要考察n的所有因数d,将 Cd 的生成元个数相加,就将得到 Cn 的元素总个数:n。也就是说:

${\displaystyle \sum _{d\mid n}\varphi (d)=n}$

其中的d为n的正约数。

运用默比乌斯反转公式来“翻转”这个和,就可以得到另一个关于 ${\displaystyle \varphi (n)}$ 的公式:

${\displaystyle \varphi (n)=\sum _{d\mid n}d\cdot \mu (n/d)}$

其中 μ 是所谓的默比乌斯函数,定义在正整数上。

对任何两个互质的正整数a, m(即 gcd(a,m) = 1), ${\displaystyle m\geq 2}$ ,有

${\displaystyle a^{\varphi (m)}\equiv 1{\pmod {m}}}$

即欧拉定理。

这个定理可以由群论中的拉格朗日定理得出,因为任意与m互质的a都属于环 ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ 的单位元组成的乘法群 ${\displaystyle \mathbb {Z} /n\mathbb {Z} ^{\times }}$

当m是质数p时,此式则为:

${\displaystyle a^{p-1}\equiv 1{\pmod {p}}}$

即费马小定理。

void get_euler() //Version 1 打表
{
    for (int i = 1; i < maxn; i++)
        phi[i] = i;
    for (int i = 2; i < maxn; i++)
        if (phi[i] == i)
            for (int j = i; j < maxn; j += i)
                phi[j] = phi[j] / i * (i - 1);
}

ll euler(int n) //Version 2
{
    ll res = 1;
    for (int i = 2; i <= sqrt(n); i++)
    {
        if (n % i == 0)
        {
            n /= i; res *= i - 1;
            while (n % i == 0) { n /= i; res *= i; }
        }
    }
    if (n > 1) res *= n - 1;
    return res;
}

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
Link to this article: https://www.singularity2u.top/2019/08/13/欧拉函数/