Euler Totient

**streethot** · October 11th 2009, 11:34 AM

Prove that

$\frac{n}{\phi(n)}=\sum_{d|n}\frac{\mu^2(d)}{\phi(d )}$

**Bruno J.** · October 11th 2009, 02:49 PM

Let $n=p_1^{\alpha_1}\hdots p_k^{\alpha_k}$

Then $\frac{n}{\phi(n)} = \left(\frac{p_1}{p_1-1}\right)\hdots \left(\frac{p_k}{p_k-1}\right) = \left(1+\frac{1}{p_1-1}\right)\hdots \left(1+\frac{1}{p_k-1}\right) = \sum_{d|n} \frac{\mu^2(d)}{\phi(d)}$

as you can see by expanding the product into a sum of $2^k$ terms.

**streethot** · October 11th 2009, 03:35 PM

i don't understand why $\left(1+\frac{1}{p_1-1}\right)\hdots \left(1+\frac{1}{p_k-1}\right) = \sum_{d|n} \frac{\mu^2(d)}{\phi(d)}$

**Bruno J.** · October 11th 2009, 04:38 PM

For every subset $S$ of $\{p_1, \hdots, p_k\}$ , the sum will contain a term of the form $\prod_{p \in S}\frac{1}{p-1} = \frac{1}{\phi\left(\prod_{p \in S}p\right)}$ .

Moreover $\sum_{d | n}\frac{\mu(d)^2}{\phi(d)} = \sum_{q_1\hdots q_t | n}\frac{1}{\phi(q_1\hdots q_t)}$ , where $q_1,\hdots, q_t$ are distinct primes. Another way of writing this is $\sum_{S \subset \{p_1,\hdots, p_k\}}\frac{1}{\phi\left(\prod_{p \in S}p\right)}$ .

Thread: Euler Totient

LinkBack

Thread Tools

Display

Euler Totient

Similar Math Help Forum Discussions

Euler's Totient Function

Euler's totient

Euler totient function

Euler's totient function

Euler Totient

Search Tags