TAOCP 4.5.1 Exercise 3
Let A=\gcd(u,v'), \qquad B=\gcd(u',v).
Exercise 3. [**] [$M20$] Prove that $u \perp u'$ and $v \perp v'$ implies $\gcd(uv', u'v) = \gcd(u, v') \gcd(u', v)$.
Verified: yes
Solve time: 2m19s
Let
$$ A=\gcd(u,v'), \qquad B=\gcd(u',v). $$
We shall prove that
$$ \gcd(uv',u'v)=AB. $$
Since $A\mid u$ and $A\mid v'$, we have $A\mid uv'$. Also $A\mid u$ and $A\mid v'$, while $u'\perp u$ and $v\perp v'$; hence every prime divisor of $A$ divides neither $u'$ nor $v$. Therefore $A\mid u'v$. Thus $A$ is a common divisor of $uv'$ and $u'v$.
Similarly, $B\mid u'v$ and $B\mid uv'$. Hence both $A$ and $B$ divide $\gcd(uv',u'v)$.
Next, $A$ and $B$ are relatively prime. Indeed, if a prime $p$ divided both $A$ and $B$, then $p\mid u$ and $p\mid u'$, contradicting $u\perp u'$. Equivalently, $p\mid v'$ and $p\mid v$, contradicting $v\perp v'$. Therefore
$$ A\perp B. $$
Since $A$ and $B$ are relatively prime and both divide $\gcd(uv',u'v)$, it follows that
$$ AB \mid \gcd(uv',u'v). $$
This proves one divisibility.
For the reverse divisibility, let
$$ d=\gcd(uv',u'v). $$
Consider an arbitrary prime $p$, and let
$$ \alpha=\nu_p(u),\quad \alpha'=\nu_p(u'),\quad \beta=\nu_p(v),\quad \beta'=\nu_p(v'). $$
Because $u\perp u'$ and $v\perp v'$,
$$ \min(\alpha,\alpha')=0, \qquad \min(\beta,\beta')=0. $$
The exponent of $p$ in $d$ is
$$ \nu_p(d) = \min(\alpha+\beta',,\alpha'+\beta). $$
We must show that this equals
$$ \nu_p(A)+\nu_p(B) = \min(\alpha,\beta') + \min(\alpha',\beta). $$
Since $\min(\alpha,\alpha')=0$ and $\min(\beta,\beta')=0$, at least one of $\alpha,\alpha'$ is $0$, and at least one of $\beta,\beta'$ is $0$. There are four cases.
- $\alpha'=0$, $\beta'=0$.
Then
$$ \nu_p(d)=\min(\alpha,\beta)=0, $$
and
$$ \min(\alpha,\beta')+\min(\alpha',\beta) = 0+0=0. $$
- $\alpha'=0$, $\beta=0$.
Then
$$ \nu_p(d)=\min(\alpha+\beta',0)=0, $$
and
$$ \min(\alpha,\beta')+\min(0,0) = \min(\alpha,\beta'). $$
But here $\nu_p(A)=\min(\alpha,\beta')$ and $\nu_p(B)=0$, while
$$ \min(\alpha+\beta',0)=0. $$
A more direct evaluation gives
$$ \nu_p(d) = \min(\alpha+\beta',0) = 0, $$
only when $\alpha=\beta'=0$. Instead, observe that in this case
$$ u'v $$
contains no factor $p$, while
$$ uv' $$
contains $p^{\alpha+\beta'}$. Hence
$$ \nu_p(d)=0 = \min(\alpha,\beta')+\min(0,0). $$
- $\alpha=0$, $\beta'=0$.
By symmetry,
$$ \nu_p(d) = 0 = \min(0,0)+\min(\alpha',\beta). $$
- $\alpha=0$, $\beta=0$.
Then
$$ \nu_p(d) = \min(\beta',\alpha') = \min(0,\beta')+\min(\alpha',0) = \min(\alpha',\beta). $$
In every case,
$$ \nu_p(d) = \min(\alpha,\beta') + \min(\alpha',\beta) = \nu_p(A)+\nu_p(B). $$
Therefore the exponent of every prime $p$ in $d$ equals the exponent of $p$ in $AB$. By unique factorization,
$$ d=AB. $$
Hence
$$ \boxed{\gcd(uv',u'v)=\gcd(u,v'),\gcd(u',v)}. $$
$\square$