previous   next   contents   top

The probability of randomly chosen integers being relatively prime

  1. Introduction
  2. Leading example
  3. Full Theorem
  4. Lemma 1. The Limit of P(K,n)
  5. Final Remarks

  

Introduction

What is the probability that two integers m and n picked at random are relatively prime?

The answer, given in
< http://mathworld.wolfram.com/RelativelyPrime.html>
is

Prob{(m,n)=1} = 1/ Z[2] = 6/PI^2

given the reasonable definition of "random integer". Here Z[x] is Riemann zeta function.

The MathWorld page shows a geometric proof of that formula based on lattice points on a plane. The proof can be generalized to three or more random integers.

On the present page, we show a different proof of the same result. The proof makes it clear what a "reasonable definition of a random integer" means precisely. The proof also easily generalizes to three or more integers.


  

Leading example

Let us consider a set of 5 numbers: {2,3,4,5,6}. Of total 25 pairs of numbers, 9 pairs -- {2,4,6} x {2,4,6} -- have the common factor of 2. Four more pairs -- (3,3), (3,6), (6,3) and (6,6) -- have the common factor of 3. However we have already counted the pair (6,6), because the two numbers have the common factor 2. One pair, (5,5), has the common factor of 5.

The number of relatively prime pairs adds to

      Cnt = 5^2 - floor(6/2)^2 - floor(6/3)^2 + floor(6/2/3)^2 - floor(6/5)^2
     { or, in a more regular way }
      = 5^2 - floor(6/2)^2 - floor(6/3)^2 + floor(6/2/3)^2 - floor(6/5)^2
      + floor(6/2/5)^2 + floor(6/3/5)^2 - floor(6/2/3/5)^2
     { all the terms we added are actually zeros }

Then

      Cnt - 6^2*(1-1/2^2)*(1-1/3^2)
      = 5^2 - 6^2 - floor(6/5)^2
      + floor(6/2/5)^2
      + floor(6/3/5)^2
      - floor(6/2/3/5)^2

Therefore,

      abs(Cnt - 6^2*(1-1/2^2)*(1-1/3^2))
      <= (6+5) + (6/5)^2 + (6/2/5)^2 + (6/3/5)^2 + (6/2/3/5)^2
where we took into account that
      abs(x+y-z) <= abs(x) + abs(y) + abs(z)
      floor(x) <= x, x>0

To continue further,

(1)    abs(Cnt - 6^2*(1-1/2^2)*(1-1/3^2))
      <= (6+5) + 6^2*((1+1/2^2)(1+1/3^2)(1+1/5^2) - (1+1/2^2)(1+1/3^2))

  

Full Theorem

We can generalize. Let us introduce the following notation:

p[i]
the i-th prime number, p[1]=2
N(K)
p[1]*p[2]*...*p[K]
kp[K]
max{ k' | p[k'] < N[K] }
P(K)
Prod{ (1-1/p[i]^2), i=1..K }
F(K)
Prod{ (1+1/p[i]^2), i=1..K }
G(K)
P(K) * F(K) = Prod{ (1-1/p[i]^4), i=1..K }
Cnt(K)
the number of pairs from {2..N} x {2..N} that are relatively prime
PS(K)
Cnt(K) / (N-1)^2, the sample frequency of relatively prime pairs of integers
P0
the desired probability that two integers > 1 chosen at random are relatively prime

We can generalize eq. (1) as follows:

(2)    abs(PS(K) - N^2/(N-1)^2 P(K))
      < (2N-1)/(N-1)^2 + N^2/(N-1)^2 ( F[kp[K]] - F[K] )

Or introducing G(K)

(3)    abs(PS(K) - N^2/(N-1)^2 P(K))
      < (2N-1)/(N-1)^2 + N^2/(N-1)^2 ( G(kp[K])/P(kp[K]) - G(K)/P(K) )

Lemma 1 below shows that P(K) -> 1/Z[2] and G(K) -> 1/Z[4] as K->Infinity. Therefore, G(kp[K])/P(kp[K]) and G(K)/P(K) have the same limit as K->Infinity, namely, Z[2]/Z[4]. We take into account that kp[K] >= K by definition. If we consider eq. (3) under the limit K->Infinity, which implies N->Infinity, we obtain

      abs(P0 - 1/Z[2]) = 0
provided that PS(K) converges. The convergence of sample frequencies to the probability is the assumption of a "reasonable definition of choosing integers at random." All other functions mentioned in eq. (3) are converging. We have used the facts that subtraction, addition and multiplication can be lifted out of the limit, provided all the limits in question exist, and
      (2N-1)/(N-1)^2 -> 0 as N->Infinity
      N^2/(N-1)^2 -> 1 as N->Infinity

Thus we obtain the desired result: the probability of two randomly chosen integers to be relatively prime is P0 = 1/Z[2]. It is easy to see that the probability that three random integers are relatively prime is 1/Z[3], etc.

It's known that Z[2], the sum of inverse squares of all the numbers, is PI^2/6. That result is easy to derive from the equality PI/4 = arctan(1) and the expansion of arctan(x) into the Tailor series. The probability that two random integers are not relatively prime -- i.e., they form a reducible fraction -- is therefore 1 - P0 = 1 - 6/PI^2.


  

Lemma 1. The Limit of P(K,n)

We show that the limit of P(K,n) = Prod{ (1-1/p[i]^n), i=1..K } as K->Infinity is 1/Z[n], where Z[n] is Riemann zeta-function
      Z[n] = Sum{ 1/i^n, i=1.. } = Prod{ 1/(1-1/p[i]^n), i=1.. }

This is just an inverse of the well-known result by Euler. I have derived it from scratch and thus gained a better appreciation of it.

Let us consider K first prime numbers, p[1] .. p[K], where p[1]=2. A term 1/(1 - (1/2)^n) is a sum of a geometric progression:

      1 + (1/2)^n + (1/2)^(2n) + ...
A product 1/(1 - (1/2)^n) * 1/(1 - (1/3)^n) is the product of the sums of two geometric progressions,
      1 + (1/2)^n + (1/2)^n*(1/3)^n + (1/2)^(2n)*(1/3)^n + ...
which can be written as
      1 + Sum{ 1/j^n, j is an integer whose prime factors are 2 or 3 }
Therefore,
      1/P(K,n) = Prod{ 1/(1 - (1/p[i])^n), i=1..K }
      = 1 + Sum{ 1/j^n, j is an integer with prime factors in p[1]..p[K] }

The latter sum is absolutely convergent. Let us consider the absolutely convergent Sum{ 1/j^n, j is any integer }, n>1, which is by definition Z[n]. We observe that 1/P(K,n) is a monotonically increasing function of K and with Z[n] as an upper bound. Therefore, 1/P(K,n) (absolutely) converges. If we consider the terms of both sums up to j=N(K) using the notation above, the difference does not exceed 1/P(kp[K],n) - 1/P(K,n), which converges to 0 as K->Infinity.


  

Final Remarks

The article An efficient Eratosthenes Sieve implementation describes an efficient Eratosthenes sieve algorithm in Scheme and takes advantage of the exact rational arithmetics of Scheme to illustrate Lemma 1.

The location of zeros of the Zeta function is related to the Prime number theorem, and the Riemann hypothesis,
< http://mathworld.wolfram.com/RiemannHypothesis.html>
< http://www.ams.org/new-in-math/cover/prime-chaos.html>

This page is based on the articles "Random mutually primes" posted on comp.lang.scheme on November 9, 11 and 13, 2001.


Last updated March 1, 2004

This site's top page is http://okmij.org/ftp/

oleg-at-okmij.org
Your comments, problem reports, questions are very welcome!

Converted from SXML by SXML->HTML