9
$\begingroup$

Is the set of prime pairs such that $gcd(p−1,q−1)=2$ of positive density? For example, for $p,q≤10^4$ the answer is approximately $1/2$.

I was wondering if it were possible to use sieve methods and results such as the Siegel-Walfisz Theorem to give a good approximation of prime pairs of this form.

The motivation for the question is for understanding the order of elements in the group $(\mathbb{Z}/pq\mathbb{Z})^∗≃(\mathbb{Z}/p\mathbb{Z})^∗×(\mathbb{Z}/q\mathbb{Z})^*$.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Would it be plausible that the density of prime pairs such that $gcd(p-1,q-1)=2^{n}$ equals $2^{-n}$? $\endgroup$
    – Sylvain JULIEN
    Commented Nov 1, 2016 at 11:56
  • 1
    $\begingroup$ @SylvainJULIEN an empirical search suggests that the density of primes such that $gcd(p−1,q−1)=2^n$ is approximately $2^{-(2n-1)}$. $\endgroup$
    – Gal Porat
    Commented Nov 1, 2016 at 12:06
  • $\begingroup$ And what about the density of prime pairs such that $v_{2}(gcd(p-1,q-1))=n$? $\endgroup$
    – Sylvain JULIEN
    Commented Nov 1, 2016 at 12:11
  • $\begingroup$ Looks like $\frac{3}{2^{2n}}$. Interesting. But maybe this is because $\frac{6}{\pi^2}$ is the probability that two random numbers are coprime, and this number is close to $\frac{2}{3}$. $\endgroup$
    – Gal Porat
    Commented Nov 1, 2016 at 12:20
  • $\begingroup$ To me it might mean that the probability that $gcd(p-1,q-1)$ is a power of two equals $2/3$. $\endgroup$
    – Sylvain JULIEN
    Commented Nov 1, 2016 at 12:40

1 Answer 1

Reset to default
22
$\begingroup$

The answer is $$ \frac{3}{4} \prod_{p>2} \Big(1 -\frac{1}{(p-1)^2} \Big) = 0.4951\ldots . $$ The product above is also known as the twin prime constant.

This follows easily from the prime number theorem in arithmetic progressions. Restricting to odd primes $p$ and $q$ below $N$ we want to count $(p-1,q-1)=2$ which by Mobius inversion can be expressed as $$ \sum_{\substack{d| (p-1)/2 \\ d| (q-1)/2 } } \mu(d). $$ Thus we want $$ \sum_{3 \le p, q\le N } \sum_{\substack{d| (p-1)/2 \\ d| (q-1)/2 } } \mu(d) = \sum_{d \le N} \mu(d) \sum_{\substack{p, q\le N \\ p\equiv q\equiv 1 \mod{2d}}} 1 . $$ For $d\le (\log N)^3$, use the prime number theorem in APs (Siegel-Walfisz) to see that these terms are $$ \sim \sum_{d\le (\log N)^3} \frac{\mu(d)}{\phi(2d)^2} \frac{N^2}{(\log N)^2}. $$ For $d> (\log N)^3$ estimate the sums over $p$ and $q$ trivially by $(N/d)^2$. So these terms contribute $$ \ll \sum_{d> (\log N)^3} \frac{N^2}{d^2} \ll \frac{N^2}{(\log N)^3}, $$ which is negligible.

So the required density is $$ \sum_{d\le (\log N)^3} \frac{\mu(d)}{\phi(2d)^2}, $$ which tends to the constant given above as $N\to \infty$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .