Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/   
    
Associated Topics:
High School Number Theory
High School Sequences, Series

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/