If you pick any two integers at random, what is that probability that they will be relatively prime? ("relatively prime" means that the two numbers share no divisors except 1)

Tell how you end up with the answer.

The greatest common divisor of two integers m and n can be interpreted as the number of lattice points in the plane which lie on the straight line connecting the vectors (0,0) and (m, n), excluding (m, n) itself.

Therefore, any lattice point (m, n) that is 'visible' from the origin, that is, no other lattice points lie on the line connecting the (0,0) vector and its own, means that the selected values of m and n have no greatest common factor; they are relatively prime.

Therefore, we need to find the fraction of all lattice points that are visible from the origin. This is found by using the Riemann zeta function, to represent which let's use Ç(z).

1/[Ç(2)] is the fraction of Cartesian coordinate pairs visible from the origin, and is thus the fraction we are looking for.This evaluates to 1/(π²/6), or 6/π².

6/π² is approximately 0.60788555894594382, which is about the same value Charlie found experimentally.

In general, the probability that n randomly selected integers lack a common divisor is [Ç(n)]^(-1).
The probability that n random integers lack a pth power common divisor is [Ç(np)]^(-1).

For more about the Riemann zeta function, look <a href=http://mathworld.wolfram.com/RiemannZetaFunction.html>here.

Posted by DJ on 2003-07-13 20:54:54