欧拉函数

定义

欧拉函数:是小于x的整数中与x互质的数的个数，一般用$\varphi (x)$表示。特殊的，$\varphi (1) = 1$

通式

$\varphi(x)=x\prod_{i=1}^n(1-\frac{1}{p_i})$ ，其中 $p_i$ 是 $n$ 的质因子， $n$ 为 $x$ 的因子个数。

欧拉函数的性质

1、若 n 为质数，显然 $\varphi(n)=n-1$
2、欧拉函数是积性函数 积性函数: 对于任意互质的整数 $a$和 $b$有性质 $f(ab)=f(a)·f(b)$的数论函数。 若 $m,n$互质， $\varphi(mn)=\varphi(m)·\varphi(n)$
3、如果 $x=2n$( $n$为奇数)， $\varphi(x)=\varphi(n)$ 即 $\varphi(2n)=\varphi(n)$( $n$为奇数)
n为奇数时,n与2互质， $\varphi(2)=1$
4、若 $p$为质数,则 $\varphi(p^k)=p^k-p^{k-1}$
因为与 $p^k$不互质的只有 $p$的倍数，而 $p^k$中 $p$的倍数有 $p^{k-1}$个
5、当 $x>2$时， $\varphi(x)$为偶数
这一点需要了解更相减损术 即 $gcd(n,x)=gcd(n,n-x)$
由该公式我们可以知道，所有与 $n$互质的数都是成对出现的
6、小于n的数中，与n互质的数的总和为 $\varphi(n)*n/2\ \ (n>1)$
由上面的证明(更相减损术)我们知道，每一对与 $n$互质的数的和为 $n$，共有 $\varphi(n)/2$对
7、$n=\sum_{d|n}\varphi(d)$即 $n$的因数 $($包括 $1$和它自己 $)$的欧拉函数之和等于 $n$
这条性质的运用又叫 欧拉反演
定义函数
$\begin{aligned}f(n)=\sum_{d|n}\varphi(d)\end{aligned}$
8、$f(n)$为积性函数 $\begin{aligned}f(n)·f(m)=\sum_{i|n}\varphi(i)\sum_{j|m}\varphi(j)=\sum_{i|n}\sum_{j|m}\varphi(i)·\varphi(j)=\sum_{i|n}\sum_{j|m}\varphi(i·j)=\sum_{d|nm}\varphi(d)=f(nm)\end{aligned}$

$f(p^k)=\varphi(1)+\varphi(p)+\varphi(p^2)+\cdots+\varphi(p^k)=1+(p-1)+(p^2-p)+\cdots+(p^k-p^{k-1})=p^k$

$n=p_1^{k_1} ·p_2^{k_2}· \cdots·p_m^{k_m}$

$f(n)=f(p_1^{k_1})·f(p_2^{k_2})·\cdots·f(p_m^{k_m})=p_1^{k_1} ·p_2^{k_2}· \cdots·p_m^{k_m}=n$ $\begin{aligned}\end{aligned}$

欧拉定理

若 $a,m$互质， $a^{\varphi(m)}≡1(mod\ m)$

证明

剩余系 指对于某一个特定的正整数 $n$，一个整数集中的数 $mod\ n$所得的余数域。
完全剩余系 设 $m\in Z+$，若 $r_0$, $r_1…$ $r_{m-1}$为 $m$个整数，并且两两模 $m$不同余，则 $r_0$, $r_1…$ $r_{m-1}$叫作模 $m$的一个完全剩余系。
缩系 设 $A$是 $mod\ n$的剩余系，若任意 $A$中两个元素相乘 $mod\ n$后仍为 $A$中的元素,则称 $A$为 $mod\ n$的缩系
若 $a,m$互质，则 $m$的一个缩系为
$\{x_1,x_2,x_3…x_{\varphi(m)}\}$
$\{ax_1\%m,ax_2\%m,ax_3\%m…ax_{\varphi(m)}\%m\}$也是 $mod\ m$的缩系
于是可以得到
$\sum_{i=1}^{\varphi(m)}ax_i\equiv \sum_{i=1}^{\varphi(m)}x_i\ (mod\ m)$
$a^{\varphi(m)}\sum_{i=1}^{\varphi(m)}x_i\equiv \sum_{i=1}^{\varphi(m)}x_i\ (mod\ m)$
$a^{\varphi(m)}\equiv 1\ (mod\ m)$
而当 $m$为质数时， $\varphi(m)=m-1$
$a^{(m-1)}≡1(mod\ m)$ 这就是我们熟知的 费马小定理
变式 $a,m$互质 $a^b≡a^{b\%\varphi(m)}(mod\ m)$

扩展欧拉定理

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

证明
从 $m$中提一个质因子 $p$出来 令 $m=p^k·s$
有 $gcd(p^k,s)=1$，即 $p^k,s$互质
根据欧拉定理，我们知道 $p^{\varphi(s)}≡1(mod\ s)$
根据欧拉函数是积性函数，我们知道 $\varphi(s)|\varphi(m)$所以有 $p^{\varphi(m)}≡p^{\varphi(s)}(mod\ s)$ 设 $p^{\varphi(s)}=xs+1$
那么 $p^{\varphi(s)+k}=xm+p^k$
所以 $p^{\varphi(s)+k}≡p^k (mod\ m)$，也有 $p^{\varphi(m)+k}≡p^k (mod\ m)$
当 $b\geq k$时， $p^b≡p^{b-k}·p^k≡p^{b-k}·p^{\varphi(s)+k}≡p^{b+\varphi(m)}(mod\ m)$ 又因为 $k\leq\varphi(p^k)\leq\varphi(m)$，所以当 $b\geq 2\varphi(m)$时，满足 $p^b≡p^{b-\varphi(m)}(mod\ m)$ 注意是 $2\varphi(m)$!
所以可以得到 $p^b≡p^{b\%\varphi(m)+\varphi(m)}(mod\ m)$
因此我们可以得到对任意质数 $p$都有 $b\geq 2\varphi(m),p^b≡p^{b\%\varphi(m)+\varphi(m)}(mod\ m)$ 非 $m$质因子的 $p$，有欧拉定理
将 $a$因式分解，可以得到
$a^b≡a^{b\%\varphi(m)+\varphi(m)}(mod\ m)$
注意 $b<\varphi(m)$时，公式不一定成立

线性筛法

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

typedef long long LL;
const int N = 1000010;
int primes[N], cnt;
int euler[N];
bool st[N];
void get_eulers(int n)
{
    euler[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            primes[cnt ++ ] = i;
            euler[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0)
            {
                euler[t] = euler[i] * primes[j];
                break;
            }
            euler[t] = euler[i] * (primes[j] - 1);
        }
    }
}

欧拉反演

本来没有欧拉反演这个名字的，只不过大家习惯性称之为欧拉反演
所谓欧拉反演其实就是利用欧拉函数的一条性质
$\begin{aligned}n=\sum_{d|n}\varphi(d)\end{aligned}$
(上面有证明) 我们试着把 $n$换成其他东西试试
$\begin{aligned}gcd(i,j)=\sum_{d|gcd(i,j)}\varphi(d)=\sum_{d|i}\sum_{d|j}\varphi(d)\end{aligned}$
让我们求个东西试试
$\begin{aligned}\sum_{i=1}^ngcd(i,n)=\sum_{i=1}^n\sum_{d|i}\sum_{d|n}\varphi(d)=\sum_{d|n}\sum_{i=1}^n\sum_{d|i}\varphi(d)=\sum_{d|n}\frac{n}{d}\varphi(d)\end{aligned}$ 把它重写一遍作为结论
$\begin{aligned}\sum_{i=1}^ngcd(i,n)=\sum_{d|n}\frac{n}{d}\varphi(d)\end{aligned}$

写的太好太全了，转自： Morning_Glory 的博客