欧拉函数

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 Atimes 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 _{pmid n}p^{alpha _{p}-1}(p-1)=nprod _{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 1times 3times 2=24}$

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

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

其中的d为n的正约数。

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

${displaystyle varphi (n)=sum _{dmid n}dcdot mu (n/d)}$

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

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

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

即欧拉定理。

这个定理可以由群论中的拉格朗日定理得出，因为任意与m互质的a都属于环 ${displaystyle mathbb {Z} /nmathbb {Z} }$ 的单位元组成的乘法群 ${displaystyle mathbb {Z} /nmathbb {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;
}