The greatest common divisor and probability

The greatest common divisor of two numbers is the largest number that goes evenly into both. For example, the greatest common divisor of 30 and 45 would be 15. On the other hand the greatest common divisor of 30 and 41 would only be 1.

In the first portion of this meeting, we gave a lesson on an efficient way to calculate the greatest common divisor of two numbers: The Euclidean algorithm.

In the investigation portion of this meeting, we asked, given two random numbers, what is most likely to be the greatest common divisor of the two numbers? Using dozens of pairs of random numbers, and dividing the work among our participants, we discovered that the number 1 was far more likely to be the greatest common divisor than any other number. But why is it true?

Check out our handouts!
GCD handout
GCD worksheet