Associated Topics || Dr. Math Home || Search Dr. Math

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/
```
Associated Topics:
High School Probability

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