Exercise 1.3.50* (gcd abound)

Question

Show that 
$$(ab,cd) = (a,c)(b,d) \left(\frac{a}{(a,c)},\frac{d}{(b,d)} \right) \left(\frac{c}{(a,c)},\frac{b}{(b,d)} \right).
$$

Richard Ganaye · Accepted Answer

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

Here we write $\mathrm{gcd}(a,b) = (a,b)$.
\begin{proof} 
Let $p_1,\ldots,p_k$ the prime factors of one of the integers $a,b,c,d$.
Then the decompositions of $a,b,c,d$ in prime factors are
\begin{align*}
a &= p_1^{a_1} \cdots p_k^{a_k},\
b &= p_1^{b_1} \cdots p_k^{b_k},\
c &= p_1^{c_1} \cdots p_k^{c_k},\
d &= p_1^{d_1} \cdots p_k^{d_k},\
\end{align*}
where $a_i\geq 0, b_i \geq 0, c_i \geq 0, d_i \geq 0.$

Then, writing only the first factor,
\begin{align*}
\frac{a}{(a,c)} &= p_1^{a_1 - \min(a_1,c_1)} \cdots,\
\frac{b}{(b,d)} &= p_1^{d_1 - \min(b_1,d_1)} \cdots,\
\left(\frac{a}{(a,c)},\frac{d}{(b,d)} ight) &= p_1^{\min(a_1-\min(a_1,c_1), d_1 - \min(b_1,d_1))} \cdots,\
\left(\frac{c}{(a,c)},\frac{b}{(b,d)} ight) &= p_1^{\min(c_1-\min(a_1,c_1), b_1 - \min(b_1,d_1))}\cdots.
\end{align*}
Therefore
\begin{align*}
&(a,c)(b,d) \left(\frac{a}{(a,c)},\frac{d}{(b,d)} ight) \left(\frac{c}{(a,c)},\frac{b}{(b,d)} ight)\
&= p_1^{\min(a_1,c_1) + \min(b_1,d_1) + \min(a_1-\min(a_1,c_1), d_1 - \min(b_1,d_1))+ \min(c_1-\min(a_1,c_1), b_1 - \min(b_1,d_1))} \cdots,
\end{align*}
and
$$(a,b)(c,d) = p_1^{\min(a_1,b_1) + \min(c_1,d_1)} \cdots.$$
The property is proved if we verify, for all natural numbers $A,B,C,D$,
\begin{align*}
\min(A+B,C+D) =&\phantom{+}\min(A,C) + \min(B,D)\
&+ \min(A-\min(A,C),D-\min(B,D))\
&+\min(C - \min(A,C), B - \min(B,D)). \qquad (1)
\end{align*}
Note that left and right members of this equality are invariant if we replace simultaneously $A$ by $C$ and $B$ by $D$ (i.e. by the permutation 
$\sigma = \begin{pmatrix} A & B & C & D\ C & D & A & B\end{pmatrix}$). This allows us the reduce the numbers of cases in the verification.
\begin{itemize}
\item If $A \leq C$ and $B \leq D$, then $A+B \leq A+D$, so $\min(A+B,C+D)  = A+B$, and
\begin{align*}
&\min(A,C) + \min(B,D) = A + B\
&\min(A-\min(A,C),D-\min(B,D))=\min(0, D-B) = 0\
&\min(C - \min(A,C), B - \min(B,D))= \min(C-A,0) = 0
\end{align*}
thus (1) is true.
\item If $A\geq C$ and $B \geq D$: idem, using the permutation $\sigma$.
\item If $A \leq C$ and $B \geq D$,
\begin{align*}
&\min(A,C) + \min(B,D) = A + D\
&\min(A-\min(A,C),D-\min(B,D))=\min(0, 0) = 0\
&\min(C - \min(A,C), B - \min(B,D))= \min(C-A,B-D) 
\end{align*}
It remains to show
$$\min(A+B,C+D) = A + D + \min(C-A,B-D),$$
with two sub-cases:
    \begin{enumerate}
     \item[$-$] If $A+B \leq C+D$, then $C-A \geq B-D$, therefore
     $$A + D + \min(C-A,B-D) = A+D +B-D = A+B=\min(A+B,C+D).$$
     \item[$-$] If $A+B \geq C+D$, then $C-A \leq B-D$, therefore
     $$A + D + \min(C-A,B-D) = A+D + C-A = C+D = \min(A+B,C+D).$$
    \end{enumerate}
\item If $A \geq C$ and $B \leq D$: idem, using the permutation $\sigma$.
\end{itemize}
This proves (1), and so
$$(ab,cd) = (a,c)(b,d) \left(\frac{a}{(a,c)},\frac{d}{(b,d)} ight) \left(\frac{c}{(a,c)},\frac{b}{(b,d)} ight).
$$
\end{proof}

Exercise 1.3.50* (gcd abound)

Answers

Comments

Exercise 1.3.50* (gcd abound)

Answers

Comments

Add answer