# Proving $P(n) =n^{\phi(n)} \prod\limits_{d \mid n} \left(\frac{d!}{d^d} \right)^{\mu(n/d)}$

Actually, I posted this long ago in MO but did not get a reply as it was unfit.

Now this is an exercise in some textbook (I think Apostol), and I would be happy to receive some answers.

Let $P(n)$ be the product of positive integers which are $\leq n$ and relatively prime to $n$. Prove that $$\displaystyle P(n) = n^{\phi(n)} \prod\limits_{d \mid n} \left(\frac{d!}{d^d} \right)^{\mu(n/d)}.$$

• This is screaming for you to use the Moebius inversion formula. – Mariano Suárez-Álvarez Oct 22 '10 at 18:52
• @Mariano: Thanks! But i actually couldn't figure out as to what my $f(n)$ and $g(n)$ should be! – anonymous Oct 22 '10 at 18:54
• Looking at the equation you want to prove, it is clear that there is exactly one choice. Maybe if you wrote what you tried, we could help you. Otherwise, I'd be just ruining your problem for you. – Mariano Suárez-Álvarez Oct 22 '10 at 18:57
• @Mariano: I think i have got it now.! – anonymous Oct 30 '10 at 20:34

## 2 Answers

Success finally!

Let,

$$f( n) = \sum_{(k,n)=1;1\leq k\leq n} \log\Bigl(\frac{k}{n}\Bigr)$$ therefore we have

$$\sum_{d|n}f(d) =\log\Bigl(\frac{1}{n}\Bigr)+...+\log\Bigl(\frac{n}{n}\Bigr)=\log\left(\frac{n!}{n^n}\right)$$

Thus by Moebius Inversion Formula:

$$f(n) = \sum_{d|n}\log\left(\frac{d!}{d^d}\right)\cdot \mu\left(\frac{n}{d}\right) = \log\left(\prod_{d|n}\left(\frac{d!}{d^d}\right)^{\mu\left(\frac{n}{d}\right) }\right)$$

$$f(n) = \sum_{(k,n)=1;1\leq k\leq n} {\log(k)} -\phi(n)\cdot \log( n) = \log(P(n))-\log(n^{\phi(n)})$$

Start by classifying $[n]$ according to GCD:

$$n! = \prod_{d|n} \prod_{(q,n)=d} q$$

where $q$ ranges from $1$ to $n.$ This is

$$n! = \prod_{d|n} \prod_{(r,n/d)=1} (dr) = \prod_{d|n} d^{\varphi(n/d)} \prod_{(r,n/d)=1} r \\ = \prod_{d|n} d^{\varphi(n/d)} P(n/d).$$

This becomes

$$n! = \prod_{d|n} (n/d)^{\varphi(d)} P(d) = \prod_{d|n} n^{\varphi(d)} \prod_{d|n} d^{-\varphi(d)} P(d) \\ = n^n \prod_{d|n} d^{-\varphi(d)} P(d).$$

so that we find

$$\prod_{d|n} d^{-\varphi(d)} P(d) = \frac{n!}{n^n}.$$

By Mobius inversion we thus have

$$n^{\Large -\varphi(n)} P(n) = \prod_{d|n} \left(\frac{d!}{d^d}\right)^{\Large \mu(n/d)}.$$

This finally yields

$$\bbox[5px,border:2px solid #00A000]{ P(n) = n^{\Large \varphi(n)} \prod_{d|n} \left(\frac{d!}{d^d}\right)^{\Large \mu(n/d)}.}$$

as claimed.