Probability of Random Numbers Being Coprime

Date: 08/12/97 at 12:10:22
From: Jonah Knobler
Subject: Probability of random numbers being coprime

I have heard from numerous sources that the probability of two 
randomly selected integers being coprime is 6/(pi^2). I have seen 
fragments of proofs to this effect but nothing conclusive as of yet.  
I have had no calculus but have a basic understanding of Taylor 
series, etc. How do you show this is true? What an incredible number 
to pop up out of nowhere! Would this have anything to do with the fact 
that sigma x = 1 to infinity (x^2) is (pi^2)/6?  Could you explain how 
to show this latter fact as well, and any relation between these two 
seemingly random quantities?

Thanks!

- Jonah Knobler

Date: 08/15/97 at 16:56:24
From: Doctor Rob
Subject: Re: Probability of random numbers being coprime

Indeed, you have made the correct connection here.

The idea is to separate the pairs of numbers according to their GCD's.
Start with a finite part of the plane, and then take the limit as its
dimensions approach infinity.

Consider the set of pairs (a,b) with 1 <= a <= N, and 1 <= b <= N.
There are N^2 altogether. Of these, [N/p]^2 share the prime divisor p,
where [.] is the greatest integer function. Then the numbers which
are relatively prime are N^2 - SUM [N/p]^2 + SUM SUM [N/(p*q)]^2 - ...
The fractions which are relatively prime are, then, using inclusion-
exclusion,

   f(N) = 1 - SUM ([N/p]/N)^2 + SUM SUM ([N/(p*q)]/N)^2 - ...

Now let f = lim f(N) as N -> infinity. 
It is clear that [N/a]/N -> 1/a, so

   f = 1 - SUM 1/p^2 + SUM SUM 1/(p^2*q^2) - ...
     = PROD (1 - 1/p^2)
     = PROD {1/(1 + 1/p^2 + 1/p^4 + 1/p^6 + ...)}
     = 1/PROD (1 + 1/p^2 + 1/p^4 + 1/p^6 + ...)
     = 1/(SUM 1/n^2)
     = 1/(Pi^2/6)
     = 6/Pi^2

The proof that SUM 1/n^2 = Pi^2/6 is perhaps most easily seen using
the following double integral:

   I = INT INT dy dx/(1 - x^2*y^2),

where the integrals both go from 0 to 1.  It turns out that the value 
of I is 3/4 of the sum you are looking for.  A clever change of 
variables makes it clear that this double integral is just Pi^2/8.

Another proof of the formula is available using Fourier series, that 
is, series of the form 

   f(x) = a(0) + SUM a(n) cos(nx) + b(n) sin(nx),

where the sum runs over all n > 0. If you choose the correct function,
and find the coefficients a(n) and b(n) that make this work, then when
the function is evaluated at x = 0, you get

   f(0) = a(0) + SUM a(n),

which gives you the value you want. I don't remember the function, but
it is moot, since the determination of the coefficients a(n) and b(n)
requires calculus.

If you are willing to accept the coefficients of a particular Fourier
Series, then here is a solution.  I take from Robert K. Ritt, _Fourier
Series_, McGraw-Hill (1970), pp. 16-17:

f(t) = t*(2*Pi - t)/Pi^2
     = 2/3 - (4/Pi^2)*SUM cos(n*t)/n^2,  0 <= t <= 2*Pi,

and f(t) = f(t - 2*Pi*k) outside that range, where the sum runs from
n=1 to infinity, and k is any integer.  I actually checked that this
is correct.

Using this, substitute t = 0, and you get

   0 = 2/3 - (4/Pi^2)*SUM 1/n^2
   SUM 1/n^2 = Pi^2/6.

Q.E.D.

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