Estimate for products of integers that are relatively prime with $N$

Question

Let $N$ be a positive integer. Are there known estimates for the product of all numbers that are smaller than $N$ and relatively prime with $N$? One can assume that $N$ is free of squares, if this helps.

Answer 1

For the sake of completeness, here is a proof of Gjergji's formula, which is a cute exercise in elementary number theory.

The idea is the same as in one of the proofs of the identity $\displaystyle n = \sum_{d | n} \varphi(d),$ only this time we will be multiplying in two ways rather than counting in two ways.

Consider the fractions $\dfrac 1N, \dfrac 2N, \ldots, \dfrac {N-1}N, \dfrac NN.$ Put them in reduced form, that is $\dfrac ad,$ where $d$ must necessarily divide $N$ and $\gcd(a, d) = 1.$ The first multiplication gives $\dfrac {N!}{N^N},$ while the second yields $\displaystyle \prod_{d | N} \prod_{\substack{a \le d-1 \\ \gcd(a, d) = 1}} \frac ad = \prod_{d | N} \frac {\Pi(d)}{d^{\varphi(d)}},$ where $\Pi(N)$ denotes the sought product. The result now follows from the Möbius inversion formula (in multiplicative notation): $\displaystyle \Pi(N) = N^{\varphi(N)} \prod_{d | N} \left( \frac {d!}{d^d} \right)^{\mu(d)}.$

For what it is worth, note that if $N$ is $2, 4,$ a power of an odd prime or twice the power of an odd prime, so that we may find a primitive root modulo $N,$ say $g,$ then the sought product is just $g^{\varphi(N)(\varphi(N)+1)/2}.$

Answer 2

To get the asymptotic, one can replace the factorial in the exact formula by the Stirling formula. Then the desired quantity can be estimated as follows: $$ c\cdot A_N\le (\dots)\le C\cdot A_N $$ with $$ A_N=N^{\phi(N)}\cdot \prod_{d|N}(\sqrt{2\pi d}\cdot e^{-d})^{\mu(N/d)}=(N/e)^{\phi(N)}. $$

Answer 3

I will slightly expand upon my comment. For $N$ a prime, one has the desired product being $(N-1)!$. For $N=pq$, a product of two primes, the desired product is $\frac{N! pq}{p!q^p q!p^q}$ . I have not worked it out, but one should note a similarity between this representation and that of the cyclotomic polynomial $\Phi_pq(x)$. For square free $N=pqr\ldots$ I imagine an analogous relation holds.

EDIT 2012.05.19 Thanks to Gjergji Zaimi, the above idea can be extended and nicely expressed in terms of the Moebius function $\mu()$ and the Euler totient function $\phi()$ as $$N^{\phi(N)}\prod_{d|N}\left(\frac{d!}{d^d}\right)^{\mu(N/d)} .$$ (I have faith enough to post it, but have not fully verified it myself. It looks right to me.) END EDIT 2012.05.19

If you want something rougher but still in the ball park, consider $(N!)^2$ as product of terms of the form $(n+1-i)i$, which for many i look like $o(N^2)$. Then the desired product is something like $\phi(N)/N$ fraction of those terms, perhaps with a power of e to take care of the discrepancy. So I nominate without proof $[(N!)^{1/N}/e]^{\phi(N)}$ as a rough estimate. I imagine provable upper and lower bounds are a mere exponential factor away from this estimate.

Gerhard "Ask Me About Rough Estimates" Paseman, 2012.05.18