也许更好的阅读体验

欧拉函数

• 定义
  欧拉函数是 小于等于 x的数中与x 互质 的数的 数目
  符号 $\phi \left(x\right)$φ(x)
  互质 两个互质的数的最大公因数等于1,1与任何数互质

• 通式
  $\phi \left(x\right)=x{\prod }_{i=1}^n(1-\frac{1}{p_i})$φ(x)=x∏i=1n​(1−pi​1​)
  其中 $p_i$pi​为 $x$x的质因子, $n$n为 $x$x的因子个数

欧拉函数常用性质

• 若 $n$n为质数，显然 $\phi \left(n\right)=n-1$φ(n)=n−1
  $\backslash begin\{aligned\}\backslash end\{aligned\}$

• 欧拉函数是积性函数
  积性函数: 对于任意 互质 的整数 $a$a和 $b$b有性质 $f\left(ab\right)=f\left(a\right)\cdot f\left(b\right)$f(ab)=f(a)⋅f(b)的数论函数。
  若 $m,n$m,n互质， $\phi \left(mn\right)=\phi \left(m\right)\cdot \phi \left(n\right)$φ(mn)=φ(m)⋅φ(n)
  $\backslash begin\{aligned\}\backslash end\{aligned\}$

• 如果 $x=2n$x=2n( $n$n为奇数)， $\phi \left(x\right)=\phi \left(n\right)$φ(x)=φ(n) 即 $\phi \left(2n\right)=\phi \left(n\right)$φ(2n)=φ(n)( $n$n为奇数)
  n为奇数时,n与2互质， $\phi \left(2\right)=1$φ(2)=1
  $\backslash begin\{aligned\}\backslash end\{aligned\}$

• 若 $p$p为质数,则 $\phi \left(p^k\right)=p^k-p^{k-1}$φ(pk)=pk−pk−1
  因为与 $p^k$pk不互质的只有 $p$p的倍数，而 $p^k$pk中 $p$p的倍数有 $p^{k-1}$pk−1个
  $\backslash begin\{aligned\}\backslash end\{aligned\}$

• 当 $x\>2$x>2时， $\phi \left(x\right)$φ(x)为偶数
  这一点需要了解更相减损术 即 $gcd(n,x)=gcd(n,n-x)$gcd(n,x)=gcd(n,n−x)
  由该公式我们可以知道，所有与 $n$n互质的数都是成对出现的
  $\backslash begin\{aligned\}\backslash end\{aligned\}$

• 小于n的数中，与n互质的数的总和为 $\phi \left(n\right)\ast n/2(n\>1)$φ(n)∗n/2  (n>1)
  由上面的证明(更相减损术)我们知道，每一对与 $n$n互质的数的和为 $n$n，共有 $\phi \left(n\right)/2$φ(n)/2对
  $\backslash begin\{aligned\}\backslash end\{aligned\}$

• $n={\sum }_{d\mid n}\phi \left(d\right)$n=∑d∣n​φ(d)即 $n$n的因数 $($(包括 $1$1和它自己 $)$)的欧拉函数之和等于 $n$n
  这条性质的运用又叫 欧拉反演
  定义函数
  $\begin{array}{c}{\displaystyle f\left(n\right)=\sum _{d\mid n}\phi \left(d\right)}\end{array}$f(n)=d∣n∑​φ(d)​

  • $f\left(n\right)$f(n)为积性函数
    $\begin{array}{c}{\displaystyle f\left(n\right)\cdot f\left(m\right)=\sum _{i\mid n}\phi \left(i\right)\sum _{j\mid m}\phi \left(j\right)=\sum _{i\mid n}\sum _{j\mid m}\phi \left(i\right)\cdot \phi \left(j\right)=\sum _{i\mid n}\sum _{j\mid m}\phi (i\cdot j)=\sum _{d\mid nm}\phi \left(d\right)=f\left(nm\right)}\end{array}$f(n)⋅f(m)=i∣n∑​φ(i)j∣m∑​φ(j)=i∣n∑​j∣m∑​φ(i)⋅φ(j)=i∣n∑​j∣m∑​φ(i⋅j)=d∣nm∑​φ(d)=f(nm)​

  $f\left(p^k\right)=\phi \left(1\right)+\phi \left(p\right)+\phi \left(p^2\right)+\cdots +\phi \left(p^k\right)=1+(p-1)+(p^2-p)+\cdots +(p^k-p^{k-1})=p^k$f(pk)=φ(1)+φ(p)+φ(p2)+⋯+φ(pk)=1+(p−1)+(p2−p)+⋯+(pk−pk−1)=pk

  $n=p_1^{k_1}\cdot p_2^{k_2}\cdot \cdots \cdot p_m^{k_m}$n=p1k1​​⋅p2k2​​⋅⋯⋅pmkm​​

  $f\left(n\right)=f\left(p_1^{k_1}\right)\cdot f\left(p_2^{k_2}\right)\cdot \cdots \cdot f\left(p_m^{k_m}\right)=p_1^{k_1}\cdot p_2^{k_2}\cdot \cdots \cdot p_m^{k_m}=n$f(n)=f(p1k1​​)⋅f(p2k2​​)⋅⋯⋅f(pmkm​​)=p1k1​​⋅p2k2​​⋅⋯⋅pmkm​​=n
  $\backslash begin\{aligned\}\backslash end\{aligned\}$

欧拉定理

若 $a,m$a,m互质， $a^{\phi \left(m\right)}\equiv 1\left(modm\right)$aφ(m)≡1(mod m)

• 证明

  • 剩余系 指对于某一个特定的正整数 $n$n，一个整数集中的数 $modn$mod n所得的余数域。
    • 完全剩余系 设 $m\in Z+$m∈Z+，若 $r_0,r_1,...r_{m-1}$r0​,r1​,...rm−1​为 $m$m个整数，并且两两模 $m$m不同余，则 $r_0,r_1,...r_{m-1}$r0​,r1​,...rm−1​叫作模 $m$m的一个完全剩余系。
    • 缩系 设 $A$A是 $modn$mod n的剩余系，若任意 $A$A中两个元素相乘 $modn$mod n后仍为 $A$A中的元素,则称 $A$A为 $modn$mod n的缩系
    • 若 $a,m$a,m互质，则 $m$m的一个缩系为
      $\{x_1,x_2,x_3...x_{\phi \left(m\right)}\}${x1​,x2​,x3​...xφ(m)​}
      $\{a{x}_1\%m,a{x}_2\%m,a{x}_3\%m...a{x}_{\phi \left(m\right)}\%m\}${ax1​%m,ax2​%m,ax3​%m...axφ(m)​%m}也是 $modm$mod m的缩系
      于是可以得到
      ${\sum }_{i=1}^{\phi \left(m\right)}a{x}_i\equiv {\sum }_{i=1}^{\phi \left(m\right)}{x}_i\left(modm\right)$∑i=1φ(m)​axi​≡∑i=1φ(m)​xi​ (mod m)
      $a^{\phi \left(m\right)}{\sum }_{i=1}^{\phi \left(m\right)}{x}_i\equiv {\sum }_{i=1}^{\phi \left(m\right)}{x}_i\left(modm\right)$aφ(m)∑i=1φ(m)​xi​≡∑i=1φ(m)​xi​ (mod m)
      $a^{\phi \left(m\right)}\equiv 1\left(modm\right)$aφ(m)≡1 (mod m)
      • 而当 $m$m为质数时， $\phi \left(m\right)=m-1$φ(m)=m−1
        $a^{(m-1)}\equiv 1\left(modm\right)$a(m−1)≡1(mod m)
        这就是我们熟知的 费马小定理

• 变式 $a,m$a,m互质 $a^b\equiv a^{b\%\phi \left(m\right)}\left(modm\right)$ab≡ab%φ(m)(mod m)

扩展欧拉定理

若 $b\>\phi \left(m\right)$b>φ(m) 即使 $a,m$a,m不互质， $a^b\equiv a^{b\%\phi \left(m\right)+\phi \left(m\right)}\left(modm\right)$ab≡ab%φ(m)+φ(m)(mod m)

• 证明
  从 $m$m中提一个质因子 $p$p出来 令 $m=p^k\cdot s$m=pk⋅s
  有 $gcd(p^k,s)=1$gcd(pk,s)=1，即 $p^k,s$pk,s互质
  根据欧拉定理，我们知道 $p^{\phi \left(s\right)}\equiv 1\left(mods\right)$pφ(s)≡1(mod s)
  根据欧拉函数是积性函数，我们知道 $\phi \left(s\right)\mid \phi \left(m\right)$φ(s)∣φ(m)所以有 $p^{\phi \left(m\right)}\equiv p^{\phi \left(s\right)}\left(mods\right)$pφ(m)≡pφ(s)(mod s)
  设 $p^{\phi \left(s\right)}=xs+1$pφ(s)=xs+1
  那么 $p^{\phi \left(s\right)+k}=xm+p^k$pφ(s)+k=xm+pk
  所以 $p^{\phi \left(s\right)+k}\equiv p^k\left(modm\right)$pφ(s)+k≡pk(mod m)，也有 $p^{\phi \left(m\right)+k}\equiv p^k\left(modm\right)$pφ(m)+k≡pk(mod m)
  当 $b\>=k$b>=k时， $p^b\equiv p^{b-k}\cdot p^k\equiv p^{b-k}\cdot p^{\phi \left(s\right)+k}\equiv p^{b+\phi \left(m\right)}\left(modm\right)$pb≡pb−k⋅pk≡pb−k⋅pφ(s)+k≡pb+φ(m)(mod m)
  又因为 $k\&lt;=\phi \left(p^k\right)\&lt;=\phi \left(m\right)$k<=φ(pk)<=φ(m)，所以当 $b\&gt;=2\phi \left(m\right)$b>=2φ(m)时，满足 $p^b\equiv p^{b-\phi \left(m\right)}\left(modm\right)$pb≡pb−φ(m)(mod m)
  注意是 $2\phi \left(m\right)$2φ(m)!
  所以可以得到 $p^b\equiv p^{b\%\phi \left(m\right)+\phi \left(m\right)}\left(modm\right)$pb≡pb%φ(m)+φ(m)(mod m)
  因此我们可以得到对任意质数 $p$p都有 $b\&gt;=2\phi \left(m\right),p^b\equiv p^{b\%\phi \left(m\right)+\phi \left(m\right)}\left(modm\right)$b>=2φ(m),pb≡pb%φ(m)+φ(m)(mod m)
  非 $m$m质因子的 $p$p，有欧拉定理
  将 $a$a因式分解，可以得到
  $a^b\equiv a^{b\%\phi \left(m\right)+\phi \left(m\right)}\left(modm\right)$ab≡ab%φ(m)+φ(m)(mod m)
  • 注意 $b\&lt;\phi \left(m\right)$b<φ(m)时，公式不一定成立

线性筛法

类似与筛素数，我们在这里利用欧拉函数是积性函数这个性质来筛 $\phi$φ
$Code$Code

int cnt;
int prime[maxn],phi[maxn];
bool vis[maxn];
void Euler_sieve (int n)
{
	phi[1]=1;
	for (int i=2;i<=n;++i){
		if (!vis[i])	prime[++cnt]=i,phi[i]=i-1;
		for (int j=1;j<=cnt&&i*prime[j]<=n;++j){
			vis[i*prime[j]]=true;
			if (i%prime[j]==0){	phi[i*prime[j]]=phi[i]*prime[j];break;}
			phi[i*prime[j]]=phi[i]*phi[prime[j]];
		}
	}
} 

欧拉反演

利用欧拉函数的一条性质
$\begin{array}{c}{\displaystyle n=\sum _{d\mid n}\phi \left(d\right)}\end{array}$n=d∣n∑​φ(d)​
(上面有证明)
我们试着把 $n$n换成其他东西试试
$\begin{array}{c}{\displaystyle gcd(i,j)=\sum _{d\mid gcd(i,j)}\phi \left(d\right)=\sum _{d\mid i}\sum _{d\mid j}\phi \left(d\right)}\end{array}$gcd(i,j)=d∣gcd(i,j)∑​φ(d)=d∣i∑​d∣j∑​φ(d)​
让我们求个东西试试
$\begin{array}{c}{\displaystyle \sum _{i=1}^{n}gcd(i,n)=\sum _{i=1}^n\sum _{d\mid i}\sum _{d\mid n}\phi \left(d\right)=\sum _{d\mid n}\sum _{i=1}^n\sum _{d\mid i}\phi \left(d\right)=\sum _{d\mid n}\frac{n}{d}\phi \left(d\right)}\end{array}$i=1∑n​gcd(i,n)=i=1∑n​d∣i∑​d∣n∑​φ(d)=d∣n∑​i=1∑n​d∣i∑​φ(d)=d∣n∑​dn​φ(d)​
把它重写一遍作为结论
$\begin{array}{c}{\displaystyle \sum _{i=1}^{n}gcd(i,n)=\sum _{d\mid n}\frac{n}{d}\phi \left(d\right)}\end{array}$i=1∑n​gcd(i,n)=d∣n∑​dn​φ(d)​

如有哪里讲得不是很明白或是有错误，欢迎指正
如您喜欢的话不妨点个赞收藏一下吧
如能得到推荐博主就更开心了
您的鼓励是博主的动力