11
$\begingroup$

The probability that two integers picked at random are relatively prime is known to be $1/\zeta{(2)}=6/\pi^2\approx0.607927...$. Generalizing, the probability that $n$ random integers have $\gcd=1$ is $1/\zeta{(n)}$.

What is the probability that two random integers have one (and only one) prime factor in common? I did some calculations and obtained the formula $\displaystyle\frac{P(2)}{\zeta(2)}=0.274933...$, where $P(n)$ is the prime zeta function. In general, I suppose that the probability that $n$ random integers have only one prime factor in common is $\displaystyle\frac{P(n)}{\zeta(n)}$.

I would be interested in having confirmation of these results, and in getting a formal proof. I would also like to obtain a generalization expressing the probability that $n$ integers picked at random have exactly $k$ prime numbers in common.

$\endgroup$

1 Answer 1

12
$\begingroup$

Fix $n\ge2$ and fix a finite set of primes $p_1,\dots,p_k$. The probability that $n$ integers "picked at random" have the prime factors $p_1,\dots,p_k$ in common and no other primes is $$ \frac1{(p_1\cdots p_k)^n} \prod_{p\notin\{p_1,\dots,p_k\}} \bigg( 1-\frac1{p^n} \bigg) = \frac1{(p_1^n-1)\cdots(p_k^n-1)\zeta(n)}. $$ This can be proved in the usual way: count the proportion of $n$-tuples $(m_1,\dots,m_n)$ with this property where each $1\le m_j\le M$, and let $M$ go to infinity.

It follows that the probability that $n$ integers "picked at random" have exactly $k$ prime factors in common is $$ \frac1{\zeta(n)} \sum_{p_1<\cdots<p_k} \frac1{(p_1^n-1)\cdots(p_k^n-1)}. $$ For example, when $k=1$, we get $$ \frac1{\zeta(n)} \sum_p \frac1{p^n-1} = \frac1{\zeta(n)} \big( P(n) + P(2n) + P(3n) + \cdots \big). $$ When $k=2$, we get $$ \frac1{\zeta(n)} \frac12 \bigg( \bigg( \sum_p \frac1{p^n-1} \bigg)^2 - \sum_p \frac1{(p^n-1)^2} \bigg). $$

$\endgroup$
2
  • 1
    $\begingroup$ Thank you to Greg for his proof. For $k=1$, your answer provides the probability that $n$ integers have one prime factor $p$ in common, including the possibility that they contain this factor multiple times (i.e. that their $\gcd$ is a power of $p$). Actually, in writing my question, I was thinking to the probability that $n$ integers have only and only one prime factor in common (i.e. their $\gcd$ is exactly a single prime factor, and not a power of a prime number. Under this condition, your solution for $k=1$ reduces to $P(n)/\zeta(n)$, as I have previously found. Thank you again. $\endgroup$
    – Anatoly
    Jul 9, 2014 at 19:50
  • 2
    $\begingroup$ You're right: for general $k$, if one wants to restrict to the $n$-tuples that have $k$ distinct primes in common but none to higher multiplicity, then all of the $(p^n-1)$s become $(p^n)$s. $\endgroup$ Jul 9, 2014 at 19:59

You must log in to answer this question.

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