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
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.
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
= 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
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
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))
We can generalize. Let us introduce the following notation:
p[i]
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)
PS(K)
Cnt(K) / (N-1)^2
, the sample frequency of relatively prime pairs of integersP0
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
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
.
P(K,n)
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) + ...
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 + ...
1 +
Sum{ 1/j^n, j is an integer whose prime factors are 2 or 3 }
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
.
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.
This site's top page is http://okmij.org/ftp/
oleg-at-okmij.org
Converted from SXML by SXML->HTML