8
$\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$
9
$\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$
  • 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 '14 at 19:50
  • 1
    $\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$ – Greg Martin Jul 9 '14 at 19:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.