关于欧拉函数的一些证明

欧拉函数是积性函数，若x,y互质,则满足

$\varphi(x\times y)=\varphi(x)\times \varphi(y)$

证明过程在楼下

$\because x,y$互质

$\therefore x,y$的质约数完全不同

简单来说

$\varphi(x)=x(1-1/p_{1})…(1-1/p_{n})…①$

$\varphi(y)=y(1-1/p'_{1})…(1-1/p'_{m})…②$

$①\times ②$得到

$\varphi(x)\times \varphi(y)$

$=x\times y(1-1/p_{1})…(1-1/p_{n})(1-1/p'_{1})…(1-1/p'_{m})$

$=\varphi(x\times y)$

线性筛欧拉函数

如果 $i \mod p =0$ 而且p为质数

那么 $\varphi(i \times p)=\varphi(i) \times p$…①

否则 $\varphi(i \times p)=\varphi(i) \times (p-1)$…②

①②证明在楼下

①式证明

首先给出证明：若$j$和$i$互质那么$j+i$和$i$互质

假设$j+i$与$i$不互质，设$b=gcd(j+i,i)$

那么$i=k_{1}\times b,j+i=k_{2}\times b$

$\therefore k_{1}\times b+j=k_{2}\times b$

$\therefore j=(k_{2}-k_{1})\times b$

$\because i=k_{1}\times b$

$\therefore i$和$j$不互质，矛盾！

$\therefore$若$j$和$i$互质那么$j+i$和$i$互质

$\because$对于区间[1,$i$]与$i$互质的数的个数为$\varphi(i)$

$\because$由楼上结论得出对于每一个区间[$k\times i+1$,$(k+1)\times i$]与$i$互质的个数都为$\varphi(i)$

$\therefore$对于区间[1,$i\times p$]与$i$互质的数的总个数为$\varphi(i)\times p$

$\because i \mod p=0$

$\therefore i$的质约数中包含了$p$的质约数

$\therefore$与$i$互质也就等于与$p$互质

$\therefore$对于区间[1,$i\times p$]与$i\times p$互质的数的总个数为$\varphi(i)\times p$

整理得到：$\varphi(i \times p)=\varphi(i) \times p$

②式证明

$\because$当$p$为质数且$i \mod p \neq 0$

$\therefore i$和$p$互质

$\therefore$满足积性函数$\varphi(i\times p)=\varphi(i)\times \varphi(p)$，

$\because p$为质数

$\therefore\varphi(p)=p-1$

整理得到:$\varphi(i \times p)=\varphi(i) \times (p-1)$