Product of Divisor Sum and Euler Phi Functions

From ProofWiki
Jump to navigation Jump to search

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 $\map {\sigma_1} n$ be the divisor sum function of $n$.

Let $\map \phi n$ be the Euler phi function of $n$.


Then:

$\ds \map {\sigma_1} n \map \phi n = n^2 \prod_{1 \mathop \le i \mathop \le r} \paren {1 - \frac 1 {p_i^{k_i + 1} } }$


Proof

From Euler Phi Function of Integer:

$\ds \map \phi n = \prod_{1 \mathop \le i \mathop \le r} p_i^{k_i - 1} \paren {p_i - 1}$

From Divisor Sum of Integer:

$\ds \map {\sigma_1} n = \prod_{1 \mathop \le i \mathop \le r} \frac {p_i^{k_i + 1} - 1} {p_i - 1}$


So:

$\ds \map {\sigma_1} n \map \phi n = \prod_{1 \mathop \le i \mathop \le r} \paren {\frac {p_i^{k_i + 1} - 1} {p_i - 1} } p_i^{k_i - 1} \paren {p_i - 1}$


Taking a general factor of this product:

\(\ds \paren {\frac {p_i^{k_i + 1} - 1} {p_i - 1} } p_i^{k_i - 1} \paren {p_i - 1}\) \(=\) \(\ds \paren {p_i^{k_i + 1} - 1} 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} \paren {1 - \frac 1 {p_i^{k_i + 1} } }\) extracting $p_i^{2 k_i}$ as a factor


So:

$\ds \map {\sigma_1} n \map \phi n = \prod_{1 \mathop \le i \mathop \le r} p_i^{2 k_i} \paren {1 - \frac 1 {p_i^{k_i + 1} } }$

Hence:

$\ds \prod_{1 \mathop \le i \mathop \le r} p_i^{2 k_i} = \paren {\prod_{1 \mathop \le i \mathop \le r} p_i^{k_i} }^2 = n^2$

and the result follows.

$\blacksquare$