欧拉函数和欧拉定理

欧拉函数是一种定义在正整数域的数论函数，在剩余系的运算中有重要作用。

定义

欧拉函数的符号是 $\varphi$，读作 phi。$\varphi(n)$ 表示在不大于 $n$ 的所有正整数中，与 $n$ 互质的数的个数。需要注意的是，按照这个定义，$\varphi(1)=1$。

欧拉函数是积性函数，对于任意满足 $(a,b)=1$ 的 $a,b$，都有 $\varphi(a\cdot b)=\varphi(a)\cdot\varphi(b)$。

一些基本公式、结论

显然，对于任意质数 $p$，它的欧拉函数值 $\varphi(p)$ 都等于 $p-1$，因为任意小于 $p$ 的数都与 $p$ 互质。不显然地，对于任意正整数 $i$，设其所有质因数分别为 $p_1,p_2,...,p_s$，那 $i$ 的欧拉函数值 $\varphi(i)=i\cdot\prod\limits_{j=1}^s\dfrac{p_j-1}{p_j}$。

引理 1. 若 $p$ 为质数，$k$ 为正整数，则 $\varphi(p^k)=p^k-p^{k-1}$

一个数 $i$ 不与 $p^k$ 互质当且仅当 $p\mid i$，而在 $\left[1,p^k\right]$ 中这样的 $i$ 一共有 $\dfrac{p^k}{p}=p^{k-1}$ 个，所以 $\varphi(p^k)=p^k-p^{k-1}$。

引理 2. 根据唯一分解定理将 $n$ 分解为 $\prod\limits_{i=1}^s{p_i}^{k_i}$，则 $\varphi(n)=n\cdot\prod\limits_{i=1}^s\dfrac{p_i-1}{p_i}$

由于欧拉函数是积性函数

$$\begin{aligned}\varphi(n)&=\prod\limits_{i=1}^s\varphi({p_i}^{k_i})\\&=\prod\limits_{i=1}^s({p_i}^{k_i}-{p_i}^{k_i-1})\\&=\prod\limits_{i=1}^s\left({p_i-1}\right)\cdot{p_i}^{k_i-1}\\&=n\cdot\prod\limits_{i=1}^s\dfrac{p_i-1}{p_i}\end{aligned}$$

引理 2 是计算欧拉函数最一般的公式，根据它可以 $O\left(\sqrt{n}\right)$ 地求出 $\varphi(n)$。

线性筛求欧拉函数

根据欧拉函数的积性和 引理 2，可得对于任意质数 $p$ 有

$$\varphi(n\cdot p)=\begin{cases}\varphi(n)\cdot(p-1)&\text{if }(n,p)=1\\\varphi(n)\cdot p&\text{if }(n,p)\neq 1\end{cases}$$

在筛素数的同时可以求出欧拉函数。

phi[1] = 1;
for(int i = 2; i <= n; ++i){
    if(!vist[i]) prime[++cnt] = i;
    for(int j = 1; j <= cnt; ++j){
        if(i % prime[j])
            phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        else{
            phi[i * prime[j]] = phi[i] * prime[j];
            break;
        }
    }
}

欧拉定理

对于任意 $a,p$ 满足 $(a,p)=1$， $a^{\varphi(p)}\equiv 1\pmod p$。

这一点可以构造证明。设 $\varphi(p)$ 个正整数 $m_1,m_2,\ldots,m_{\varphi(p)}$ 构成 $p$ 的一个既约剩余系，根据既约剩余系的定义可以得到 $(m_i,p)=1$。

对于其中任意两个不同的数 $m_i,m_j$，由于 $(a,p)=1$，$a\cdot (m_i-m_j)\nmid p$。换言之 $a\cdot m_i$ 与 $a\cdot m_j$ 在模 $p$ 意义下不同余。

由于其中的数两两不同余，$a\cdot m_1,a\cdot m_2,\ldots,a\cdot m_{\varphi(p)}$ 也构成 $p$ 的一个既约剩余系。于是 $\prod(a\cdot m_i)\equiv\prod m_i\pmod p$，即 $a^{\varphi(p)}\equiv 1\pmod p$。

费马小定理

对于任意 $a$ 和任意质数 $p$ 满足 $p \nmid a$，$a^{p}\equiv a\pmod p$。

费马小定理是欧拉定理的特殊情况。我们可以用更简洁的数学归纳法来证明它：

显然 $1^{p}\equiv 1\pmod p$。假设我们已经证明 $a^{p}\equiv a\pmod{p}$，根据二项式定理

$$(a+1)^{p}=\sum\limits_{i=0}^{p}\binom{p}{i}\cdot a^i$$

其中的二项式系数 $\binom{p}{i}$，由于 $p$ 与任意可能的 $i$ 互质（除了 $i=0$ 和 $i=p$），因此 $\forall i\neq 0 \text{ 且 } i\neq p,\binom{p}{i}\equiv 0\pmod{p}$，而对于 $i=0$ 和 $i=p$，显然 $\binom{p}{i}=1$。于是可以将原式写作

$$(a+1)^p\equiv a^{p}+1\pmod{p}$$

即

$$(a+1)^p\equiv a+1\pmod p$$

得证。

扩展欧拉定理

对于任意 $a,b,p$，$a^{b}\equiv\begin{cases}a^b&\text{if }b<\varphi(p)\\a^{b\bmod \varphi(p)+\varphi(p)}&\text{if }b\ge\varphi(p)\end{cases}\pmod{p}$

证明略。

嵌套幂

求 $n^{n^{n^{\ldots}}}\bmod p$。

根据扩展欧拉定理

$$n^{n^{n^{\ldots}}}\equiv n^{n^{n^{\ldots}}\bmod \varphi(p)+\varphi(p)}\pmod p$$

而

$$n^{n^{n^{\ldots}}}\equiv n^{n^{n^{\ldots}}\bmod \varphi(\varphi(p))+\varphi(\varphi(p))}\pmod {\varphi(p)}$$

每迭代一次，模数就变为其欧拉函数。可以证明，在 $O(\log p)$ 级别次迭代内，模数可以降至 $1$，此时式子值恒为 $0$。

int solve(int n, int p){
    if(p == 1) return 0; 
    return qpow(n, solve(n, phi[p]) + phi[p]) % p;
}

由于使用了快速幂，时间复杂度为 $O(n\log^2 p)$。类似的式子都可以套用这种方法计算。

例题

上帝与集合的正确用法
炸脖龙I
相逢是问候

评论