6
$\begingroup$

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)}.$$

  • 7
    This is screaming for you to use the Moebius inversion formula.2010-10-22
  • 0
    @Mariano: Thanks! But i actually couldn't figure out as to what my $f(n)$ and $g(n)$ should be!2010-10-22
  • 6
    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.2010-10-22
  • 0
    @Mariano: I think i have got it now.!2010-10-30

2 Answers 2

5

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)})$$

0

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.