TAOCP 4.5.1 Exercise 2
Let $d = \gcd(u, v)$.
Exercise 2. [**] [$M15$] Prove that if $d = \gcd(u, v)$ then $u/d$ and $v/d$ are relatively prime.
Verified: yes
Solve time: 8m41s
Let $d = \gcd(u, v)$. By definition, $d$ divides both $u$ and $v$, so there exist integers $a$ and $b$ such that $u = ad$ and $v = bd$. Suppose $u/d$ and $v/d$ are not relatively prime, so there exists an integer $c > 1$ such that $c \mid (u/d)$ and $c \mid (v/d)$. Then $c \mid a$ and $c \mid b$, which implies $cd \mid u$ and $cd \mid v$. But $cd > d$, contradicting the maximality of $d$ as the greatest common divisor of $u$ and $v$. Therefore no such $c$ exists, and $u/d$ and $v/d$ are relatively prime.
This completes the proof.
∎