Greatest Common Divisor - Probabilities and Expected Value

Probabilities and Expected Value

In 1972, James E. Nymann showed that k integers, chosen independently and uniformly from {1,...,n}, are coprime with probability 1/ζ(k) as n goes to infinity. (See coprime for a derivation.) This result was extended in 1987 to show that the probability that k random integers has greatest common divisor d is d-k/ζ(k).

Using this information, the expected value of the greatest common divisor function can be seen (informally) to not exist when k = 2. In this case the probability that the gcd equals d is d−2/ζ(2), and since ζ(2) = π2/6 we have

This last summation is the harmonic series, which diverges. However, when k ≥ 3, the expected value is well-defined, and by the above argument, it is

For k = 3, this is approximately equal to 1.3684. For k = 4, it is approximately 1.1106.