Blog 1

Random Talk on Random Thoughts

Product of GCD and LCM ★

| Comments | ∞

In ProofWiki’s first proof, it has taken me some time to understand. I often write $d=\gcd(a,b)$, $a=a’d$, $b=b’d$ for some $a',b' \in \Z_{>0}$, and $n$ as any common multiple of $a$ and $b$. Then $n = q_1 a = q_2 b$ for some $q_1,q_2 \in \Z$. The letter $q$ connotes quotient. To show that $\lcm(a,b) \times \gcd(a,b) = ab$, it suffices to show that

\begin{gather} a \left | \frac{ab}{d} \right. \land b \left | \frac{ab}{d} \right. \label{eq:isLCM}\\ a|n \land b|n \implies \left.\frac{ab}{d}\right|n \label{eq:leastLCM} \end{gather}

Equations \eqref{eq:isLCM} and \eqref{eq:leastLCM} mean that “$ab/d$ is a LCM of $a$ and $b$” and “$ab/d$ is the least LCM of $a$ and $b$” respectively.

Equation \eqref{eq:isLCM} is very easy to check since $\displaystyle \frac{ab}{d} = a’b = ab’$.

By Bézout’s Identity, $ax+by=d$ for some $x,y \in \Z$.

Since what we want is $\displaystyle \frac{ab}{d} (\dots) = n$, we multiply both sides of the above equation by $\displaystyle \frac{n}{d}$.

\[ \begin{aligned} \frac{axn+byn}{d}=n\\ \frac{axbq_2+byaq_1}{d}=n\\ \left( \frac{ab}{d} \right) (xq_2+yq_1) = n \end{aligned} \]

Hence \eqref{eq:leastLCM} is proved.

Comments