TAOCP 4.5.2 Exercise 11
By Theorem 4.
Section 4.5.2: The Greatest Common Divisor
Exercise 11. [**] [M22] What is the probability that $\gcd(u, v) \le 3$? (See Theorem D.) What is the average value of $\gcd(u, v)$?
Verified: yes
Solve time: 1m19s
By Theorem 4.5.2D, the probability that two positive integers $u$ and $v$ are relatively prime is $\frac{6}{\pi^2}$. The event $\gcd(u, v) \le 3$ is the union of the events $\gcd(u, v) = 1$, $\gcd(u, v) = 2$, and $\gcd(u, v) = 3$. Each of these probabilities can be expressed as $P(\gcd(u, v) = k) = P(u/k \perp v/k)/k^2$, because dividing both numbers by $k$ reduces the problem to the case of coprime integers. Hence we have
$$ P(\gcd(u, v) = 1) = \frac{6}{\pi^2}, \quad P(\gcd(u, v) = 2) = \frac{6}{\pi^2 \cdot 2^2} = \frac{3}{2\pi^2}, \quad P(\gcd(u, v) = 3) = \frac{6}{\pi^2 \cdot 3^2} = \frac{2}{3\pi^2}. $$
Summing these gives
$$ P(\gcd(u, v) \le 3) = \frac{6}{\pi^2} + \frac{3}{2\pi^2} + \frac{2}{3\pi^2} = \frac{49}{6\pi^2}. $$
To compute the average value of $\gcd(u, v)$, observe that
$$ \mathbb{E}[\gcd(u, v)] = \sum_{k \ge 1} k , P(\gcd(u, v) = k) = \sum_{k \ge 1} \frac{k \cdot 6}{\pi^2 k^2} = \frac{6}{\pi^2} \sum_{k \ge 1} \frac{1}{k} . $$
The harmonic series diverges, so the expected value of $\gcd(u, v)$ is infinite.
$\boxed{P(\gcd(u, v) \le 3) = 49/(6\pi^2),\quad \text{average value of } \gcd(u, v) = \infty}$ ∎