数论之欧拉函数

发表于 | 更新于 | 分类于 | 阅读次数：

欧拉函数，用$\phi(n)$ 表示 ，指的是小于等于n的数中与n互质的数的数目，欧拉函数是一个积性函数.
$$
\phi(x) = x \times (1 -\frac{ 1}{p_1}) + x \times(1-\frac{1}{p_2}) +x \times(1 - \frac{1}{p_n})
$$

这里介绍一些相关的知识:

1.一个算术函数f，如果对于两个互素整数m,n有f(nm)=f(n)f(m)则称 f为积性函数。如果对于任意两个正整数mn有f(nm)=f(n)f(m)则称f为完全积性函数 。

2.如果f是一个积性函数，则对于正整数$$ n = p_1^{a_1} \times p_2^{a_2} \times p_n^{a_n}$$（pi为素数）(这里是唯一分解定理)，则$$ f(n)=f(p_1^{a_1})\times f(p_2^{a_2}) \times f(p_n^{a_n}) $$

欧拉函数

现在回归欧拉函数，看公式中的字母：

其中p指的是x的质因子。（注意的是$\phi(1) = 1$，当两个数字的公因数只有1的时候，就说两个数字互质）

接下来介绍几种欧拉函数的求法：

分解质因数求欧拉函数:

注意的是，如果最终n>1， 说明n也是一个质因子了，那么就要把它也算进去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int main()
{
    int n;
    cin >> n;
    int ans = n;
    for(int i = 2; i * i <= n; ++i)
    {
        if(n % i == 0)
        {
            ans = ans /i * (i - 1);        //kuangbin中是ans -= ans/i;  这个肯定不会溢出
            while(n % i == 0)
                n /= i;
        }
    }
    if(n > 1) ans = ans / n * (n - 1);         
    cout << ans << '\n';
}

欧拉函数打表（类似埃氏筛法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void getphi(int n)
{
    for(int i = 1; i <= n; ++i)
        phi[i] = i;
    for(int i = 2; i <= n; ++i)
    {
        if(phi[i] == i)
        {
            for(int j = i; j <= n; j += i)
            {
                phi[j] = phi[j]/i * (i - 1);
            }
        }
    }
}

欧拉函数线性筛法（可以得到欧拉函数和素数表）

需要用到以下三条性质，这里不作证明(第一条p为质数)

  1. $$phi[p] = p - 1$$

  2. $$ i \mod p = 0 \to phi[i \times p] = phi[i] \times p$$

  3. $$ i \mod p \ne 0 \to phi[i \times p] = phi[i] \times (p - 1)$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int phi[10005];
const int N = 10000;
int tot;
int is[N + 5];
int pri[N + 5];
void getphi()
{
    memset(is, 0, sizeof(is));
    phi[1] = 1;
    is[0] = is[1] = 1;
    tot = 0;
    for(int i = 2; i <= N; ++i)
    {
        if(!is[i])
        {
            pri[++tot] = i;
            phi[i] = i - 1;
        }
        for(int j = 1; j <= tot && i * pri[j] <= N; ++j )
        {
            is[i * pri[j]] = 1;
            if(i % pri[j] == 0)
                phi[i * pri[j]] = phi[i] * pri[j];
            else
                phi[i * pri[j]] = phi[i] * (pri[j] - 1);
            if(i % pri[j] == 0) break;
        }
    }
}

欧拉函数的重要性质:

  1. 若N是质数X的K次幂，$$phi[N] = (X - 1)\times X ^{k - 1}$$
  2. 若M,N互质， 那么 $$ phi[M \times N] = phi[M] \times phi[N]$$
  3. 若N是奇数， 那么$$ phi[2 \times N] = phi[N]$$
  4. 若X,Y是质数，且$$N = X \times Y , phi[N] = (x - 1) \times (y - 1)$$
  5. 小于N且与N互质的数的和为： $$N/2 \times phi[N]$$

欧拉定理

对于和m 互质的 x ，有 $$ x ^{\phi(m)}\equiv 1\mod m$$

当m 为素数时， $$phi[m] = m - 1$$ 所以有 $$ x^{m - 1} \equiv 1(\mod m)$$

这就是费马小定理，所以说费马小定理是欧拉定理的特殊形式。

欧拉定理的应用

$$ a^b \mod p = (a \mod p)^{b \mod \phi(p)} \mod p$$ //a和p互质

如果p为质数：

$$ a^b \mod p = (a \mod p)^{b \mod (p - 1)} \mod p $$

还有一个真伪性我还没有验证的公式，先记录下来:

$$ a^b\mod p = (a\mod p )^{\phi(p) + b \mod \phi(p)} \mod p $$ //这里可以摆脱a 和 p互质的束缚