Let X and Y be independent random variables that are both equally likely to be either 1,2,...

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 Qk = P{D = k}.

(a) Give a heuristic argument that

---

(b) Use part (a) to show that

---

Q1 = P{X and Y are relatively prime}

It is a well-known identity that  6/π2. (In number theory, this is known as the Legendre theorem.)

(c) Now argue that  where Pi is the ith-smallest prime greater than 1.