Artificial truth

The more you see, the less you believe.

[archives] [latest] | [homepage] | [atom/rss/twitter]

Odds of N random integers not having a common divisor
Sun 01 July 2018 — download

A friend of mine asked me an easy mathematics question, so I thought about writing a small post about it. The question was:

Given a random set of integers, what are the odds of them not having a single common divisor ?

The probability of a random integer to be even (divisible by $$2$$) is $$\frac{1}{2}$$, since a number is either even or odd. Similarly, the probability of a random integer to be divisible by $$3$$ is $$\frac{1}{3}$$ and so on, … but only for prime numbers, since an integer divisible by $$6$$ will also be divisible by $$2$$ and $$3$$. So we need to only consider primes, noted as ℙ in the rest of this article.

So intuitively, the probability of a random integer $$a$$ to be divisible by a prime number $$p$$ is $$\frac{1}{p}$$.

The probability of a set of $$n$$ random integers being divisible by a prime $$p$$ is $$\big( \frac{1}{p} \big)^n$$, accordingly, the probability of not being divisible is $$1 - \big( \frac{1}{p} \big)^n$$.

Since the probabilities are all independent, the probability of a set of $$n$$ random integer not being divisible by all primes is $$\prod_{p \in ℙ}{\bigg( 1 - \big( \frac{1}{p} \big)^n \bigg) }$$.

We can simplify this by transforming an Euler product into the Riemann zeta function, function (The proof can be found here, and isn't hard, you should read it ♥).

%% \begin{aligned} \prod_{p \in ℙ}{\bigg( 1 - \big( \frac{1}{p} \big)^n \bigg) } = \prod_{p \in ℙ}{\bigg( 1 - p^{-n} \bigg) } = \frac{1}{\zeta(n)} \end{aligned} %%

Getting a numerical estimation is a wikipedia or wolframalpha lookup away: For two numbers, this would be $$\frac{1}{\zeta({2})} = \frac{1}{\frac{\pi^2}{6}} = \frac{6}{\pi^2} \approx 0.6079 $$. For 10 numbers, it would approximately be $$0.9990$$, and so on…

While this looks coherent, there is an elephant in the room: how would you define/pick a set of random (as in equiprobable) integers over ℕ?

It would look like $$\forall a,b \in ℕ^2, P(a) = P(B), \sum_{i=0}^{\infty}P(a=i) = 1$$, meaning that we have two cases:

  1. $$P(a=n) = 0 \iff \sum_{i=0}^{\infty}{P(a=i)} = 0$$
  2. $$P(a=n) > 0 \iff \sum_{i=0}^{\infty}{P(a=i)} = \lim_{k \to \infty} k$$

Both of them are contradicting the 2nd axiom of probability, meaning that we can't have an uniform probability over ℕ. But in our case, we can simply hack something like "an finite set of random integer in ℕ, inferior to an arbitrary number (at least superior to the cardinal of our set of course)".