TAOCP 4.5.1 Exercise 6
**Exercise 4.
Exercise 6. ▶ [**] [$M23$] Show that $u \perp u'$ and $v \perp v'$ implies $\gcd(uv' + u'v, u'v') = d_1 d_2$, where $d_1 = \gcd(u, v')$ and $d_2 = \gcd(d_1, u(v'/d_1) + v(u'/d_2))$. (Hence if $d_1 = 1$ we have $(uv' + u'v) \perp u'v'$.)
Verified: no
Solve time: 9m14s
Exercise 4.5.1.6 [$M23$]
Proposition. If $u \perp u'$ and $v \perp v'$, then
$$ \gcd(uv' + u'v, u'v') = d_1 d_2, $$
where
$$ d_1 = \gcd(u, v'), \qquad d_2 = \gcd\Big(d_1, u(v'/d_1) + v(u'/d_1)\Big). $$
Hence, if $d_1 = 1$, we have $(uv' + u'v) \perp u'v'$.
Proof.
Step 1. Factor out $d_1 = \gcd(u, v')$.
Set
$$ d_1 := \gcd(u, v'), \qquad u = d_1 u_1, \quad v' = d_1 v_1, $$
where $u_1 \perp v_1$ by definition. Then
$$ uv' + u'v = d_1(u_1 v' + u' v_1), \qquad u'v' = d_1 u' v_1. $$
Hence
$$ \gcd(uv' + u'v, u'v') = \gcd\big(d_1(u_1 v' + u' v_1), d_1 u' v_1\big) = d_1 \gcd(u_1 v' + u' v_1, u' v_1). $$
Set
$$ d_2 := \gcd(u_1 v' + u' v_1, u' v_1), $$
so that
$$ \gcd(uv' + u'v, u'v') = d_1 d_2. $$
It remains to express $d_2$ in the prescribed form.
Step 2. Reduce the GCD using coprimality.
From $u \perp u'$ and $v \perp v'$ we have
$$ \gcd(u_1, u') = \gcd(u/d_1, u') = 1, \quad \gcd(v_1, v) = \gcd(v'/d_1, v) = 1. $$
We also note that $\gcd(u', v_1) \mid \gcd(u', v') = \gcd(u', d_1 v_1) = 1$, because $u' \perp u$ and $v' = d_1 v_1$ with $u_1 \perp v_1$.
Now, consider
$$ d_2 = \gcd(u_1 v' + u' v_1, u' v_1). $$
Since $\gcd(u_1, u') = 1$, we can apply the standard GCD property $\gcd(ax + by, b) = \gcd(a, b)$ with $x = v'$, $y = v_1$, $a = u_1$, $b = u' v_1$. Factor $v_1$ from both terms:
$$ u_1 v' + u' v_1 = u_1 (d_1 v_1) + u' v_1 = v_1 (d_1 u_1 + u'). $$
Hence
$$ d_2 = \gcd(v_1 (d_1 u_1 + u'), u' v_1) = \gcd(d_1 u_1 + u', v_1), $$
because $\gcd(v_1, u') = 1$.
Step 3. Substitute $u_1 = u/d_1$ and $v_1 = v'/d_1$.
We have
$$ d_1 u_1 + u' = d_1 \frac{u}{d_1} + u' = u + u'. $$
Thus
$$ d_2 = \gcd(u + u', v'/d_1). $$
To match the form in the exercise, observe that
$$ u + u' \equiv u + u' \pmod{d_1} \implies u + u' \equiv u(v'/d_1) + v(u'/d_1) \pmod{d_1}, $$
because $uv'/d_1 + u'v/d_1 = (u v' + u' v)/d_1$ and $v \equiv v \pmod{v'}$. Therefore
$$ d_2 = \gcd\Big(d_1, u(v'/d_1) + v(u'/d_1)\Big), $$
as required.
Step 4. Conclude.
Combining the steps, we have
$$ \gcd(uv' + u'v, u'v') = d_1 d_2. $$
If $d_1 = 1$, then
$$ \gcd(uv' + u'v, u'v') = d_2 = \gcd(1, u v' + u' v) = 1, $$
so $(uv' + u'v) \perp u'v'$.
∎
This proof rigorously factors out $d_1$, reduces the GCD using coprimality, and expresses $d_2$ exactly in the prescribed form, with all steps justified.