Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
Maybe mathoverflow.net/questions/97041/… is relevant. –  Martin Brandenburg May 18 '12 at 11:44
    
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 –  Gerhard Paseman May 18 '12 at 13:23
    
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 –  Gerhard Paseman May 18 '12 at 13:42
2  
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. –  Gerry Myerson May 20 '12 at 23:26
    
Many thanks for the formula. I am trying to understand what one can get concerning the asymptotics. Any help is still appreciated. –  vlk May 21 '12 at 10:40

3 Answers 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

share|improve this answer
4  
The expression is $$n^{\phi(n)}\prod_{d|n}\left(\frac{d!}{d^d}\right)^{\mu(n/d)}$$ –  Gjergji Zaimi May 18 '12 at 19:06
    
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 –  Gerhard Paseman May 18 '12 at 19:44
    
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) –  Igor Rivin May 20 '12 at 0:16
    
@Gerhard: could you comment my own answer in light of yours. –  vlk Jul 2 '12 at 13:28

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

share|improve this answer
    
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 –  Gerhard Paseman May 20 '12 at 15:43
    
... 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 –  Gerhard Paseman May 20 '12 at 15:52
    
Yes, mod N indeed, thank you. –  Daniel m3 May 20 '12 at 16: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)}. $$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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