文章总览：坠临万界的星芒

欧拉函数和欧拉定理也是非常基础的数论知识。欧拉函数做为积性函数，并且自身携带欧拉名称加持各种优良性质，被广泛的运用到各个数学推导方面；而欧拉定理更是必不可少，计算逆元是它最基本的运用，它也是凌驾于费马小定理的存在（费马小定理可以从欧拉定理中得出）；并且其拓展即拓展欧拉函数还可以在取模运算中缩小大指数范围，等等等等。接下来我们介绍无所不能的——欧拉函数与欧拉定理。

  1. 欧拉函数推导
  2. 欧拉函数性质
  3. 欧拉函数的计算
  4. 欧拉函数拓展
  5. 欧拉定理推导
  6. 拓展欧拉定理推导

概念基础：因缘假合的人身

欧拉函数基础推导

关于欧拉函数，就从最基础的开始讲起。我们定义函数 $\varphi(n)$ 表示从 $1$ 到 $n$ 的数字中与 $n$ 互质的有多少个。这就是欧拉函数所表示的信息。那么关于欧拉函数我们能有什么已知的值吗？

非常显然的，对于一个质数 $p$，其欧拉函数值 $\varphi(p)=p-1$ 这是显然的，因为 $p$ 作为质数显然与 $1\sim p$ 之间的除了它本身以外任何数字互质。其次有一个容易让人纰漏的点，那就是 $\varphi(1)$。根据欧拉函数的定义，我们要找到区间 $[1,1]$ 中与 $1$ 互素的数的个数，互素的定义就是最大公约数等于 $1$，所以 $\varphi(1)=1$ 是显而易见的。

那么对于非质数的值我们能如何计算呢？由于质数的美妙性质，我们纵使是考虑合数，也一般先从质数的幂次下手，那么对于质数 $p$，我们考虑它的 $k$ 次幂的欧拉函数 $\varphi(p^k)$ 。

显然的在 $[1,p^k]$ 的区间范围内，只要不存在因子 $p$ 的数都与 $p^k$ 互素，也就是说，我们只需要从总量中减去 $p$ 的倍数就可以了。根据小学就学过的容斥原理，在 $[1,p^k]$ 范围内显然质数 $p$ 的倍数有 $p^k/p=p^{k-1}$ 个，那么 $\varphi(p^k)=p^{k}(1-\frac{1}{p})\ $。

这样考虑完了质数的幂次，接下来考虑两个质数相乘的结果，设 $n=pq$ 且 $p,q$ 均为质数。那么我们如果从容斥原理的角度来讲，在 $[1,n]$ 的范围内我们要计算的就是含有质因子 $p,q$ 任意其一的数字的数量。而如果直接从总量减去 $p$ 的倍数再减去 $q$ 的倍数的话，有 $pq$ 为因子的数字就会被减去两边，那么我们就还要把他加回来，然后可以推导出下式：

关于第二步到第三部的转换，只是一个简单的因式分解而已，可以尝试倒推回去验证一下。

然后我们就惊人的注意到不管是质数，质数的幂次，还是两个质数乘积，其答案都表现为了一个共同的值！这难道真的是巧合吗？看下表分析：

我们甚至可以有一个大胆的猜测，$\varphi(n)$ 的计算公式可以是下面这样（其中 $n=\prod_{i=1}^kp_i^{\alpha_i}$ 即整数唯一分解定理拆解 $n$ 的结果，$p_i$ 为 $n$ 所有素因子，$\alpha_i$ 为对应素因子的幂次）

事实上确实如此。为什么这样是对的呢？或者换句话说这个问题的主要来源应该是为什么这样可以正确处理容斥。比较显然的是，展开后的结果中的某一个分数的分母如果是由偶数个因子组成，那么对应符号就是 +，否则是 - 。我们可以观察一下小时候学过的韦恩图或者说文氏图的结构，一眼顶针就可以看出结论。

1~30范围内不同质因数因子的倍数

欧拉函数常见性质

欧拉函数的性质应该是挺多的，首先说一个关于它本身的性质——欧拉函数是积性函数。

定义：什么是积性函数？

若一个函数 $f(x)$ 满足 $f(1)=1$，且当 $\gcd(a,b)=1$ 时，$f(ab)=f(a)f(b)$，则该函数被称为积性函数。特别的，若 $gcd(a,b)\neq 1$ 时，$f(ab)$ 依然满足 $f(ab)=f(a)f(b)$ 则函数 $f(x)$ 被称为完全积性函数。

有了上面的定义其实理解欧拉函数时积性函数并不困难，可以自己代入几个数推导一下。显然的 $\varphi(1)=1$，这是介绍欧拉函数时一开始介绍到的，满足积性函数定义中的第一个条件。那么如果 $(a,b)=1$ 的话，$\varphi(ab)$ 时候会像刚刚积性函数的定义中写的那样 $\varphi(ab)=\varphi(a)\varphi(b)$ 呢？

答案是可以的，在 OI-wiki 中给出了一个使用剩余系的证明，不过我没看懂不过不太好理解，所以我们可用相对简单的方式来验证关于欧拉函数时积性函数的命题，那就是直接套公式。

这个应该没有什么太大的推导难度，所以我们也是直接看下一个性质：$n=\sum_{d\mid n}\varphi(d)$ 。这个式子长得非常恶心，一个求和符号下面带了一个从来没见过的东西，然后把一坨欧拉函数加起来了？这是什么意思？？？？？

简单介绍一下，$d\mid n$ 表示 $d$ 是 $n$ 的约数，那么这个式子的意思就很明显了，不过这是为什么呢？如何证明它？这让我们一头雾水，学过莫比乌斯反演的同志都知道，这是简单一个莫比乌斯反演就可以解决的问题。不过我们跳过莫比乌斯反演，考虑别的证法（绝对不是因为我不会

证明：

如果 $\gcd(a,b)=g$ 那么显然的 $\gcd(\frac{a}{g},\frac{b}{g})=1$。如果我们定义一个新的函数 $f(x)$ 表示区间范围 $[1,n]$ 的数字中满足 $\gcd(k,n)=x$ 的整数 $k$ 的个数。则显然 $f(x)$ 等价于 $\varphi(\frac{n}{x})$，整体除以最大公约数 $x$ 后，这些满足条件的数就变成和 $n$ 互质的了，这满足欧拉函数的定义，所以显然等价。

那么根据 $f$ 的定义，我们其实可以有 $n=\sum_{i=1}^nf(i)$，这是因为我们枚举了这个范围内所有的数作为最大公约数，那么范围内所有数都逃不掉，他们的总和自然是区间的大小 $n$。

又因为等价，所以替换为 $n=\sum_{i=1}^n\varphi(\frac{n}{i})$，由于如果 $i\nmid n$ 那么这个欧拉函数显然没有意义，就可以转化为 $n=\sum_{d\mid n}\varphi(\frac{n}{d})$，但是这个最终的答案还是差了那么一点点，这怎么办？注意到这里的 $d\mid n$ 与 $\varphi(\frac{n}{d})$ 存在对称性，那么等价的就可以换为：

证毕！

这里熟练运用 $\gcd$ 的性质比较常用，一会也要用到，算是比较重要的知识点。除此之外还有最后一个性质，但是这个最后一个性质比较简单，也可以套用通项公式暴力推导求解，所以不讲了，性质放在这，感兴趣的自行推导：

接下来介绍关于欧拉函数的一些小应用。

概念应用：揭示前路的言灵

欧拉函数计算

关于欧拉函数的计算，目前主要的方法是线性筛，这个在我的文章里面讲过，可以去看。

友情链接：

【算法介绍】杜教筛和 Min_25 筛 | 祝馀宫

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<int> pri;
bool isp[N];
int phi[N];

inline void Init(int n) {
    phi[1] = 1;
    for(int i = 2; i <= n; i++) {
        if(!isp[i]) {
            pri.push_back(i);
            phi[i] = i - 1;
        }
        for(auto &p : pri) {
            if(i * p > n) break;
            isp[i * p] = 1;
            if(i % p == 0) {
                phi[i * p] = phi[i] * p;
            	break;
            }
            phi[i * p] = phi[i] * phi[p];
        }
    }
}

欧拉函数反演

这个作为一个拓展内容吧……简单介绍一下，反演就是一种变换式子的方式。我们可以来看一个非常非常基础的例子，首先借用欧拉函数的性质之一：

代入 $n=\gcd(a,b)$，就会得到下面这样的式子：

这显然是等价的，因为一个数 $d$ 如果既是 $a$ 的因子也是 $b$ 的因子那么它一定是最大公约数的因子，不然的话就说明这个最大公约数是假的，还存在更大的公约数。但这不是重点，如果对 $\gcd(i,n)$ 求和，我们会惊喜的发现：

这个过程就被我们称为欧拉反演。

定理基础：凝眸毁灭的瞬间

  • 欧拉定理推导

讲完欧拉函数，我们接下来讲欧拉定理，这两个东西其实关系不算特别大，只是因为欧拉定理需要用到一点点关于欧拉函数的定义，又因为他们都姓欧拉，所以放在一起讲了。欧拉定理的内容大致如下（其中 $a,m$ 互质）

但是在此之前，你一定听过另外一个定理，那就是费马小定理，内容是若 $m$ 为素数，则：

不难发现费马小定理其实就是欧拉定理的特殊情况，这是因为 $\varphi(p)=p-1$ 造就了费马小。我们可以简单的先证明费马小定理，然后尝试能不能从中学习到一些经验最后得到结果。

那么关于定理证明，我们或许第一下想到的就是数学归纳法，这是非常常用的一个技巧。

证明：数学归纳法证明费马小定理。

费马小定理 $a^{p-1}\equiv1\pmod p$ 等价于 $a^p\equiv a\pmod p$。非常显然 $1^p\equiv 1\pmod p$ 是成立的，如果我们假设 $a^p\equiv a\pmod p$ 成立，则有二项式定理可以计算 $(a+1)^p$ ：

这中间很大一坨组合数完全不知道怎么化简，但别忘了，我们要算的是模 $p$ 意义下的结果。显然当 $k\in[1,p)$ 时我们根据组合数的计算公式都可以得到 $C_p^k\equiv0\pmod p$，则该式子在模 $p$ 意义下等价于：

又因为我们假设 $a^p\equiv a\pmod p$ 所以该式化简为 $(a+1)^p\equiv a+1\pmod p$ 证明成立。

但是显然的这个数学归纳的思路是无法拓展到欧拉定理上的，因为二项式定理拆解之后我们无法证明那一坨东西的值在模 $p$ 意义下为 $1$ 。所以如果我们仍然要沿用数学归纳的思路，必须另辟蹊径，注意到我们在推欧拉函数的时候，将数字分为了四类：

  1. $\varphi(1)=1$
  2. $\varphi(p)=p-1$
  3. $\varphi(p^k)=p^k(1-\frac{1}{p})=p^{k-1}(p-1)$
  4. $\gcd(a,b)=1,\varphi(ab)=\varphi(a)\varphi(b)$

那么有一个思路就应运而生：我们将前三类作为数学归纳的基例，那么第四类就显然了。

证明：数学归纳法证明欧拉定理。

按照刚刚的思路我们处理数学归纳的基例。显然的我们这里数学归纳法归纳的不是 $a$ 而是模数 $m$，但这个不影响，因为我们的基例和推导始终都是对所有 $\gcd(a,n)=1$ 的 $a$ 有效的。

基例基础处理

  1. 首先显然的 $\varphi(1)=1$，$a^{1}\equiv 1\pmod 1$ 是显然的，只要 $a$ 是整数都成立。
    不要被这个 $a^1\equiv1\pmod 1$ 迷惑了，这是因为两边在模 $1$ 意义下都为 $0$ 才这么写（
  2. 第二是 $\varphi(p)=p-1$，这时候欧拉定理退化为费马小定理，略。
  3. 接下来是重头戏，只要证明了 $a^{\varphi(p^k)}\equiv 1$，那么就变得特别简单了。

基例特殊情况

那么我们可以对于 $p$ 的幂次 $k$ 进行归纳，这时候的基例就是刚刚的第二例基例即费马小。我们这时候做出归纳假设设对于 $a^{p^{k-1}(p-1)}\equiv1\pmod{p^k}$ 成立，这里是直接用一开始算出来的欧拉函数值把 $\varphi(p^k)$ 替换了。

那么我们的目标就是递推出 $a^{p^k(p-1)}\equiv1\pmod{p^{k-1}}$。因为取模的定义，我们可以把归纳假设成立的式子变换为 $a^{p^{k-1}(p-1)}=1+mp^k$，其中 $m$ 为任意整数。然后我们左右两边各自做上 $p$ 次方：

接下来又是熟悉的操作，我们要证明这玩意在模 $p^{k+1}$ 意义下为 $1$，那么简单的分讨一下：

  1. $1$ 显然在模 $p^{k+1}$ 意义下为 $1$，那么剩下来的部分就都得是 $0$ 。
  2. $C_p^1=p$，代入到那一项刚好是 $mp^{k+1}$ 模 $p^{k+1}$ 的意义下确实是 $0$ 。
  3. 剩下的部分就是 $C_p^i(mp^k)^i$ 其中 $i\in[2,p]$ 的部分了，显然因为 $k\ge 1$ 所以 $2k\ge k+1$ 这就说明这些项也是在模 $p^{k+1}$ 意义下为 $0$ 的。

综上可以得到该式等价于 $a^{p^{k}(p-1)}\equiv1\pmod{p^{k+1}}$，那么对于这一类的基例也就推导完毕了。接下来就是证明欧拉定理的最终阶段。

数学归纳部分

设模数 $m=ab$ 其中 $a,b\gt1$ 且 $\gcd(a,b)=1$，那么假设下面两个等式成立：

为了防止冲突底数从 $a$ 换做了 $x$，含义不变。然后我们在很显然的可以得出下面两个式子：

根据中国剩余定理，我们可以得到 $x^{\varphi(a)\varphi(b)}\equiv1\pmod{\operatorname{lcm}(a,b)}$ 即 $x^{\varphi(n)}\equiv1\pmod{n}$。

那么至此归纳结束，欧拉定理证明完毕了。

关于最后一个根据中国定理，这个又是另一个内容了，可以去看我的博文：

友情链接：

【算法介绍】中国剩余定理及其拓展 | 祝馀宫

看完了就知道关于同余方程组的解只有下面一种可能性：

而在上面 $\gcd(a,b)=1$，所以他们的最大公约数自然就是 $n$。

这些定理的证明全都是基于代数方法的，事实上还有更加简便的方式，就是从剩余系考虑。简单介绍一下剩余系这个概念：我们把在模 $m$ 意义下所有的可能的余数的集合，称为模数 $m$ 的完全剩余系，即 $\{0,1,\dots,m-1\}$ 这个集合。如果把这个集合内不与 $m$ 互质的数去掉，只剩下与 $m$ 互素的，那么被称为简化剩余系。

关于刚刚两个定理，我们可以用剩余系的角度来证明一波：

证明：费马小定理

构造一个序列：$A=\{1,2,3\dots,p-1\}$，这个序列有着这样一个性质：

序列性质证明：

$\because (A_i,p)=1,(a,p)=1\quad\therefore(A_i\times a,p)=1$

又因为每一个 $A_i\times a \pmod p$ 都是独一无二的，且 $A_i\times a \pmod p < p$

得证（每一个 $A_i\times a$ 都对应了一个 $A_i$）

设 $f=(p-1)!$，则 $f\equiv a\times A_1\times a\times A_2\times a \times A_3 \dots \times A_{p-1} \pmod p$

证毕。

因为剩余系内的这些元素独一无二，总量不变，从而得到一个特殊的性质来证明费马小，这是一个不错的想法，非常显然的，这个证明方式在欧拉定理中也生效，我们构造出关于模数 $m$ 的简化剩余系，使用和刚刚费马小一样的证明方式即可得证，不再赘述。

定理拓展：劫余重生的希望

  • 拓展欧拉定理推导

拓展欧拉定理就是关于欧拉定理的一个拓展，其内容如下：

拓展欧拉定理的作用也很显然，就是降幂，高幂次的计算可以在拓展欧拉定理的作用下变成 $\varphi(m)$ 级别，当然 $m$ 不能特别大，不然我们也算不了。

关于拓展欧拉定理的证明，这个我们来一个各个击破：

证明：拓展欧拉定理

Case 1. 证明 $a^b\equiv a^{b\bmod\varphi(m)}\pmod m,\gcd(a,m)=1$。

讲模运算替换为 $b=k\cdot\varphi(m)+r$，根据定义 $0\le r<\varphi(m)$，那么式子就可以转化：

其中 $a^{k\varphi(m)}$ 被消掉的原因是欧拉定理 $a^{\varphi(m)}\equiv1\pmod m$。

Case 2. 证明 $a^b\equiv a^b\pmod m,\gcd(a,m)\neq1,b<\varphi(m)$。

就这还要证明？？？？？？？？？

这条定理的作用是使得我们降幂到一定程度后告诉我们可以不用降幂了。

Case 3. 证明 $a^{(b\bmod\varphi(m))+\varphi(m)}\pmod m,\gcd(a,m)\neq1,b\ge\varphi(m)$。

首先显然的，因为乘方的特殊性质，我们会发现证明这样一个 $a$ 和证明他其中一个质因子 $p_i$ 满足该定理是等价的，我们可以给一个简单的证明。

就是一路用乘方的性质推下去即可。

加下来的问题转化为证明 ${p_i}^b\equiv p_i^{(b\bmod\varphi(m))+\varphi(m)}\pmod m$ 为了方便下文用 $p$ 代替 $p_i$ 。

如果 $p,m$ 互质，那么这时候就是上面一开始的 Case 1. 的情况，接下来要考虑的就是不互质。由于 $p$ 是质数，那么 $m$ 就至少得是 $2p$ 以上，如果设 $m=sp^r$ 其中 $\gcd(s,p)=1$，那么由于欧拉函数是积性函数，根据定义就有 $\varphi(m)=\varphi(s)\varphi(p^r)$，接下来又是一路推导：

由于 $b\ge\varphi(m)\ge r$，我们有 $p^b=p^{b-r}\times p^r\equiv p^{b-r}\times p^{r+\varphi(m)}=p^{\varphi(m)+b}\pmod m$ 这时候记录一个额外的函数 $f(x)$ 表示 $p^x\bmod m\ (x\ge\varphi(m))$，那么这个式子就可以表示为 $f(x)=f(x+\varphi(m))$ 那么其实相对应的我们就有 $f(x)=f(x-\varphi(m))$。

而最终的答案就是 $f(b)$ 那么就可以考虑一直减去 $\varphi(m)$ 得到结果，但由于 $f(x)$ 的参数 $x$ 满足 $x\ge\varphi(m)$，所以在减法递推的过程中还要保证 $x\ge2\varphi(m)$，最终的结果就可以是 $b\bmod\varphi(m)+\varphi(m)$ 搞定。

又因为这里一开始的转化，所以可以得到：

至此，拓展欧拉定理，证毕！

关于上面 Case 3. 中提到的 $b\ge\varphi(m)\ge r$，其中 $\varphi(m)\ge r$ 的证明如下：

证明：

首先 $φ(m)=φ(s)×φ(p^r)≥φ(p^r)$（等号在 $s=1,2$ 时取到）

$φ(p^r)=p^r−p^{r−1}=p^{r−1}(p−1)≥p^{r−1}$（ $p≥2$，等号在 $p=2$ 时取到）

数学归纳法证 $p^{r−1}≥r$：

  • $r=1$ 时显然成立；
  • 假设 $r=i$ 时 $p^{i−1}≥i$ 成立 $p^i=p×p^{i−1}≥2p^{i−1}=p^{i−1}+p^{i−1}≥p^{i−1}+1=i+1$ 成立，因此 $p^{r−1}≥r$ 成立。

把上面所有的不等号串起来，就是 $φ(m)≥r$

算法实战：拓宇行天的意志

查看相关算法标签喵！

参考资料（以下排名不分先后）