probability that two positive integers are relatively prime


The probability that two positive integers chosen randomly are relatively prime is

6π2=0.60792710185.

At first glance this “naked” result is beautiful, but no suitable definition is there: there isn’t a probability spaceMathworldPlanetmath defined. Indeed, the word “probability” here is an abuse of language. So, now, let’s write the mathematical statement.

For each n+, let Sn be the set {1,2,,n}×{1,2,,n} and define Σn to be the powerset of Sn. Define μ:Σn by μ(E)=|E|/|Sn|. This makes (Sn,Σn,μ) into a probability space.

We wish to consider the event of some (x,y)Sn also being in the set An={(a,b)Sn:gcd(a,b)=1}. The probability of this event is

P((x,y)An)=SnχAndμ=|An||Sn|.

Our statement is thus the following. For each n+, select random integers xn and yn with 1xn,ynn. Then the limit limnP((xn,yn)An) exists and

limnP((xn,yn)An)=6π2.

In other words, as n gets large, the fraction of |Sn| consisting of relatively prime pairs of positive integers tends to 6/π2.

References

  • 1 Challenging Mathematical Problems with Elementary Solutions, A.M. Yaglom and I.M. Yaglom, Vol. 1, Holden-Day, 1964. (See Problems 92 and 93)
Title probability that two positive integers are relatively prime
Canonical name ProbabilityThatTwoPositiveIntegersAreRelativelyPrime
Date of creation 2013-03-22 14:56:08
Last modified on 2013-03-22 14:56:08
Owner mps (409)
Last modified by mps (409)
Numerical id 21
Author mps (409)
Entry type Result
Classification msc 11A41
Classification msc 11A05
Classification msc 11A51