拓展欧拉定理

文章转载自算法学习笔记(33): 拓展欧拉定理 - 知乎 (zhihu.com)，如有侵权，请联系作者删除。

---

先介绍一下欧拉定理：

若正整数\(a\)与\(m\)互质，则\(a^{\varphi(m)}\equiv 1(mod\ m)\)。

这里的\(\varphi (m)\)指的是欧拉函数，即小于或等于\(m\)且与\(m\)互质的正整数个数。当\(m\)是质数 \(p\)时，欧拉定理退化成费马小定理\(a^{p-1}\equiv1(mod\ p)\) 。

在算法竞赛中，我们常常会用到它的一个重要的推论：若正整数\(a\)与\(m\)互质，则

\(a^b\equiv a^{b\ mod\ \varphi(m)}(mod\ m)\)。

（这是因为\(a^b=a^{\varphi(m)\lfloor b/\varphi(m)\rfloor+b\ mod\ \varphi (m)}\equiv 1·a^{b\ mod\ \varphi(m)}(mod\ m)\)）

利用这个推论，即使\(b\)比较大，我们也可以轻松地算出\(a^b\ mod\ m\)的值，但需要满足\(a\)与\(m\)互质的前提。

---

为了解决\(a\)与\(m\)不互质时的问题，我们引入了拓展欧拉定理：若\(b\geq\varphi(m)\)，则：\(a^b\equiv a^{b\ mod\ \varphi(m)+varphi(m)}\ (mod\ m)\ (*)\)

这里仍有前提条件，但影响不大，因为\(b\leq\varphi (m)\)时直接用快速幂计算即可。

当\(a\)与\(m\)互质时，由于\(a^b\equiv a^{b\ mod\ \varphi(m)}·1\equiv a^{b\ mod\ \varphi(m)}·a^{\varphi(m)}\ (mod\ m)\ (*)\)式显然成立。

当\(a\)与\(m\)不互质时，我们考虑吧\(m\)质因数分解成\({p_1}^{q_1}{p_2}^{q_2}······{p_n}^{q_n}\)，我们只需要证明的每个\({p_i}^{q_i}\)，都有\(a^b\equiv a^{b\ mod\ \varphi(m)+\varphi(m)}(mod\ {p_i}^{q_i})\)即可。因为如果设\(m_1、m_2\)互质，且\(x\equiv y\ (mod\ m_1)\)同时\(x\equiv y\ (mod\ m_2)\)，则\(x\equiv y(mod\ m_1m_2)\)必成立（\(x-y\)既是\(m_1\)的倍数又是\(m_2\)的倍数），所以这里可以进行合并。

现在分类讨论\({p_i}^{q_i}\)：

若\(gcd(a,{p_i}^{q_i})=1\)，则：

\(a^b\equiv a^{\lfloor b/\varphi(m)\rfloor\varphi(m)+b\ mod\ \varphi(m)}\equiv a^{b\ mod\ \varphi(m)}(mod\ {p_i}^{q_i})\)

（注意到\(\lfloor b/\varphi(m)\rfloor\varphi(m)\)必然是\(\varphi ({p_i}^{q_i})\)的倍数，因为欧拉函数是积性函数）

若\(gcd(a,{p_i}^{q_i})\ne1\)，则\(a\)必然是\(p\)的倍数。设\(a=np\)，注意到\(\varphi({p_i}^{q_i})={p_i}^{q_i-1}(p_i-1)\)，则可以证明\(\varphi ({p_i}^{q_i}\geq q_i)\)。则：

\(b\geq \varphi(m) \geq \varphi({p_i}^{q_i})\geq q_i\)

所以\({p_i}^{q_i}\)是\(a^{b\ mod\ \varphi (m)+\varphi(m)}\)的因数，也是\(a^b\)的因数，即：

\(a\equiv a^{b\ mod\ \varphi(m)+\varphi(m)}\equiv 0(mod\ {p_i}^{q_i})\)

综上，\(a^b\equiv a^{b\ mod\ \varphi(m)+\varphi(m)(mod\ m)}(b\geq\varphi(m))\)

代码实现时可以边读入边取模，另外一定要注意这个式子仅在\(b\geq \varphi(m)\)时成立。

#include <bits/stdc++.h>
using namespace std;
bool large_enough = false; // 判断是否有b >= phi(m)
inline int read(int MOD = 1e9 + 7) // 快速读入稍加修改即可以边读入边取模，不取模时直接模一个大于数据范围的数
{
    int ans = 0;
    char c = getchar();
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
    {
        ans = ans * 10 + c - '0';
        if (ans >= MOD)
        {
            ans %= MOD;
            large_enough = true;
        }
        c = getchar();
    }
    return ans;
}
int phi(int n) // 求欧拉函数
{
    int res = n;
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
            res = res / i * (i - 1);
        while (n % i == 0)
            n /= i;
    }
    if (n > 1)
        res = res / n * (n - 1);
    return res;
}
int qpow(int a, int n, int MOD) // 快速幂
{
    int ans = 1;
    while (n)
    {
        if (n & 1)
            ans = 1LL * ans * a % MOD; // 注意防止溢出
        n >>= 1;
        a = 1LL * a * a % MOD;
    }
    return ans;
}
int main()
{
    int a = read(), m = read(), phiM = phi(m), b = read(phiM);
    cout << qpow(a, b + (large_enough ? phiM : 0), m);
    return 0;
}

---

关于欧拉定理的证明我就不放上来了，实在是太难了┭┮﹏┭┮，如果感兴趣的话可以看看原文章：算法学习笔记(33): 拓展欧拉定理 - 知乎 (zhihu.com)