證明 euler phi-function誰可提供代數證法

Definition. Let n be a positive integer. The number of positive integers less than or equal to n which are relatively prime to n will be denoted by f(n). This function is called Euler's phi-function, or the totient function.
\. If the prime factorization of n is n = p1^m1 p2^m2 · · · pn^mn , then
1. 若p為一質數，則 f(p^k)=p^k-p^(k-1)
2. f(n) = n(1-1/p1)(1-1/p2) · · · (1-1/pk). k=4作例證即可