欧拉函数、欧拉定理学习笔记

欧拉函数

欧拉函数， \varphi(n) ， \leq n 的与 n 互质的数的个数。

\varphi(n) = \sum \limits _{i=1}^n \left[ i \nmid n \right]

例如， \varphi(1) = 1 ，而对于质数 p ， \varphi(p) = p - 1 .

引理 1

若 p 为质数， \varphi(p^k) = p^k - p^{k-1}

证明：

\forall i \leq p^k ，有 \dfrac{p^k}{p} 个数满足 x \mid p^k 。

形如： 1,2,3,\ldots,p,p+1,p+2,\ldots,2p,\ldots,p^k

因此 \varphi(p^k) = p^k - \dfrac{p^k}{p} = p^k - p^{k-1}

与唯一分解定理关系

由整数唯一分解定理，整数 n 可以写作：

n = \prod \limits _{i=1}^s p_i^{k_i} ，其中 p_i 为质数。

有： \varphi(n) = n \times \prod \limits _{i=1}^{s} \dfrac{p_i - 1}{p_i}

证明：

已知欧拉函数是积性函数。

\varphi(p^k) = p^k - p^{k-1} = p^k \times (1 - \dfrac{1}{p})

\varphi(n) = \prod \limits _{i=1}^s \varphi(p_i^{k_i})

\varphi(n) = \prod \limits _{i=1}^s p_i^{k_i} \times (1 - \dfrac{1}{p_i})

\varphi(n) = \prod \limits _{i=1}^s p_i^{k_i} \times \prod \limits _{i=1}^s (1 - \dfrac{1}{p_i})

\varphi(n) = n \times \prod \limits _{i=1}^s (1 - \dfrac{1}{p_i})

由此可以求单个欧拉函数。

积性函数

积性函数： \forall a,b,\gcd(a,b) = 1 ， \varphi(a\times b) = \varphi(a) \times \varphi(b)

证明：

可以利用中国剩余定理证明欧拉函数的积性。

\forall 0 \leq x < a,0 \leq y < b

\begin{cases} z \equiv x \pmod{a} \ z \equiv y \pmod{b} \end{cases}

z 在 \bmod ab 意义下有唯一解。且每个 z 对应的 x,y 是固定的。

当且仅当 x 与 a 互质且 y 与 b 互质时， z 与 ab 互质。

否则：

当 x 与 a 不互质时，设 x = g \times k_1,a = g \times k_2 ， z = x + a \times k .

z = g \times k_1 + g \times k_2 \times k ，不与 ab 互质。

必要性证毕，接下来证明充分性。

z = x + ak_1

z = y + bk_2

\gcd(a,x) = \gcd(b,y) = 1

由欧几里得算法知， \gcd(x + ak_1,a) = \gcd(a,(x+ak_1) \bmod a)

即 \gcd(z,a) = \gcd(a,x) = 1

同理 \gcd(z,b) = 1

则 z 与 a,b 无公因子，而与 ab 也无公因子。

\gcd(z,ab) = 1

\forall x,y,\gcd(x,a) = 1,\gcd(y,b) = 1 ， \gcd(z,ab) = 1

那么每个与 a 互质的数，任意与一个与 b 互质的数搭配，即可产生唯一的与 ab 互质的数。

根据乘法原理， \varphi(ab) = \varphi(a) \times \varphi(b) .

欧拉定理

费马小定理

若 p 为素数， \gcd(a,p) = 1 ，则 a^{p-1} \equiv 1 \pmod{p} .

对于任意整数 a ，有 a^p \equiv a \pmod{p} .

欧拉定理

若 \gcd(a,m) = 1 ， a^{\varphi(m)} \equiv 1 \pmod{m}

费马小定理是欧拉定理的一种特殊情况，当 m 是素数时， \varphi(m) = m - 1 ， a^{m-1} \equiv 1 \pmod{p} .

扩展欧拉定理

在使用时，一般简化为：

只有 \gcd(a,p) = 1,b \geq \varphi(p) 的情况有所特殊，现证明简化无误：

\because \gcd(a,p) = 1,a^\varphi(p) \equiv 1 \pmod{p} ，

\therefore a^{b \bmod \varphi(p) + \varphi(p)} \equiv a^{b \bmod \varphi(p)} \pmod{p}

线性筛欧拉函数

欧拉筛可以用于筛积性函数。

对于枚举的每个 i ：

若 i 为素数，则 \varphi(i) = i - 1 .

随后用 i 与素数表筛合数。

设 x = i \times j ，其中 j 为素数。

每个 x 都只会被筛到一次，而 j 是它的最小质因子。

i \bmod j = 0 时， i 包含了 x 的所有质因子。

\varphi(x) = n \times \prod \limits _{i=1}^s (1 - \dfrac{1}{p_i})

\varphi(x) = j \times i \times \prod \limits _{i=1}^s (1 - \dfrac{1}{p_i})

\varphi(x) = j \times \varphi(i)

而当 i \bmod j \neq 0 时， i 与质数 j 互质，根据欧拉函数积性有： \varphi(x) = \varphi(i) \times \varphi(j) = \varphi(i) \times (j-1)

将计算欧拉函数的式子塞到线性筛素数的框架中。

#include <cstdio>
const int maxn = 1e7 + 100;
int n, p;
bool notprime[maxn];
int primes[maxn], cnt, phi[maxn];
inline void Euler(int top)
{
    phi[1] = 1, notprime[1] = 1;
    for (int i = 2; i <= top; ++i)
    {
        if (!notprime[i]) primes[++cnt] = i, phi[i] = i - 1;
        for (int j = 1; j <= cnt && i * primes[j] <= top; ++j)
        {
            notprime[i * primes[j]] = 1;
            if ((i % primes[j]) == 0) { phi[i * primes[j]] = phi[i] * primes[j]; break; }
            else phi[i * primes[j]] = phi[i] * (primes[j] - 1);
        }
    }
}
int main()
{
    scanf("%d %d", &n, &p);
    Euler(n);
    int ans = 0;
    for (int i = 1; i <= n; ++i) ans = (ans + 1ll * (phi[i] + i) * (phi[i] + i)) % p;
    printf("%d\n", ans);
    return 0;
}

例题：[SDOI2008]仪仗队

给定 n \times n 的方阵，从 (0,0) 到 (n-1,n-1) ，问从 (0,0) 到任意非 (0,0) 点，共有多少条本质不同的直线。

可以发现图像关于 y=x 对称，可以考虑下半部分的贡献。

本质相同的直线是什么？

设 (0,0) 到 (x_1,y_1) 与 (x_2,y_2) 的直线本质相同，有：

\dfrac{y_1}{x_1} = \dfrac{y_2}{x_2}

\dfrac{x_2}{x_1} = \dfrac{y_2}{y_1} = t

那么 x_2 = x_1 \times t,y_2 = y_1 \times t

当 (x_1,y_1) 是该直线上离原点最近的点时， t 为整数。

并且 \gcd(x_1,y_1) = 1 ，否则设 \gcd(x_1,y_1) = g ，点 (\dfrac{x_1}{g},\dfrac{x_2}{g}) 一定离原点更近。

而对于后方所有点， \gcd(x_2,y_2) = t ，都不计贡献。

单独考虑 x = 0,y = 0,y = x 的情况。

所求即：

可以发现， \sum \limits _{y=1}^{x-1} [\gcd(x,y) = 1] 即欧拉函数， \varphi(x) .

然而，特殊地， x = 1 时， \varphi(x) = 1 ，而应当只有 0 ，特殊设置一下即可。

原式化简为 3 + 2 \times \sum \limits _{x=2}^{n-1} \varphi(x)

特别地，当 n = 1 时，答案为 0 .

#include <cstdio>
const int maxn = 4e4 + 100;
bool notprime[maxn];
int primes[maxn], cnt, phi[maxn];
int n;
inline void euler()
{
    for (int i = 2; i <= n - 1; ++i)
    {
        if (!notprime[i]) primes[++cnt] = i, phi[i] = i - 1;
        for (int j = 1; j <= cnt && primes[j] * i <= n - 1; ++j)
        {
            notprime[i * primes[j]] = 1;
            if ((i % primes[j]) == 0) { phi[i * primes[j]] = phi[i] * primes[j]; break; }
            phi[i * primes[j]] = phi[i] * (primes[j] - 1);
        }
    }
}
int main()
{
    scanf("%d", &n);
    euler();
    long long ans = 0;
    for (int i = 2; i < n; ++i) ans += phi[i];
    ans = ans * 2 + 3;
    if(n == 1) ans = 0;
    printf("%lld\n",ans);
    return 0;
}

例题：洛谷 P5091 扩展欧拉函数模板

求 a^b \pmod{m} ，其中 p \leq 10^{2 \times 10^7} .

可以使用扩展欧拉函数减小指数，以简化计算。

先用质因数分解的方法求出 \varphi(m) ，时间复杂度 O(\sqrt{m}) .

随后边读边模，最后用快速幂求解即可。

#include <cmath>
#include <cstdio>
#include <ctype.h>
#define int long long
const int bufSize = 1e6;
inline char nc()
{
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
inline T read(T& r)
{
    static char c;
    r = 0;
    for (c = nc(); !isdigit(c); c = nc()) ;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r;
}
int a, m, b;
inline int euler(int x)
{
    int top = std::sqrt(x);
    int res = x;
    for (int i = 2; i <= top; ++i)
    {
        if ((x % i) == 0)
        {
            res = res / i * (i - 1);
            while ((x % i) == 0) x /= i;
        }
    }
    if (x != 1) res = res / x * (x - 1);
    return res;
}
inline int mul(int x, int y)
{
    int res = 0;
    for (; y > 0; y >>= 1)
    {
        if (y & 1) res = (res + x) % m;
        x = (x + x) % m;
    }
    if (res < 0) res += m;
    return res;
}
inline int fastpow(int x, int k)
{
    int res = 1;
    for (; k; k >>= 1)
    {
        if (k & 1) res = mul(res, x);
        x = mul(x, x);
    }
    return res;
}
signed main()
{
    read(a), read(m);
    int phi = euler(m);
    static char c;
    b = 0;
    for (c = nc(); !isdigit(c); c = nc());
    bool flag = 0;
    for (; isdigit(c); c = nc())
    {
        b = b * 10 + c - 48;
        if (b >= phi) b %= phi, flag = 1;
    }
    printf("%lld\n", fastpow(a, b + phi * flag));
    return 0;
}