欧拉函数与欧拉定理

积性函数

定义：若 $a,b$ 互质时，有 $f(ab)=f(a)*f(b)$ ,那么称函数 $f$ 为积性函数。

$ps$：$cbj$大佬说所有积性函数都可以用线性筛求值 $qwq$

欧拉函数

$\varphi(n)$ 表示比 $n$ 小的与 $n$ 互质的正整数的个数

对 $n$ 做质因数分解,得到 $n=p_1^{c_1}p_2^{c_2}\cdots p_m^{c_m}$ 则：

$\varphi(n)=n*(1-{1\over p_1})*(1-{1\over p_2})*\cdots *(1-{1\over p_m})$

证明：

若 $n$ 含有两个不同的质因子 $p,q$ ,

那么在 $1$ ~ $n$ 中 $p$ 的倍数有 $\cfrac {n}{p}$ 个，$q$ 的倍数有 $\cfrac {n}{q}$ 个，

如果我们把这 $\cfrac {n}{p}+\cfrac {n}{q}$ 个数减掉，

那么 $p,q$ 的共同因子就会被排除两遍，需要加回来一次。

因此 $1$ ~ $n$ 中不与 $n$ 含有共同因子 $p,q$ 的数的个数为：

$n-\cfrac {n}{p}-\cfrac {n}{q}+\cfrac {n}{pq}=n(1-{1\over p})(1-{1\over q})$

欧拉函数是积性函数

证明：根据我们得到的式子可得对于两个互质的数 $a,b$ 有

$\varphi(a)\varphi(b)=a*\prod_{质数p\mid a}(1-p)*b*\prod_{质数p\mid b}(1-p)=(a*b)*\prod_{质数p\mid (a*b)}(1-p)=\varphi(a*b)$

线性筛求欧拉函数的值 ：

需要利用的三条性质：

• 1 若 $x$ 为质数，那么 $\varphi(x)=x-1$
• 2 设 $p$ 为质数，若对于一个数 $x$ 有 $p\mid x$ 且 $p^2\mid x$ ,则 $\varphi(x)=\varphi(x/p)*p$
• 3 设 $p$ 为质数，若对于一个数 $x$ 有 $p\mid x$ 但 $p^2\not\mid x$ ,则 $\varphi(x)=\varphi(x/p)*\varphi(p)$

证明：

第一条性质是显然的

第二条性质可以从公式中得到，因为 $x$ 和 $x/p$ 含有的质因子种类完全一样，所以 $\varphi(x)$ 和 $\varphi(x/p)$ 的商由公式可得是 $p$ ，所以 $\varphi(x)=\varphi(x/p)*p$

第三条性质可以直接由 $\varphi(n)$ 为积性函数得到

那么我们就可以利用这三条性质，在线性筛的基础上在 $\Theta(n)$ 的时间复杂度里求出 $1$~$n$ 的欧拉函数

#define ll long long

ll n,phi[N],prime[N],tot,v[N];

for(int i=2;i<=n;i++){

    if(v[i]==0){

        prime[tot++]=i;

        phi[i]=i-1;

        v[i]=i;

    }

    for(int j=0;j<tot;j++){

        if(v[i]<prime[j]||prime[j]*i>n)break;

        v[i*prime[j]]=prime[j];

        if(i%prime[j])phi[i*prime[j]]=phi[i]*phi[prime[j]];

        else phi[i*prime[j]]=phi[i]*prime[j];

    }

}

欧拉定理

$a^{\varphi(n)}\equiv1\pmod n\quad\quad (a\bot n)$

证明：

$a^{\varphi(n)}x_1x_2x_3\cdots x_{\varphi(n)}\pmod n \tag{1}$

$\equiv (ax_1)(ax_2)\cdots(ax_{\varphi(n)})\pmod n \tag{2}$

因为 $a\bot n$ , 所以 $x_i\bot n$ ,所以 $ax_i\bot n$ ，所以 $ax_i \mod m$ 属于 $n$ 的简化剩余系，

因为 {$x_1,x_2,x_3\cdots x_{\varphi(n)}$} 正好构成了 $n$ 的简化剩余系，又有对于任意不相等的 $x_i,x_j$ 存在若 $a\bot n$ 那么 $ax_i\not\equiv ax_j\pmod n$

所以,对构成 $n$ 的简化剩余系的元素分别乘上 $a$ ,得到的数恰好又构成 $n$ 的简化剩余系,

即上面的式子等价于：

$x_1x_2x_3\cdots x_{\varphi(n)}\pmod n \tag{3}$

对(1)、(3)式两边同除 $x_1x_2x_3\cdots x_{\varphi(n)}$ 可得：

$a^{\varphi(n)}\equiv1\pmod n$

证毕。

可以发现其实费马小定理就是欧拉定理的特例，因为当p为质数时，$\varphi(p)=p-1$

扩展：

$a^{b}\equiv a^{b\mod\varphi(n)}\pmod n\quad\quad (a\bot n)$

证明：设 $b=q*\varphi(n)+r$ ,其中 $0\leq r<\varphi(n)$ ,即 $r=b \mod\varphi(n)$ ,于是：

$a^b\equiv a^{q*\varphi(n)+r}\equiv1^q*a^r\equiv a^r\equiv a^{b \mod\varphi(n)}\pmod n$

证毕

这个欧拉定理的小扩展可以帮我们有效降幂，但是他显然还不够一般，为了可以更方便的降幂，我们有：

扩展欧拉定理

$a^b \equiv a^{(b\mod\varphi(c))+\varphi(c)}\pmod c$

证明：

我们可以考虑对 $a$ 做质因数分解，

对于 $a$ 的质因数中与 $c$ 互质的 $p$ 因为欧拉定理显然符合上式，

对于 $p\mid c$ ，我们可以先把 $c$ 拆成 $s*p^r$ ，其中 $s$ 与 $p$ 互质，因为$p^{\varphi(s)}\equiv 1\pmod s$，因为欧拉函数为积性函数，所以 $\varphi(s)*\varphi(p^r)=\varphi(c)$ ，那么显然有

$p^{\varphi(c)}\equiv1\pmod s$

从而

$p^{b}\equiv p^{b\mod\varphi(c)}\pmod s$

两边同乘 $p^r$，因为 $c=s*p^r$，所以

$p^{b+r}\equiv p^{(b\mod\varphi(c))+r}\pmod c$

因为 $c=s*p^r$，所以 $\varphi(c)\ge r$，所以可以对两边同乘 $p^{\varphi(c)-r}$

$p^{b}\equiv p^{(b\mod\varphi(c))+\varphi(c)}\pmod c$

证毕