Home > Problem of the Week > Archive List > Detail

<< Prev 10/9/2011 Next >>

Think of a Fraction...Any Fraction...

What is the probability that a random fraction is irreducible?

By definition, a random fraction will be a fraction whose numerator and denominator are random natural numbers.

And, irreducible means that the GCD of the numerator and denominator is 1.

A Big Concern: How can you attack this problem, as it is basically impossible to sample a natural number? Yet, it is possible to randomly sample from a finite set of natural numbers (e.g. {1, 2, 3, 4, ...., 4999, 5000}).

Finally, this problem can even be extended into the complex plane. Below is a picture of the irreducible "complex" fractions for part of the plane (Thanks to Wolfram's Math World and Clifford Pickover's work):


Hint: Perform an experiment. Start with an interval {n, n+1, n+2, ..., n+k}, sample numerators and denominators...is your fraction reducible? Repeat m times.

Do you need to be concerned with value of n? Or that the sequence is increasing by 1 (or any fixed number)?

Also, it turns out that it is important to decide if your samples are with or without replacement...with the distinction becoming less important as the size of the interval becomes extremely large in size?


Solution Commentary: Rather than spoil the interesting answer or solution to this problem, I offer three notes:

  • First (and this will sound strange), assume that your response to the original question is M. Now, divide 6 by M, and then take the square root of that answer. If this value is close to π, you probably are on the right track...
  • Second, a good discussion of the problem is Jim Fey's "Probability, Integers, and Pi" (Mathematics Teacher, November 1973, pp. 329-332)
  • And third, a full solution is provided in the Mathematics Magazine, Jan/Feb 1955, pp. 170-171.