8.2 The purpose of this problem is to demonstrate that the probability that two random numbers are relatively prime is about 0.6.
Let P = Pr[gcd(a,
b) = 1]. Show that Pr[gcd(a,
b) = d] = P/d2
Hint: Consider the quantity gcd (a/d , b/d)
b. The sum of the result of part (
a) over all possible values of d is 1. That is:
