5
$\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$
1

1 Answer 1

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$
7
  • 1
    $\begingroup$ That was exactly my mistake, thanks for pointing it out. $\endgroup$
    – Jonathan H
    May 29, 2018 at 22:59
  • $\begingroup$ Out of curiosity, could you please refer to something / briefly explain the case of pariwise coprimality? $\endgroup$
    – Jonathan H
    May 29, 2018 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, 2018 at 23:02
  • 2
    $\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, 2018 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, 2018 at 0:16

You must log in to answer this question.

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