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

$\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$ 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
    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$ 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
    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$ Nov 1, 2016 at 12:40

1 Answer 1

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

$\endgroup$

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.