Find the prime factorisation of $6500$ and $1120$, and write down, in factorised form, $\gcd(6500, 1120)$ and $\operatorname{lcm}(6500, 1120)$.

Question

(i) Find the prime factorisation of $6500$, and of $1120$.

What is the typical way to go about this? Just using common divisibility rules? That's what I did. I'm not sure if there's a more structured way that I should be doing this, since it could be more difficult depending on the number? The above seem to be easy cases.

$65 \times 100 = 6500$

$13 \times 5 \times 25 \times 4 = 6500$

$13 \times 5 \times 5^2 \times 2^2 = 6500$

$13 \times 5^3 \times 2^2 = 6500$

$1120 = 112 \times 10$

$= 66 \times 2 \times 5 \times 2$

$= 6 \times 11 \times 2^2 \times 5$

$= 3 \times 11 \times 2^3 \times 5$

(ii) Hence write down, in factorised form, $gcd(6500, 1120)$ and $lcm(6500, 1120)$.

For GCD we just selected the highest powers of the numbers that are common to both? So it would be $\gcd(6500, 1120) = 5^3 \times 13 \times 2^3$?

And I think for LCM we take the lowest powers of each number? So it would be $\operatorname{lcm}(6500, 1120) = 5 \times 2^2$?

Thanks for any help.

Answer 1

You made a slight error in the prime factorisations.

$$6500=2^2\cdot5^3\cdot13\\1120=2^5\cdot5\cdot7$$ Hence we have $$\gcd(6500,1120)=2^2\cdot5\\\operatorname{lcm}(6500,1120)=2^5\cdot5^3\cdot7\cdot13$$ The key is gcd:min(powers) and lcm:max(powers)

Answer 2

One can do the gcd without factoring first. Oh, $$ \operatorname{lcm}(a,b) = \frac{ab}{\gcd(a,b)} $$

$$ \frac{ 6500 }{ 1120 } = 5 + \frac{ 900 }{ 1120 } $$ $$ \frac{ 1120 }{ 900 } = 1 + \frac{ 220 }{ 900 } $$ $$ \frac{ 900 }{ 220 } = 4 + \frac{ 20 }{ 220 } $$ $$ \frac{ 220 }{ 20 } = 11 + \frac{ 0 }{ 20 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccccc} & & 5 & & 1 & & 4 & & 11 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 5 }{ 1 } & & \frac{ 6 }{ 1 } & & \frac{ 29 }{ 5 } & & \frac{ 325 }{ 56 } \end{array} $$ $$ $$ $$ 325 \cdot 5 - 56 \cdot 29 = 1 $$

$$ \gcd( 6500, 1120 ) = 20 $$
$$ 6500 \cdot 5 - 1120 \cdot 29 = 20 $$