TAOCP 4.5.2 Exercise 13

Section 4.5.2: The Greatest Common Divisor

Exercise 13. [**] [HM23] Given that $u$ and $v$ are random odd positive integers, show that they are relatively prime with probability $8/\pi^2$.

Verified: yes
Solve time: 1m11s

Let

$$ P_d=\Pr(\gcd(u,v)=d). $$

By Theorem D, the probability that two random positive integers are relatively prime is

$$ P_1=\frac6{\pi^2}. $$

If $u$ and $v$ are restricted to odd integers, write $u=da$, $v=db$, where $d=\gcd(u,v)$ and $a\perp b$. Since $u$ and $v$ are odd, $d$, $a$, and $b$ must all be odd. Thus

$$ P_1^{(\mathrm{odd})} =\sum_{\substack{k\ge1\ k\text{ odd}}}\mu(k)\frac1{k^2}, $$

by the argument of Exercise 10. The Euler product therefore becomes

$$ P_1^{(\mathrm{odd})} =\prod_{p\text{ odd prime}}\left(1-\frac1{p^2}\right). $$

Using

$$ \prod_{p}\left(1-\frac1{p^2}\right)=\frac6{\pi^2}, $$

we remove the factor corresponding to $p=2$:

$$ P_1^{(\mathrm{odd})} =\frac{\dfrac6{\pi^2}}{1-\dfrac1{2^2}} =\frac{\dfrac6{\pi^2}}{\dfrac34} =\frac8{\pi^2}. $$

Hence the probability that two random odd positive integers are relatively prime is

\boxed{\frac8{\pi^2}}. ] ∎