欧拉定理 拓展欧拉定理

发表于 更新于 分类于

欧拉定理 拓展欧拉定理

算数基本定理

算术基本定理，又称唯一分解定理

定理内容是：

任何一个大于1的自然数\(N\)，如果\(N\)不为质数，都可以唯一分解成有限个质数的乘积\(N = P_1^{a_1} P_2^{a_2} \dots P_n^{a_n}\)。这里\(P_1 < P_2 < \dots < P_n\)均为质数，指数\(a_i\)均为正整数。 ## 欧拉线性筛

线性筛法求素数

for(int i=2;i<N;i++){
  if(!vis[i])p[++cnt]=i;      //若未被标记，则i为质数
  for(int j=1;j<=cnt && i*p[j]<N;j++){
    vis[i*p[j]]=1; //打上合数标记
    if(i%p[j]==0)break;       //p[j]为i的约数时退出
  }
}

欧拉函数

欧拉函数（Euler’s totient function）

欧拉函数是小于或等于\(n\)的正整数中与\(n\)互质的数的数目（故\(\varphi(1) = 1\)），记为\(\varphi(n)\)。

欧拉函数的通式：\(\varphi(x) = x \cdot \prod_{i=1}^{n} \left(1 - \frac{1}{p_i}\right)\)

eg: 1,5,7,11 12*(1-1/2)(1-1/3)

证明

欧拉函数的证明

情况1、如果n是一个素数（即n=p），显然——

\[\varphi(n) = p - 1 = p(1 - 1/p) = n(1 - 1/p)\]

公式成立！

情况2、如果n是一个素数p的\(\alpha\)次幂，那么—— 从1到n中，只有p的倍数不与n互质。从1到n，p、2p、3p、……、\(p^{\alpha - 1}p\)这些是p的倍数，一共有\(p^{\alpha - 1}\)个，所以：

\[\varphi(n) = n - p^{\alpha - 1} = p^\alpha - p^{\alpha - 1} = p^\alpha(1 - 1/p) = n(1 - 1/p)\]

公式依然成立！

情况3、n是两个素数的乘积，设\(n = p * q\)，显然——

此时与n互质的数既不是p的倍数，也不是q的倍数。类似情况2中的分析，p的倍数应有q个，q的倍数有p个，但是还多算了一个即是p也是q的倍数的数，即n自己。于是——

\[ \varphi(n) = n - (p + q - 1) = p * q - p - q + 1 = (p - 1)(q - 1) = n(1 - 1/p)(1 - 1/q) \]

公式继续成立！

注意观察的话，还可以发现——

\[ \varphi(n) = \varphi(p * q) = p * q(1 - 1/p)(1 - 1/q) = \varphi(p) * \varphi(q) \]

欧拉函数是积性函数有着乘法性质 积性函数：对于指定条件有效 完全积性函数：是对于任何因子有效

情况4、n是某个m和一个与m互质的素数p的乘积，即n=m*p

情况4的证明比较复杂，我们这里利用以后的一个结论（欧拉函数是积性函数）非正规模式反向验证一下：

假设m是之前讨论的情况，即m满足欧拉函数公式:

\[\varphi(m) = m \cdot \prod_{i=1}^k \left(1 - \frac{1}{p_i}\right)\]

同时，因为n=m*p，m与p互质，则有：

\[\varphi(n)=\varphi(m * p)=\varphi(m)*\varphi(p)\]

另外，由情况1可知 \[\varphi(p)=p-1=p(1-1/p)\]

显然，\(\varphi(m)*\varphi(p)\)得到的公式，依然满足欧拉函数。

代码实现

欧拉函数参考代码

int euler(int n) { //求正整数n的欧拉函数（类似常规的素数判定）
    int i, ret = n;
    for(i = 2 ; i*i <= n; i++){ //因为和因子有关，所以只需根号n内
        if(n % i == 0){ //找到一个因子i
            ret = ret - ret / i; //减去因子i相关的数
            while(n % i == 0)   n /= i; //去除所有的因子i
        }
    }
    if(n > 1) ret = ret - ret / n; //比如原始n=10，最后一个因子5
    return ret;
}

复杂度：O(sqrtn)

特殊性质

欧拉函数的两个重要性质：

当\(i\)与\(P_j\)互质时，有\(\varphi(i \cdot P_j) = \varphi(i) \cdot (P_j - 1)\)

当\(i\)为\(P_j\)的倍数时，则有\(\varphi(i \cdot P_j) = \varphi(i) \cdot P_j\)

为什么？（证明中的情况4和情况5）

欧拉函数的上述性质，同时给出了欧拉函数的另外一种求法——

可以用类似线性筛素数的方式线性求所有欧拉函数的值

线性求解代码

欧拉函数的线性求法

for(int i=2;i<=N;i++){
  if(!vis[i]) p[++cnt]=i,phi[i]=i-1;  //$\varphi(p) = p - 1$
  for(int j=1;j<=cnt && i*p[j]<=N;j++){
      vis[i*p[j]]=1;
      if(i%p[j]==0){phi[i*p[j]]=phi[i]*p[j];break;}
      phi[i*p[j]]=phi[i]*(p[j]-1);
  }
}

复杂度：O(n)

例题1

题目描述： 欧拉函数是数论中的一种重要函数，现在用\(φ(n)\)表示小于\(n\)且与\(n\)互质的数的数量。现在有一个简单的问题：给定\(a,b\)，请尝试计算\(φ(a)+φ(a+1)+ \dots +φ(b)\)

输入描述： 包含多组测试用例；             每组是两个整数\(a,b\)（\(2 < a < b < 3 \times 10^6\)）。

输出描述： 请计算\(φ(a)+φ(a+1)+ \dots +φ(b)\)的结果。

思考回答： 算法思想是？

线性计算+前缀和

例题2

  • 给出一些数字，对于每个数字\(a_i\)找到一个数\(j > 1\)使得\(\varphi(j) \geq a_i\)，求\(\min \{\sum j\}\)。

  • 解题思路？

  • 通过线性筛预处理欧拉函数的值，然后，多次倒着取min即可（后缀最小值）。

线性+2分最优解

欧拉定理

欧拉定理（Euler Theorem）

若\(n,a\)为正整数，且他们互质，则 \[ a^{\varphi(n)} \equiv 1 \pmod{n} \]

显然，当\(n\)为质数时就是费马小定理的内容

证明过程

设与\(n\)互质的\(\varphi(n)\)个数分别为\(x_1, x_2, x_3, \dots, x_{\varphi(n)}\)，并令\(p_i = a \cdot x_i\)

现给出如下两个引理 引理一：\(x_i\)两两不同余，\(p_i\)两两不同余 引理二：\(\gcd(n, p_i \bmod n) = 1\)

引理一：\(x_i\)两两不同余，\(p_i\)两两不同余

显然，\(x_i\)是两两不同余的

假设\(p_i\)与\(p_j\)同余，则\(p_i - p_j = kn\)

又\(p_i = a \cdot x_i\)，\(p_i - p_j = a(x_i - x_j) = kn\)

因为\(\gcd(a, n) = 1\)，故\(n \mid (x_i - x_j)\)，矛盾

引理一得证。

引理二：\(\gcd(n, p_i \bmod n) = 1\)

若不然，则有 \(ax_i = kn + r\)，\(\gcd(r, n) > 1\)

\(ax_i - kn = r > 1\)

由 \(\gcd(a, n) = 1\) 及裴蜀定理，有 \(ax_0 - k_0n = 1\)

故 \(x_i = r \cdot x_0\)，与 \(\gcd(x_i, n) = 1\) 矛盾

引理二得证。

eg:12 1 5 7 11 a = 5 5 25 35 55

由于 \(p_i\) 两两不同余，所以 \(p_i \mod n\)，是两两不同的 \(\varphi(n)\) 个数，且他们均与 \(n\) 互质。

于是 \(p_i \mod n\) 与 \(x_i\) 建立了一一对应关系。

故有 \(\prod_{i=1}^{\varphi(n)} p_i \equiv a^{\varphi(n)} \prod_{i=1}^{\varphi(n)} x_i \equiv \prod_{i=1}^{\varphi(n)} x_i \pmod{n}\)

因为 \(\gcd(\prod_{i=1}^{\varphi(n)} x_i, n) = 1\)，所以 \(\prod_{i=1}^{\varphi(n)} x_i\) 的逆元存在。

两边同乘逆元得到 \(a^{\varphi(n)} \equiv 1 \pmod{n}\)，定理得证。

欧拉定理的应用(1)

如果在模运算中有除法，同时模数不是质数，则此时不可以用费马小定理，而是用欧拉定理。

\((b/a) \pmod{n} = (b * x) \pmod{n}\)（x为a的逆元）

当n不是质数的时候，因为\(a^{\varphi(n)} \equiv 1 \pmod{n}\)，所以a模n的逆元x可以表示为\(a^{\varphi(n) - 1}\)。

不是质数时使用欧拉定理进行求解逆元 模运算时有除法

欧拉定理的应用(2)

扩展欧拉定理（用来降幂，又称为欧拉降幂）

\[ a^b \equiv \begin{cases} a^{b \%\varphi(n)} & gcd(a, n) = 1 \\ a^b & gcd(a, n) \neq 1,\ b < \varphi(n) \\ a^{b \%\varphi(n) + \varphi(n)} & gcd(a, n) \neq 1,\ b \geq \varphi(n) \end{cases} \pmod{n} \]

  • 前两项结论显然，现证第三项

扩展欧几里得证明

  • 考虑\(a = p\)为\(n\)的一个质因子的情况

  • 设\(n = s \cdot p^r\)，\(\boldsymbol{\mathrm{gcd}}(s,p) = 1\)，则有\(p^{\boldsymbol{\varphi}(s)} \equiv 1 \pmod{s}\)

  • 显然，有\(\boldsymbol{\varphi}(s) \mid \boldsymbol{\varphi}(n)\)，故\(p^{\boldsymbol{\varphi}(n)} \equiv 1 \pmod{s}\)

  • \(p^{\boldsymbol{\varphi}(n)} = ks + 1,\, p^{\boldsymbol{\varphi}(n)+r} = ks \cdot p^r + p^r = kn + p^r\)

  • 所以\(p^{\boldsymbol{\varphi}(n)+r} \equiv p^r \pmod{n}\)，对任意\(b \geq \boldsymbol{\varphi}(n) \geq r\)就有 \[p^b = p^{b - r + r} \equiv p^{b - r + \boldsymbol{\varphi}(n) + r} = p^{\boldsymbol{\varphi}(n) + b} \pmod{n}\]

  • 因此，\(p^b \equiv p^{b \bmod \boldsymbol{\varphi}(n) + \boldsymbol{\varphi}(n)} \pmod{n}\)

  • 当 \(a = p^k\) 时，则有

  • \(\big(p^k\big)^b = p^{kb} \equiv p^{\varphi(n) + kb} \equiv p^{k\varphi(n) + kb} = \big(p^k\big)^{\varphi(n) + b} \equiv \big(p^k\big)^{b \bmod \varphi(n) + \varphi(n)} \pmod{n}, \quad b \geq \varphi(n),\ k > 0\)

  • 考虑 \(a\) 的标准分解，若 \(a = \prod p_i^{k_i}\)，则对每个 \(p_i^{k_i}\)，均满足 \(\big(p^k\big)^b \equiv \big(p^k\big)^{b \bmod \varphi(n) + \varphi(n)} \pmod{n}\)，累乘起来则得到 \(a^b \equiv a^{b \bmod \varphi(n) + \varphi(n)} \pmod{n}\)，即得证。

功能-大数字快速幂

阅读下面的程序，猜测可能的程序功能

int main(){
    while(~scanf("%lld %s %lld",&a,b,&c)){
        LL len = strlen(b);
        LL p = phi(c);
        LL ans = 0;
        for(LL i = 0 ; i<len ; i++){
            ans = (ans*10 +b[i] -'0')%p;
        }
        ans +=p;
        printf("%lld\n",qpower(a,ans,c));
    }
}

可以看出费马小定理是欧拉定理的特殊情况。

欧拉定理可以用于指数取模

例题3

  • 给定一个长度为n的数组以及若干次询问\(l\)，\(r\)，求：\(a_l^{a_{l+1}^{a_{l+2}^{\cdot^{\cdot^{a_r}}}}} \bmod m\)

  • 递归求解即可，基本思路： 

    LL get(LL l, LL r, LL m)
    {
        if(l==r || m==1) return mo(a[l], m);
        return qow(a[l], get(l+1, r, phi(m)), m);
    }

递归思路

例题4

  • T组询问，每次询问给出一正整数\(p(p<=1\text{e}7)\)，求\(2^{2^{2^{\cdot^{\cdot^2}}}} \mod p\)
  • \(2^{2^{2^{\cdot^{\cdot^2}}}} \equiv 2^{2^{2^{\cdot^{\cdot^2}}} \mod \varphi(p) + \varphi(p)} \pmod{p}\)
  • \(2^{2^{2^{\cdot^{\cdot^2}}}} \equiv 2^{2^{2^{\cdot^{\cdot^2}}} \mod \varphi(\varphi(p)) + \varphi(\varphi(p))} \pmod{\varphi(p)}\)

发现 φ 值不断减小，有终止产生

  • 和上一题一样，递归求解即可；
  • 递归的层次数会不会很大？
  • 根据欧拉函数的2个性质：
    • （1）\(p>2\)时，\(\boldsymbol{\varphi(p)}\)为偶数； （通式可证）
    • （2）\(p\)如果为偶数，\(\boldsymbol{\varphi(p)} <= p/2\) （通式可证）
  • 可以证明：递归层数为\(\boldsymbol{O(log \, p)}\)

小结

1、欧拉线性筛

2、欧拉函数

3、欧拉定理

4、扩展欧拉定理（降）

补充取模性质

一个数对于m取模（A），那么其有充分性的推论是其对于m约数取模的值相同（B） A -》 B