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

Let $m$ be a fixed integer. I want to count number of prime triplet $(p,q,r)$ such that $p < q < r < 2p$ with $m$ divides $p-1, q-1$ but not $r-1$ and the product $pqr$ is an $l$ digit integer.

share|improve this question
    
Is $l$ also fixed? –  Qiaochu Yuan Dec 29 '11 at 8:07
    
Yes $l$ is fixed. –  user15864 Dec 29 '11 at 8:09
    
It would be nice to get some motivation for doing this. Also, you are unlikely to get an exact count for l larger than , say, 30. If you want a rough estimate, the count should have close to l - 3n digits, where n is the number of digits of m. Gerhard "Ask Me About System Design" Paseman, 2011.12.29 –  Gerhard Paseman Dec 29 '11 at 8:38
    
These kinds of integers are used many times for multi prime RSA case. –  user15864 Dec 29 '11 at 9:43
add comment

1 Answer

up vote 4 down vote accepted

Under your assumptions $p,q,r$ are all about size $x= 10^{l/3}$. The congruence conditions are basically independent so you'd get about $(x/\log x)^3(\phi(m)-1)/\phi(m)^3$. There may be a constant in front to account for the inequalities among the primes and the fact that you want exactly $l$ digits. This should be OK when $l$ is large compared to $m$. If that's not the case, it might be trickier.

share|improve this answer
    
Thank you for the help. –  user15864 Dec 29 '11 at 14:47
add comment

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.