最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

欧拉函数

来源：博客园

挺多，定理挺简单，证明复杂。


(资料图)

欧拉函数（ \(\phi\) ）

定义：

\(\phi(x)\) 表示所有 \(\le x\) 的数中，与 \(x\) 互质的数的个数。

通式：

设 \(p_1,p_2,...,p_n\) 表示 \(x\) 的质因数。则：

\[\phi(x)=x\times \prod\limits_{i=1}^n \frac{p_i-1}{p_i}\]

证明：首先，显然，一个数和 \(x\) 互质的充要条件是其不是 \(x\) 质因数的倍数。所以我们考虑筛掉所有 \(x\) 的质因数的倍数。随便找两个 \(x\) 的质因数 \(p_i,p_j\) ，考虑容斥，他们的倍数个数为：

\[\frac{x}{p_i} + \frac{x}{p_j} - \frac{x}{p_ip_j}\]

所以剩下的个数为：

\[x-\frac{x}{p_i}-\frac{x}{p_j}+\frac{x}{p_ip_j}\]\[x\times(1-\frac{1}{p_i}-\frac{1}{p_j}+\frac{1}{p_ip_j})\]\[x\times(1-\frac{1}{p_i})(1-\frac{1}{p_j})\]

同理筛去所有的即可得到通式。

附：求 \(x\) 内与 \(y\) 互质的数：

\[x\times \prod\limits_{i=1}^n \frac{p_i-1}{p_i}\]

其中 \(p\) 是 \(y\) 的质因数集（推导类似欧拉定理通式推导）。也可以写作：

\[\frac{x}{y}\times \phi(y)\]

————做题时得到的类似通式扩展。

性质：

  1. 若 \(x\) 为质数，则 \(\phi(x)=x-1\)
  2. 若 \(x\) 为质数，则 \(\phi(x^k)=x^k-x^{k-1}\)1,2 结合定义显然
  3. \(\phi\) 是积性函数对于任意互质的 \(x,y\) ， \(\phi(xy)=\phi(x)\times\phi(y)\)
  4. 当 \(x\) 是奇数时 \(\phi(2x)=\phi(2)\times\phi(x)=\phi(x)\)
  5. \(x (x>1)\) 以内所有与其互质的数的和 \(=\phi(x)\times x \div 2\)证明：前置定理更相减损术，简单来说，就是 \(\gcd(x,y)=\gcd(x,x-y)=\gcd(x-y,y)\)由这个公式可以知道，所有与 \(x\) 互质的数都是成对出现的，并且他们的和为 \(x\)（ \(y,x-y\) ）。因为共有 \(\phi(x) \div 2\) 组，所以他们的和为 \(\phi(x)\times x \div 2\)同时由这个证明可得， \(\phi(x)(x>2)\) 是偶数。
  6. \(x=\sum\limits_{a\mid x}\phi(a)\)证明，设 \(f(a)=\sum\limits_{i\mid a}\phi(i)\)\[\because f(n)\times f(m)=\sum\limits_{i\mid n}\phi(i) \sum\limits_{j\mid m}\phi(j)=\sum\limits_{i\mid n}\sum\limits_{j\mid m}\phi(ij)=\sum\limits_{k\mid nm}\phi(k)=f(nm)\text{ }(\gcd(n,m)=1)\]\[\therefore f \text{ 是积性函数}\]\[\therefore f(p^k)=\phi(1)+\phi(p)+\phi(p^2)+...+\phi(p^k)=p^k\text{ (p 为质数)}\]\[\because x=p_1^{k_1}p_2^{k_2}...p_n^{k_n}\]\[\therefore f(x)=f(p_1^{k_1})f(p_2^{k_2})...f(p_n^{k_n})=p_1^{k_1}p_2^{k_2}...p_n^{k_n}=x\]

线性筛求欧拉函数：

因为欧拉函数是积性函数，所以可以线性筛。

// npri 表示是否是质数（为1不是），pri存储质数，phi存储欧拉函数，x指通式中的xinline void phi_sieve(int n){npri[1]=1;phi[1]=1;for(int i=2;i<=n;i++){if(!npri[i]) phi[i]=i-1,pri[++ppri]=i;for(int j=1;j<=ppri&&i*pri[j]<=n;j++){npri[i*pri[j]]=1;if(i%pri[j]==0){phi[i*pri[j]]=phi[i]*pri[j];break;}//phi[i]已经有质因数pri[j]，只需要x扩大pri[j]即可。phi[i*pri[j]]=phi[i]*phi[pri[j]];//phi 为积性函数，phi[i*pri[j]] = phi[i] * phi[pri[j]]}}}

欧拉反演：

其实就是应用欧拉函数的性质 \(6\)\(gcd\) 公式（好像是主要用途）：

\[\sum\limits_{i=1}^n\gcd(i,n)=\sum\limits_{d\mid n}\frac{n}{d}\phi(d)\]

证明（借鉴博客：https://www.cnblogs.com/Morning-Glory/p/11106828.html ）：将 \(gcd(i,j)\) 带入性质 \(6\) 得：

\[gcd(i,j)=\sum\limits_{d\mid\gcd(i,j)}\phi(d)=\sum\limits_{d\mid i}\sum\limits_{d\mid j}\phi(d)\tag1\]

将 \(\sum\limits_{i=1}^n\gcd(i,n)\) 带入 \((1)\) 得

\[\sum\limits_{i=1}^n\gcd(i,n)=\sum\limits_{i=1}^n\sum\limits_{d\mid i}\sum\limits_{d\mid n}\phi(d)=\sum\limits_{d\mid n}\frac{n}{d}\phi(d)\]

证毕。

欧拉定理：

若 \(a,m\) 互质，则满足：

\[a^{\phi(m)}\equiv 1 \pmod{m}\]

证明这篇博客讲的极其详细，不赘述。

扩展欧拉定理：

对于任意 \(a,m\)

\[a^c \equiv\begin{cases} a^{c \bmod \varphi(m)} &\gcd(a,m)=1 \\ a^c &\gcd(a,m) \neq 1,c<\varphi(m) \\ a^{\left(c \bmod \varphi(m)\right)+\varphi(m)} &\gcd(a,m) \neq 1,c \geq \varphi(m)\end{cases}\pmod m\]

证明极其复杂，这里不给出了，可以参考这篇博客

参考博客：https://www.cnblogs.com/Morning-Glory/p/11106828.htmlhttps://www.cnblogs.com/wangxiaodai/p/9758242.html （欧拉定理证明）https://www.cnblogs.com/1024th/p/11349355.html （扩展欧拉定理证明）

关键词： 欧拉定理 主要用途 充要条件