31) Let X and Y be independent random variables that are both equally likely to be either 1, 2,..., (10)^N, where N is very large. Let D denote the greatest common divisor of X and Y, and let Q_k = P(D = k).

(a) Give a heuristic argument that Q_k ≤

$$

\frac{1}{k^2}

$$

HINT: Note that in order for D to equal k, k must divide both X and Y and also X/k and Y/k must be relatively prime. (That is, they must have a greatest common divisor equal to 1.)

(b) Use part

(a) to show that Q₁ = P(X and Y are relatively prime] =

$$

\frac{1}{\sum_{k=1}^{\infty} 1/k^2}

$$

It is a well-known identity that

$$

\sum_{k=1}^{\infty} 1/k^2 = π²/6

$$, so Q₁ = 6/π² (In number theory this is known as the Legendre theorem.)

(e) Now argue that

$$

Q_1 = \prod_{i=1}^{\infty} \left( \frac{P_i^2-1}{P_i^2} \right)

$$

where P_i is the ith smallest prime greater than 1.

HINT: X and Y will be relatively prime if they have no common prime factors.

Hence, from part (b), we see that

$$

\prod_{i=1}^{\infty} \left( \frac{P_i^2-1}{P_i^2} \right) = \frac{6}{π^2}

$$

which was noted without explanation in Problem 11 of Chapter 4.

relationship between this problem and Problem 11 of Chapter 4 is X and Y are relatively prime if XY has no multiple prime factors.)