Proof of Euler's Totient Function formula
The proof for the formula of Euler’s Totient Function, denoted as \( \phi(n) \), relies on two primary properties: the behavior of the function on prime powers and its multiplicative nature.
The goal is to prove that for a positive integer \( n \) with prime factorization \( n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k} \):
\[
\phi(n) = n \prod_{i=1}^{k} \left( 1 - \frac{1}{p_i} \right)
\]
Step 1: \( \phi(n) \) for Prime Powers
Let \( p \) be a prime number and \( n = p^k \). To find \( \phi(p^k) \), we count how many integers between 1 and \( p^k \) are not coprime to \( p^k \). An integer is not coprime to \( p^k \) if and only if it is a multiple of \( p \). The multiples of \( p \) in the range \( [1, p^k] \) are: \[ p, 2p, 3p, \dots, (p^{k-1})p \] There are exactly \( p^{k-1} \) such multiples. Subtracting these from the total count: \[ \phi(p^k) = p^k - p^{k-1} = p^k \left( 1 - \frac{1}{p} \right) \] Step 2: The Multiplicative Property
A key property of the Totient function is that it is multiplicative. If \( \gcd(a,b) = 1 \), then: \[ \phi(ab) = \phi(a)\phi(b) \] Proof of this multiplicative property is here. Step 3: Final Assembly
Using the fundamental theorem of arithmetic, any integer \( n > 1 \) can be written as \( n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k} \). Since each \( p_i^{a_i} \) term is coprime to the others, we apply the multiplicative property: \[ \phi(n) = \phi(p_1^{a_1}) \cdot \phi(p_2^{a_2}) \cdots \phi(p_k^{a_k}) \] Substitute the result from Step 1 for each term: \[ \phi(n) = \left( p_1^{a_1} - p_1^{a_1 - 1} \right)\left( p_2^{a_2} - p_2^{a_2 - 1} \right) \cdots \left( p_k^{a_k} - p_k^{a_k - 1} \right) \] Factor out \( p_i^{a_i} \) from each term: \[ \phi(n) = p_1^{a_1} \left( 1 - \frac{1}{p_1} \right) \cdot p_2^{a_2} \left( 1 - \frac{1}{p_2} \right) \cdots p_k^{a_k} \left( 1 - \frac{1}{p_k} \right) \] Rearrange the terms: \[ \phi(n) = \left( p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k} \right) \prod_{i=1}^{k} \left( 1 - \frac{1}{p_i} \right) \] Since the term in the parentheses is \( n \), we arrive at the general formula: \[ \phi(n) = n \prod_{p \mid n} \left( 1 - \frac{1}{p} \right) \]
Step 1: \( \phi(n) \) for Prime Powers
Let \( p \) be a prime number and \( n = p^k \). To find \( \phi(p^k) \), we count how many integers between 1 and \( p^k \) are not coprime to \( p^k \). An integer is not coprime to \( p^k \) if and only if it is a multiple of \( p \). The multiples of \( p \) in the range \( [1, p^k] \) are: \[ p, 2p, 3p, \dots, (p^{k-1})p \] There are exactly \( p^{k-1} \) such multiples. Subtracting these from the total count: \[ \phi(p^k) = p^k - p^{k-1} = p^k \left( 1 - \frac{1}{p} \right) \] Step 2: The Multiplicative Property
A key property of the Totient function is that it is multiplicative. If \( \gcd(a,b) = 1 \), then: \[ \phi(ab) = \phi(a)\phi(b) \] Proof of this multiplicative property is here. Step 3: Final Assembly
Using the fundamental theorem of arithmetic, any integer \( n > 1 \) can be written as \( n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k} \). Since each \( p_i^{a_i} \) term is coprime to the others, we apply the multiplicative property: \[ \phi(n) = \phi(p_1^{a_1}) \cdot \phi(p_2^{a_2}) \cdots \phi(p_k^{a_k}) \] Substitute the result from Step 1 for each term: \[ \phi(n) = \left( p_1^{a_1} - p_1^{a_1 - 1} \right)\left( p_2^{a_2} - p_2^{a_2 - 1} \right) \cdots \left( p_k^{a_k} - p_k^{a_k - 1} \right) \] Factor out \( p_i^{a_i} \) from each term: \[ \phi(n) = p_1^{a_1} \left( 1 - \frac{1}{p_1} \right) \cdot p_2^{a_2} \left( 1 - \frac{1}{p_2} \right) \cdots p_k^{a_k} \left( 1 - \frac{1}{p_k} \right) \] Rearrange the terms: \[ \phi(n) = \left( p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k} \right) \prod_{i=1}^{k} \left( 1 - \frac{1}{p_i} \right) \] Since the term in the parentheses is \( n \), we arrive at the general formula: \[ \phi(n) = n \prod_{p \mid n} \left( 1 - \frac{1}{p} \right) \]
Comments
Post a Comment