Choosing Numbers with No Common Factors

Date: 03/31/98 at 02:13:09
From: Hui Shen
Subject: Probability

A friend of mine asked me this question, and I have no idea what to 
do. Can you help?

What is the probability of choosing 2 numbers that have no common 
factors?

Date: 03/31/98 at 11:48:51
From: Doctor Rob
Subject: Re: Probability

This is a classic problem.  The short answer is 6/Pi^2, or about 
0.607927. Here is a way of seeing this.

Let P equal the probability of being relatively prime. Then it is 
clear that

   P = A(2) * A(3) * A(5) * A(7) * A(11) * ...,

where A(p) is the probability that two randomly chosen numbers will 
*not* both be divisible by p. Clearly A(p) = 1 - 1/p^2. 

The above equation says that two integers are relatively prime if and 
only if they have no prime number as a common divisor.  Thus

   P = Product (1-1/p^2)  over all prime numbers p.

The trick here is to consider 1/P:

   1/P = Product 1/(1-1/p^2),

and expand the fraction inside the product as a geometric series:

   1/P = Product (1 + 1/p^2 + 1/p^4 + 1/p^6 + ...), over all primes p,
       = Product Sum 1/p^(2*i), over all i >= 0 and all primes p.

Now if we exchange the product and sum, we find

   1/P = Sum Product 1/p^(2*i),
       = Sum 1/(Product p^i)^2
       = Sum 1/n^2, over all n >= 1

This is because for each integer n, we can give its prime power
factorization as n = Product p^i for some set of i's. Then for the 
prime p, choose the term with i = e(p). Thus

   P = 1/[Sum 1/n^2]

Now all I have to do is convince you that Sum 1/n^2 = Pi^2/6. Here is 
a slick proof of that fact due to Calabi, using calculus.

Consider

   I = (4/3)*Integral Integral 1/(1-x^2*y^2)dx dy, 
              0 <= x <= 1, 0 <= y <= 1

On the one hand, it turns out that I = Sum 1/n^2, which we prove as
follows. Expanding 1/(1-x^2*y^2) as a geometric series, we get

   I = (4/3)*Integral Integral Sum (x^2*y^2)^i dx dy
     = (4/3)*Integral Integral Sum x^(2*i)*y^(2*i) dx dy
     = (4/3)*Integral Sum [Integral x^(2*i) dx]*y^(2*i) dy
     = (4/3)*Integral Sum y^(2*i)/(2*i+1) dy
     = (4/3)*Sum Integral y^(2*i)/(2*i+1) dy
     = (4/3)*Sum 1/(2*i+1)^2,

where the sum is over all i >= 0, and the integrals are from 0 to 1.  
Now

   Sum 1/n^2 = Sum 1/(2*i+1)^2 + Sum 1/(2*i)^2
             = Sum 1/(2*i+1)^2 + (1/4)*Sum 1/i^2
             = Sum 1/(2*i+1)^2 + (1/4)*Sum 1/n^2

So

   (3/4)*Sum 1/n^2 = Sum 1/(2*i+1)^2

Thus

   I = (4/3)*(3/4)*Sum 1/n^2,
     = Sum 1/n^2.

On the other hand, it turns out that I = Pi^2/6, which we prove in 
this way.  Make the substitution x = sin(u)/cos(v) and
y = sin(v)/cos(u), so

   x^2*y^2 = tan^2(u)*tan^2(v),

and

   dx dy = J du dv,

where

       | cos(u)/cos(v)  sin(u)*sin(v)/cos^2(v) |
   J = |                                       |,
       | sin(u)*sin(v)/cos^2(u)  cos(v)/cos(u) |

     = 1 - tan^2(u)*tan^2(v)

Thus

   I = (4/3)*Integral Integral 1/(1-tan^2(u)*tan^2(v))*
                                    (1-tan^2(u)*tan^2(v)) du dv,

     = (4/3)*Integral Integral 1 du dv,

over the region u >= 0, v >= 0, u + v <= Pi/2.  Then the double 
integral is just the area of that region, which is a triangle of 
height and base Pi/2, whose area is Pi^2/8.  Thus

   I = (4/3)*Pi^2/8,
     = Pi^2/6.

Thus

   Sum 1/n^2 = Pi^2/6,
   P = 6/Pi^2.

Another proof uses this Fourier series,

   x^2/2 = Pi*x - Pi^2/3 + 2*Sum cos(n*x)/n^2, over n >= 1,

which is valid for 0 <= x <= 2*Pi.  Set x = 0 and rearrange this 
equation to get

   Sum 1/n^2 = Pi^2/6.

-Doctor Rob,  The Math Forum
Check out our web site http://mathforum.org/dr.math/