Product of Sigma and Euler Phi Functions
Jump to navigation
Jump to search
Although this article appears correct, it's inelegant. There has to be a better way of doing it.
Better to start with $\displaystyle \phi \left({n}\right) = n \prod_{p \mathrel \backslash n} \left({1 - \frac 1 p}\right)$ and then a lot of the gnarliness goes away
You can help Proof Wiki by redesigning it.
Theorem
Let $n$ be an integer such that $n \ge 2$.
Let the prime decomposition of $n$ be:
- $n = p_1^{k_1} p_2^{k_2} \ldots p_r^{k_r}$
Let $\sigma \left({n}\right)$ be the sigma function of $n$.
Let $\phi \left({n}\right)$ be the Euler phi function of $n$.
Then:
- $\displaystyle \sigma \left({n}\right) \phi \left({n}\right) = n^2 \prod_{1 \mathop \le i \mathop \le r} \left({1 - \frac 1 {p_i^{k_i + 1}}}\right)$
Proof
Better to start with $\displaystyle \phi \left({n}\right) = n \prod_{p \mathrel \backslash n} \left({1 - \frac 1 p}\right)$ and then a lot of the gnarliness goes away
You can help Proof Wiki by redesigning it.
To discuss this proof in more detail, feel free to use the talk page.
If you are able to fix this proof, then when you have done so you can remove this instance of {{Improve}} from the code.
If you would welcome a second opinion as to whether your improvement is correct, add an invitation to {{Proofread}} the page (see the proofread template for usage).
From Euler Phi Function of Integer:
- $\displaystyle \phi \left({n}\right) = \prod_{1 \mathop \le i \mathop \le r} p_i^{k_i - 1} \left({p_i - 1}\right)$
From Sigma Function of Integer:
- $\displaystyle \sigma \left({n}\right) = \prod_{1 \mathop \le i \mathop \le r} \frac {p_i^{k_i + 1} - 1} {p_i - 1}$
So:
- $\displaystyle \sigma \left({n}\right) \phi \left({n}\right) = \prod_{1 \mathop \le i \mathop \le r} \left({\frac {p_i^{k_i + 1} - 1} {p_i - 1}}\right) p_i^{k_i - 1} \left({p_i - 1}\right)$
Taking a general factor of this product:
| \(\ds \left({\frac {p_i^{k_i + 1} - 1} {p_i - 1} }\right) p_i^{k_i - 1} \left({p_i - 1}\right)\) | \(=\) | \(\ds \left({p_i^{k_i + 1} - 1}\right) p_i^{k_i - 1}\) | cancelling $p_i - 1$ top and bottom | |||||||||||
| \(\ds \) | \(=\) | \(\ds p_i^{2 k_i} - p_i^{k_i - 1}\) | multiplying out the bracket | |||||||||||
| \(\ds \) | \(=\) | \(\ds p_i^{2 k_i} \left({1 - \frac 1 {p_i^{k_i + 1} } }\right)\) | extracting $p_i^{2 k_i}$ as a factor |
So:
- $\displaystyle \sigma \left({n}\right) \phi \left({n}\right) = \prod_{1 \mathop \le i \mathop \le r} p_i^{2 k_i} \left({1 - \frac 1 {p_i^{k_i + 1} } }\right)$
Hence:
- $\displaystyle \prod_{1 \mathop \le i \mathop \le r} p_i^{2 k_i} = \left({\prod_{1 \mathop \le i \mathop \le r} p_i^{k_i}}\right)^2 = n^2$
and the result follows.
$\blacksquare$