# Thread: Number theory Question 1

1. Sorry It should be:

How can i show that

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

here $\displaystyle \mu , \phi$ are mobius function and Euler's phi function.

2. Originally Posted by peteryellow
$\displaystyle \frac{n}{\phi(n)} = \sum_{d|n} \frac{\mu^2(d)}{\phi(d)}$

Remember that both, $\displaystyle \mu$ and $\displaystyle \phi$ are multiplicative, hence $\displaystyle \frac{\mu^2(n)}{\phi(n)}$ is multiplicative.

Now, recall the fact that if $\displaystyle f(n)$ is a multiplicative arithmetic function then so is $\displaystyle \sum_{d|n} f(d)$

From now on I will denote: $\displaystyle F(n)=\sum_{d|n} \frac{\mu^2(d)}{\phi(d)}$

Now let's compute $\displaystyle F(p^s)=\sum_{d|p^s} \frac{\mu^2(d)}{\phi(d)}$ where $\displaystyle p$ is a prime number ( and s is greater than 0): $\displaystyle \sum_{d|p^s} \frac{\mu^2(d)}{\phi(d)}=\frac{\mu^2(1)}{\phi(1)}+ \frac{\mu^2(p)}{\phi(p)}=1+\frac{1}{p-1}$

Now suppose $\displaystyle n=\prod_{p|n}p^s$ is the prime descomposition of n.

Then $\displaystyle F(n)=\prod_{p|n}F(p^s)=\prod_{p|n}\left(1+\frac{1} {p-1}\right)=\prod_{p|n}\left(\frac{1}{1-\tfrac{1}{p}}\right)$

Now recall the fact that: $\displaystyle \frac{\phi(n)}{n}=\prod_{p|n}\left(1-\tfrac{1}{p}\right)$ and we are done

3. Thanks for veryyyyyyyy detalied reply. :-)