Cách tính phi hàm Euler
 

Mọi người cho e hỏi công thức tính phi hàm euler và chứng minh với ạ

Nếu $n$ có phân tích tiêu chuẩn ra thừa số nguyên tố là $n=p_{1}^{i_{1}}p_{2}^{i_{2}}...p_{k}^{i_{k}}$ thì $\varphi(n)=n\left(1-\dfrac{1}{p_{1}}\right)\left(1-\dfrac{1}{p_{2}}\right)...\left(1-\dfrac{1}{p_{k}}\right)$

Dễ thấy rằng với $p$ nguyên tố thì $\varphi(p^k)=p^{k-1}(p-1)$. Chia tập $\left\{1,2,...,p^k\right\}$ thành $p^{k-1}$ tập, mỗi tập chứa $p$ số tự nhiên liên tiếp thì mỗi tập có $p-1$ số nguyên tố cùng nhau với $p$.

Tiếp theo ta chứng minh rằng nếu $(m, n)=1$ thì $\varphi(mn)=\varphi(m)\varphi(n)$. Với mọi $m\in \mathbb{Z}$, xét $U(I_{m})=\left\{[r]\in \mathbb{Z}/{m}|(r,m)=1\right\}$.
Theo định lý phần dư Trung Hoa, với mỗi $a, b$ nguyên, tồn tại số $c$ sao cho $[c]=[a]$ (trong $\mathbb{Z}/m$) và $[c]=[b]$ (trong $\mathbb{Z}/n$).

Xét ánh xạ $f:U(I_{m})\times U(I_{n})\to U(I_{mn})$, $f(([a],[b]))=[c]$ với số $c$ được định nghĩa như trên. Ánh xạ này được định nghĩa tốt, vì theo định lý phần dư Trung Hoa số $c$ là duy nhất theo module $mn$ nên nếu $[d]=[a]$ và $[d]=[b]$ thì $[d]=[c]$. Ánh xạ này là đơn ánh vì nếu tồn tại $([k], [l])$ sao cho $f(([k],[l]))=[c]$ thì $[a]=[c]=[k]$ và $[b]=[c]=[l]$. Ánh xạ này hiển nhiên là toàn ánh, vì nếu $[c]=[a]$ và $[c]=[b]$ thì do $(c, mn)=1$ nên $(a,m)=1$, $(b,n)=1$, tức là $a\in U(I_{m})$, $b\in U(I_{n})$. Vậy $f$ là song ánh, nên số phần tử của 2 tập hợp phải bằng nhau, tức là $\varphi(m)\varphi(n)=\varphi(mn)$. Từ đây kết hợp với $\varphi(p^k)=p^{k-1}(p-1)$ ta có ngay đpcm.