【学习笔记】浅谈欧拉函数
-
本文是对欧拉函数学习的一个总结，略去了部分证明。所以这真的是“浅谈”。希望可以帮助到不会欧拉函数的人。
-
若无特殊说明，文中涉及的数均为正整数。
基本内容：
在数论中，对于一个正整数
n ，欧拉函数是[1,n] 中与n 互质的数的数目，用\varphi(n) 进行表示。
显然，根据定义我们可以轻松推出：\varphi(n)=\sum_{i=1}^{n}\space [\gcd(i,n)=1] （注：上式中，对于一个命题
P ，[P] 的值在命题为真时为1 ，反之为0 ）
性质：
-
见上文，于是我们有一个算
\varphi(n) 的最朴素方法：int phi(int n) { int res=0; for(int i=1;i<=n;i++) { if(gcd(i,n)==1) ++res; } return res; }若将
\gcd 的时间复杂度近似看作O(\log n) ，则这段代码的时间复杂度为O(n\log n) ，倘若有m 个数的话这段代码的时间复杂度显然很大，所以下文将提到一种更好的方法。 -
若对于一个正整数
n ，有n=p^k ，则：\varphi(n)=p^k-p^{k-1} 证明略。
-
若
\gcd(n,m)=1 ，则：\varphi(nm)=\varphi(n)\times\varphi(m) 证明略。根据这条性质我们亦能知道欧拉函数是个积性函数。
-
设
n=\prod_{i=1}^np_i^{k_i} （p 为质数），则：\varphi(n)=n\times\prod_{i=1}^n(1-\dfrac{1}{p_i}) 证明：
根据性质
2 和性质3 ，有：\varphi(n)=\prod_{i=1}^n\varphi(p_i^{k_i})=\prod_{i=1}^n(p_i^{k_i}(1-\dfrac{1}{p_i}))=n\times\prod_{i=1}^n(1-\dfrac{1}{p_i}) 证毕！
-
若
p 为n 的一个质因数且p\nmid\dfrac{n}{p} ，则：\varphi(n)=\varphi(\dfrac{n}{p})\times(p-1) 证明：
设
证毕！
-
若
p 为n 的一个质因数且p\mid\dfrac{n}{p} ，则：\varphi(n)=\varphi(\dfrac{n}{p})\times p 证明：
设
n=\prod_{i=1}^mp_i^{k_i}\times p^k ，那么\dfrac{n}{p}=\prod_{i=1}^mp_i^{k_i}\times p^{k-1} ，则：\varphi(\dfrac{n}{p})=\dfrac{n}{p}\times\prod_{i=1}^m(1-\dfrac{1}{p_i})\times(1-\dfrac{1}{p}) \varphi(n)=n\times\prod_{i=1}^m(1-\dfrac{1}{p_i})\times(1-\dfrac{1}{p})=\varphi(\dfrac{n}{p})\times p 证毕！
-
根据性质
5 和性质6 ，我们可以考虑在线性筛筛质数的同时计算出每个数的欧拉函数值，具体实现如下：void prephi(int n) { for(int i=2;i<=n;i++) { if(!flag[i]) { pr[++cnt]=i; phi[i]=i-1; } for(int j=1;j<=cnt;j++) { if(i*pr[j]>n)break; flag[i*pr[j]]=1; if(i%pr[j]==0) { phi[i*pr[j]]=phi[i]*pr[j]; break; } phi[i*pr[j]]=phi[i]*(pr[j]-1); } } }时间复杂度
O(n) ，与线性筛的时间复杂度一致。 好了，现在你已经学会了欧拉函数的基本内容，那么它究竟有什么用处呢？接下来，让我们引出：欧拉定理：
欧拉定理指的是，当
\gcd(a,n)=1 时，有：a^{\varphi(n)}\equiv1\pmod n 证明略，可以用反证法进行证明。
欧拉定理还有一个推论：当
请读者自行用欧拉定理尝试证明。
还有一个与它相关的，我们把它称作扩展欧拉定理：
例题：
在这里我为大家挑选了几道欧拉函数的题目，可以用来练练手。本文就不再进行讲解，我相信题解肯定比写的我好qwq