4
$\begingroup$

In this section of the Wikipedia article on coprime integers, it is stated that:

More generally, the probability of $k$ randomly chosen integers being coprime is $1/\zeta(k)$.

where $\zeta$ is the Riemann zeta function.

Although there is no proof of this, the statement follows a fleshed out explanation about the probability of two random integers being coprime. Briefly, it proceeds as follows:

  • The probability of any integer being divisible by some other integer $p$ is $1/p$ (because every $p^\mathrm{th}$ integer is).
  • The probability that two random integers (chosen independently) are both divisible by $p$ is $1/p^2$.
  • For a given integer, being divisible by primes $p$ or $q$ are two independent events, and hence the probability of both being true is $1/pq$.
  • Therefore the probability that two random integers are coprimes (i.e. that they are not both divisible by any prime) is:

$$ \prod_{\text{prime } p} 1 - \frac{1}{p^2} = \left( \prod_{\text{prime } p} \frac{1}{1 - p^{-2}} \right)^{-1} = \frac{1}{\zeta(2)} \approx 0.61 $$

And it seems straightforward to apply the same reasoning for $k$ integers:

  • The probability of $k$ random integers chosen independently being divisible by $p$ is $1/p^k$.
  • Hence the probability that they are all coprimes is obtained when they are not all divisible by any prime:

$$ \prod_{\text{prime } p} 1 - \frac{1}{p^k} = \frac{1}{\zeta(k)} $$

My problem with this is one of intuition; intuitively, considering several integers should increase the chances of two of them having a common prime factor, and therefore the probability of $k$ random integers being coprime should asymptotically decrease with $k$. However I think $1/\zeta$ is increasing on $[1, \infty)$, and quickly converges to 1. Where am I going wrong? And what is the right way to think about this?

$\endgroup$
4
$\begingroup$

With $N = 3$, the definition of three integers being coprime is that the highest common factor of the three integers is $1$. In other words, for any prime $p$, at least one of my three integers is not divisible by $p$. Thus, as $N$ increases, it becomes easier for coprimality to be satisfied.

I think you are thinking about the integers being pairwise coprime (i.e. each pair of integers is a coprime pair). This is a different notion from the one discussed in the article, and, as you point out, pairwise coprimality becomes harder to satisfy as $N$ increases.

$\endgroup$
  • 1
    $\begingroup$ That was exactly my mistake, thanks for pointing it out. $\endgroup$ – Sheljohn May 29 '18 at 22:59
  • $\begingroup$ Out of curiosity, could you please refer to something / briefly explain the case of pariwise coprimality? $\endgroup$ – Sheljohn May 29 '18 at 22:59
  • $\begingroup$ @Sheljohn "Coprime" means "for each $p$, at most $N-1$ of my integers are divisible by $p$". "Pairwise coprime" means "for each $p$, at most one of my integers are divisible by $p$. $\endgroup$ – Kenny Wong May 29 '18 at 23:02
  • 1
    $\begingroup$ @Sheljohn The probability of none of the integers being divisible by $p$ is $\left(1 - \frac 1 {p}\right)^N$. The probability of precisely one of the integers being divisible by $p$ is $N \frac 1 p \left( 1 - \frac 1 p\right)^{N-1}$ (the factor of $N$ appears because there are $N$ integers to choose from). So the probability that at most one of my integers is divisible by $p$ is $\left( 1 + \frac{N-1}{p}\right)\left( 1 - \frac{1}{p}\right)^{N-1}$. And the probability that my $N$ integers are pairwise coprime is $\prod_p \left( 1 + \frac{N-1}{p}\right)\left( 1 - \frac{1}{p}\right)^{N-1}$. $\endgroup$ – Kenny Wong May 29 '18 at 23:06
  • 1
    $\begingroup$ Strictly speaking there is no uniform probability distribution on $\mathbb{N}$ hence the argument above should be applied to $[1,N] \cap \mathbb{Z}$, and then $N$ alowed to tend to infinity. So the argument is talking about the limiting case, informally. $\endgroup$ – kodlu May 30 '18 at 0:16

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.