欧拉函数性质
前言：欧拉函数的定义 $\varphi(n)$ 为 $1-n$ 中与 $n$ 互质的数。
1证明： $\varphi(1)=1$
$$
\because 只有1与1本身互质\\
\therefore \varphi(1)=1
$$
2证明：$当p是质数时，\varphi(p)=p-1$
$$
\because p是质数\\
\therefore \forall x(1<x<p) gcd(x,p)=1\\
\therefore \varphi(p)=p-1
$$
3证明：$当p是质数时，对于n=p^k,\varphi(n)=p^k-p^{k-1}=(p-1)\times p^{k-1}$
$$
\because n=p^k\\
\therefore \varphi(n)=n-\frac n p\\
=n(1-\frac 1 p)\\
=p^k\times1-p^k\times \frac 1 p\\
=p^k-p^{k-1}\\
=p^{k-1}\times \frac {p^k-p^{k-1}} {p^{k-1}}\\
=p^{k-1}\times (\frac {p^k} {p^{k-1}}-\frac {p^k} {p^k})\\
=p^{k-1}\times (p-1)\\
=p^k-p^{k-1}
$$
4证明：$对于gcd(a,b)=1,\varphi(a\times b)=\varphi(a)\times \varphi(b)$
$$
设a=p_1^{c_1}p_2^{c_2}\cdots p_n^{c_n},b=q_1^{d_1}q_2^{d_2}\cdots q_m^{d_m}\\
\therefore \varphi(a\times b)=a\times b(1-\frac 1 {p_1})(1-\frac 1 {p_2})\cdots (1-\frac 1 {p_n})(1-\frac 1 {q_1})(1-\frac 1 {q_2})\cdots (1-\frac 1 {q_m})\\
=(a\times (1-\frac 1 {p_1})(1-\frac 1 {p_2})\cdots (1-\frac 1 {p_n}))(b\times (1-\frac 1 {q_1})(1-\frac 1 {q_2})\cdots (1-\frac 1 {q_m}))\\
=\varphi(a) \times \varphi(b)
$$
5证明1：$对于质数p，若n\%p=0,则\varphi(n\times p)=\varphi(n)\times p$
$$
设n=p_1^{c_1}p_2^{c_2}\cdots p_n^{c_n}\\
\because n\%p=0\\
\therefore lcm(n,p)=n\\
\therefore \varphi(n\times p)=p\times n(1-\frac 1 {p_1})(1-\frac 1 {p_2})\cdots (1-\frac 1 {p_n})=\varphi(n)\times p
$$
证明2：$对于质数p，若n\%p!=0,则\varphi(n\times p)=\varphi(n)\times (p-1)$
$$
\because p是质数\\
\therefore \varphi(p)=p-1,p与n互质\\
\therefore \varphi(n\times p)=\varphi(n)\times \varphi(p)=\varphi(n)\times (p-1)
$$
7证明： $\sum_{d\vert n} \varphi(d)=n$
$$
设 f(n)=\sum_{d\vert n} \varphi(d)\\
\because f(n\times m)=\sum_{d\vert nm} \varphi(d)=\sum_{d\vert n} \varphi(d)\cdot\sum_{d\vert m} \varphi(d)=f(n) \times f(m)\\
\therefore f(x)是积性函数\\
f(p^m)=\sum_{d|p^m} \varphi(d)=\varphi(p^0) + \varphi(p^1) + \cdots + \varphi(p^m)=1+(p^1-1)+(p^2-p^1)+\cdots +(p^m-p^{m-1})=p^m\\
设n=p_1^{c_1}p_2^{c_2}\cdots p_n^{c_n}\\
\therefore f(n)=f(p_1^{c_1}p_2^{c_2}\cdots p_n^{c_n})=f(p_1^{c_1})f(p_2^{c_2})\cdots f(p_n^{c_n})=p_1^{c_1}p_2^{c_2}\cdots p_n^{c_n}=n\\
\therefore \sum_{d\vert n} \varphi(d)=f(n)=n
$$