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.

  • $\begingroup$ Maybe mathoverflow.net/questions/97041/… is relevant. $\endgroup$ May 18, 2012 at 11:44
  • $\begingroup$ As a rough guide (n!)^(phi(n)/n). One can use an inclusion exclusion type formula to get more exact. Also, for n prime one has the exact formula (n-1)! . Gerhard "Ask Me About System Design" Paseman, 2012.05.18 $\endgroup$ May 18, 2012 at 13:23
  • $\begingroup$ It may be that the rough guide needs to be divvided by e^phi(n) to make it less rough. Gerhard "Maybe Stirling's Approach Would Work" Paseman, 2012.05.18 $\endgroup$ May 18, 2012 at 13:42
  • 2
    $\begingroup$ I'm surprised that no one has thought to look this up at the Online Encyclopedia of Integer Sequences, where it is oeis.org/A001783. There you will find the formula given in the answers here, with a reference to Apostol's textbook on Analytic Number Theory. I don't think anything there deals in asymptotics. $\endgroup$ May 20, 2012 at 23:26
  • $\begingroup$ Many thanks for the formula. I am trying to understand what one can get concerning the asymptotics. Any help is still appreciated. $\endgroup$
    – vlk
    May 21, 2012 at 10:40

3 Answers 3


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

  • $\begingroup$ Your remark regarding primitive roots should be made mod N. Taking N=9 I get 2240 which is not the 21st power of any integer. Also g^phi(N) will be 1, so the result will be a square root of 1 mod N. Gerhard "I Like The Proof Idea" Paseman, 2012.05.20 $\endgroup$ May 20, 2012 at 15:43
  • $\begingroup$ ... which will be -1 mod N, in a manner akin to the proof of Wilson's theorem. Gerhard "Ask Me About System Design" Paseman, 2012.05.20 $\endgroup$ May 20, 2012 at 15:52

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


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

  • 4
    $\begingroup$ The expression is $$n^{\phi(n)}\prod_{d|n}\left(\frac{d!}{d^d}\right)^{\mu(n/d)}$$ $\endgroup$ May 18, 2012 at 19:06
  • $\begingroup$ Nice. If you don't post it as a separate answer, I'll steal it (with attribution). Gerhard "Or Beg Or Borrow Or..." Paseman, 2012.05.18 $\endgroup$ May 18, 2012 at 19:44
  • $\begingroup$ While this is a rather jumpy function, I am guessing there is a nice expression (or at least an asymptotic formula) for the product of all this for $N$ going from $1$ to $M$ (or if you take logs, the sum of logs) $\endgroup$
    – Igor Rivin
    May 20, 2012 at 0:16
  • $\begingroup$ @Gerhard: could you comment my own answer in light of yours. $\endgroup$
    – vlk
    Jul 2, 2012 at 13:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.