MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
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|cite|improve this answer
Thank you for the help. – user15864 Dec 29 '11 at 14:47

Your Answer


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.