Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I was reading a text book and came across the following approach to find the LCM and HCF of rational numbers/fractions:

  • LCM of fractions = LCM of numerators/HCF of denominators
  • HCF of fractions = HCF of numerators/LCM of denominators

Can someone please help me understand why the above formula holds true or how the above is logically deduced?

Thanks in advance!

share|improve this question
    
I think you start with the observation that for integers $a, b, k$ we have $\gcd(ka, kb) = k \gcd(a, b)$ and $\text{lcm}(ka, kb) = k \text{lcm}(a, b)$ and then just extend this to rational $k$. You should get the same result as the above. –  Qiaochu Yuan Jun 11 '11 at 21:24

2 Answers 2

Notation: $\text{HCF}$ is denoted below as $\text{gcd}$.

Assume you have two fractions $\frac{a}{b},\frac{c}{d}$ reduced to lowest terms. Let

$$\begin{eqnarray*} a &=&\underset{i}{\prod } p_{i}^{e_{i}(a)},\qquad b=\underset{i}{\prod } p_{i}^{e_{i}(b)}, \\ c &=&\underset{i}{\prod } p_{i}^{e_{i}(c)},\qquad d=\underset{i}{\prod } p_{i}^{e_{i}(d)}. \end{eqnarray*}$$

be the prime factorizations of the integers $a,b,c$ and $d$. Then

$$\frac{\underset{i}{\prod }\ p_{i}^{\max \left( e_{i}(a),e_{i}(c)\right) }}{% \prod_{i}\ p_{i}^{\min \left( e_{i}(b),e_{i}(d)\right) }}$$

is a fraction which is a common multiple of $\frac{a}{b},\frac{c}{d}$. It is the least one because by the properties of the $\text{lcm}$ and $\gcd $ of two integers, $\prod_{i}\ p_{i}^{\max \left( e_{i}(a),e_{i}(c)\right) }$ is the least common multiple of the numerators and $\prod_{i}\ p_{i}^{\min \left( e_{i}(b),e_{i}(d)\right) }$ is the greatest common divisor of the denominators. Hence

$$\begin{eqnarray*} \text{lcm}\left( \frac{a}{b},\frac{c}{d}\right) &=&\text{lcm}\left( \frac{{\prod_{i}\ p_{i}^{e_{i}(a)}}}{\prod_{i}\ p_{i}^{e_{i}(b)}},\frac{% \prod_{i}\ p_{i}^{e_{i}(c)}}{\prod_{i}\ p_{i}^{e_{i}(d)}}\right)=\frac{\prod_{i}\ p_{i}^{\max \left( e_{i}(a),e_{i}(c)\right) }}{% \prod_{i}\ p_{i}^{\min \left( e_{i}(b),e_{i}(d)\right) }}=\frac{\text{lcm}(a,c)}{\gcd (b,d)}.\quad(1) \end{eqnarray*}$$

Similarly

$$\begin{eqnarray*} \gcd \left( \frac{a}{b},\frac{c}{d}\right) =\gcd \left( \frac{{\prod_{i}\ p_{i}^{e_{i}(a)}}}{\prod_{i}p_{i}^{e_{i}(b)}},\frac{% \prod_{i\ }p_{i}^{e_{i}(c)}}{\prod_{i}p_{i}^{e_{i}(d)}}\right) =\frac{\prod_{i}\ p_{i}^{\min \left( e_{i}(a),e_{i}(c)\right) }}{% \prod_{i}\ p_{i}^{\max \left( e_{i}(b),e_{i}(d)\right) }} =\frac{\gcd (a,c)}{\text{lcm}(b,d)}.\quad(2) \end{eqnarray*}$$

The repeated application of these relations generalizes the result to any finite number of fractions.

share|improve this answer

Below is a proof that works in any GCD domain, using the universal definitions of GCD, LCM. These ideas go back to Euclid, who defined the greatest common measure of line segments. Nowadays this can also be viewed in terms of fractional ideals or Krull's $v$-ideals.

Theorem $\rm\quad\ \ (a/b,A/B)\: =\: (a,A)/[b,B]\ \ $ if $\rm\ \ (a,b) = 1 = (A,B)$
Proof
$\rm\begin{eqnarray} &\rm c &|&\rm a/b,A/B \\ \quad\iff&\rm Bbc &|&\rm aB,Ab \\ \iff&\rm Bbc &|&\rm (aB,Ab) \\ \iff&\rm Bbc &|&\rm (aB, (A,aB)(b,aB))\ \ &\rm by\quad (x,yz) = (x,y(z,x)),\ \ see\ [2] \\ \iff&\rm Bbc &|&\rm (aB, (A,a) (b,B))\ \ &\rm by\quad (a,b) = 1 = (A,B) \\ \iff&\rm Bbc &|&\rm (a,A) (b,B)\ \ &\rm by\quad (A,a)\ |\ a,\ (b,B)\ |\ B \\ \iff&\rm c &|&\rm (a,A)/[b,B]\ \ &\rm by\quad (b,B)\:[b,B] = bB, \ \ see\ [3] \end{eqnarray}$

Here are links to proofs of the gcd laws used: law [2] and law [3].

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.