\documentclass[a4paper,12pt]{article}

\begin{document}

\parindent=0pt

QUESTION

Let $a,b,c$ denote positive integers.

\begin{description}

\item[(i)]
Define the least common multiple, LCM$(a,b)$, and the highest
common factor, HCF$(a,b)$, of $a$ and $b$.

\item[(ii)]
Prove the formula

$$LCM(a,b)=\frac{ab}{HCF(a,b)}.$$

\item[(iii)]
If we define LCM$(a,b,c)$ and HCF$(a,b,c)$ in a similar manner
which of the following two formulae is correct?

$$LCM(a,b,c)=\frac{abc}{NCF(a,b,c)}$$

or

$$LCM(a,b,c)=\frac{abcHCF(a,b,c)}{HCF(a,b)HCF(a,c)HCF(b,c)}.$$

Prove it. (Hint: In (iii) you may assume that every positive
integer has a unique factorisation into prime powers.)

\end{description}



ANSWER

\begin{description}

\item[(i)]
LCM$(a,b)$ is the (positive) integer, $e$, such that $a|e$ ($a$
divides $e$) and $b|e$ and if $f$ is any other (positive) integer
multiple of both $a$ and $b$ then $e\leq f$.

HCF$(a,b)$ is the (positive) integer, $d$, such that $d|a$ and
$d|b$ and if $f$ is any other (positive) integer dividing both $a$
and $b$ then $f|d$ (or, as turns out to be equivilent, $f\leq d$.)

\item[(ii)]
If HCF$(a,b)=d$ there exist integers, $n$ and $m$, such that
$a===md,\ b=nd$. Hence $\frac{ab}{d}=mnd=mb=na$ which shows that
$\frac{ab}{d}$ is a common multiple. Now suppose that $f$ is
another common multiple. Since the
HCF$\left(\frac{a}{d},\frac{b}{d}\right)=1$ there exist integers,
$u$ and $v$, such that
$1=u\left(\frac{a}{d}\right)+v\left(\frac{b}{d}\right)$. Therefore

\begin{eqnarray*}
f&=&fu\left(\frac{a}{d}\right)+fv\left(\frac{b}{d}\right)=fum+fvn=\left(\frac{f}{nd}\right)umnd+\left(\frac{f}{md}\right)vmnd\\
&=&\left(\left(\frac{f}{b}\right)u+\left(\frac{f}{a}\right)u\right)mnd\geq
mnd
\end{eqnarray*}

because
$\left(\left(\frac{f}{b}\right)u+\left(\frac{f}{a}\right)v\right)$
is a n integer (necessarily positive) and so
$1\leq\left(\left(\frac{f}{b}\right)u+\left(\frac{f}{a}\right)v\right)$.

\item[(iii)]
The first formula is wrong, because if we set $a=b=c=2$ then
LCM(2,2,2)=2 but $\frac{2^3}{HCF(2,2,2)}=4$. Therefore we  must
prove the second formula.

Let $p_1,\ldots,p_k$ be distinct primes and write

\begin{eqnarray*}
a&=&p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k}\\
b&=&p_1^{\beta_1}p_2^{\beta_2}\ldots p_k^{\beta_k}\\
c&=&p_1^{\gamma_1}P_2^{\gamma_2}\ldots p_k^{\gamma_k}
\end{eqnarray*}

with the $0\leq\alpha_i,0\leq\beta_i,0\leq\gamma_i$ for all $1\leq
i\leq k$. With this notation we have

\begin{eqnarray*}
abc&=&\prod_{i=1}^kp_i^{\alpha_i+\beta_i+\gamma_i},\\
HCF(a,b)&=&\prod_{i=1}^kp_i^{min(\alpha_i,\beta_i)}\\
HCF(a,c)&=&\prod_{i=1}^kp_i^{min(\alpha_i,\gamma_i)},\\
HCF(b,c)&=&\prod_{i=1}^kp_i^{min(\beta_i,\gamma_i)},\\
HCF(a,b,c)&=&\prod_{i=1}^kp_i^{min(\alpha_i,\beta_i,\gamma_i)}.
\end{eqnarray*}

Hence the right hand expression is equal to

$$\frac{\prod_{i=1}^kp_i^{\alpha_i+\beta_i+\gamma_i}p_i^{min
(\alpha_i, \beta_i,\gamma_i)}}{\prod_{i=1}^kp_i^{min(\alpha_i,
\beta_i)}p_i^{min(\alpha_i,\gamma_i)}p_i^{min(\beta_i,
\gamma_i)}}.$$

If, for example, $\alpha_i\leq\beta_i\leq\gamma_i$ then

$$\alpha_i+\beta_i+\gamma_i+min(\alpha_i,\beta_i,\gamma_i)
-min(\alpha_i,\beta_i)-min(\alpha_i,\gamma_i)-min(\beta_i,\gamma_i)$$

is equal to
$\alpha_i+\beta_i+\gamma_i+\alpha_i-\alpha_i-\alpha_i-\beta_i
=\gamma_i=max(\alpha_i,\beta)i,\gamma_i)$. Therefore the right
hand expression equals

$$\prod_{i=1}^kp_i^{max(\alpha_i,\beta_i,\gamma_i)}=LCM(a,b,c)$$

as required.


\end{description}





\end{document}