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
Math Forum Home || Math Library || Quick Reference || Math Forum Search