Probabilities of relative primality

From The Universe of Discourse -- the probability that two randomly-selected polynomials over Z₂ are relatively prime is 1/2. (More formally, the probability that two randomly-selected polynomials over Z₂ of degree less than n are relatively prime is 1/2 + 1/4ⁿ; the original result holds as n goes to infinity.) There's actually an almost one-to-one correspondence between pairs which aren't relatively prime and pairs which are. You can find this, and some more general results, in "The Probability of Relatively Prime Polynomials", from the June 2007 issue of Mathematics Magazine, (Arthur T. Benjamin and Curtis D Bennett, page 196).

The most general result is as follows: if a₁(x), ..., a_m(x) are randomly chosen polynomials of degree less than n in F[x], where F is the finite field with q elements, then the probability that they are relatively prime is 1 - 1/q^m-1 + (q-1)/q^mn; this is all shown with a counting argument that invokes the Euclidean algorithm. The case from The Universe of Discourse is the case m = 2, where n goes to infinity.

This reminds me of one of my favorite statements in mathematics: "the probability that two randomly chosen integers are relatively prime is 6/π²." This seems almost meaningless -- how can we choose integers "at random"? More formally, let A(n) be the number of relatively prime pairs of integers in {1, 2, ..., n}; then

The convergence is pretty quick; A(100)/100² = 0.6087, and A(1000)/1000² = 0.608383, while 6/π² = 0.6079...

Why is this true? Well, the probability that two integers are relatively prime is the probability that they're not both divisible by 2, times the probability that they're not both divisible by 3, times the probabiltiy that they're not both divisible by 5, and so on. The probability that two integers aren't both divisible by a given prime p is 1 - 1/p². So the probability that two "randomly chosen integers" aren't both divisible by the same prime p for all primes p is

and Euler showed that this was equal to 1/ζ(2), or 6/π².

Similarly, the probability that n randomly chosen integers are relatively prime (not pairwise relatively prime; I count a triple like (6, 10, 15), since there isn't a prime number dividing all three of those) is 1/ζ(n). We recall that
ζ(n) = 1 + (1/2)ⁿ + (1/3)ⁿ + ...
and if n is large we can throw away all but the first two terms; thus the probability that n randomly chosen integers are relatively prime is about 1 - (1/2)ⁿ. This makes sense; if there are n integers that aren't relatively prime, the reason they're not relatively prime is almost always because they're all even.

The logical next question is: what is the average of the greatest common divisor of randomly chosen integers? From some quick numerical work, it looks like

grows like log n, that is, the average of the GCDs of pairs of integers randomly chosen from {1, 2, ..., n} is about some constant times log n. (The constant, to one decimal place, looks like 0.6.) But I don't know the answer. If I get bored at some point in the next couple days I'll see if I can figure it out.