Question

The HCF of 65 and 117 is expressible in the form of 65m + 117n. Find the value of m and n. Also find the LCM of 65 and 117 using prime factorization.

Answer 1

Hint:
1) Euclid’s Division Algorithm: If a and b are positive integers such that a = bq + r, then every common divisor of a and b is a common divisor of b and r, and vice-versa. This algorithm can be used to readily find the HCF of two numbers.
2) Prime Numbers: The numbers which have exactly two factors, i.e. they are not divisible by any other number except for 1 and themselves, are called prime numbers. All other numbers are called composite numbers. 1 is neither prime (it has exactly one factor!), nor composite.

Complete step by step solution:
Finding the value of m and n:
Euclid’s Division Algorithm:
Step 1: We can write 117 = 65 × 1 + 52, and by comparing it with a = bq + r, we can say that here a = 117, b = 65, q = 1 and r = 52.
Step 2: Using the Euclid’s Division Algorithm, if a number x divides both a = 117 and b = 65, then it must also divide both b = 65 and r = 52. Using the same algorithm again, 65 = 52 × 1 + 13. Since, x divides both 65 and 52, it must divide both 52 and 13.
Step 3: Repeating the algorithm further, 52 = 13 × 4 + 0. So, x must also divide both 13 and 0, which means that x = 13.
Finally, to express this HCF x = 13 in terms of a and b, let us go backwards from the last step where we had b:
Using (Step 2): 13 = 65 - 52.
Using (Step 1): 13 = 65 - (117 - 65) = 65 × 2 + 117 × (-1) = 65m + 117n.
∴ The value of m is 2 and the value of n is -1.
Finding the LCM:
Let us write 65 and 117 as a product of prime numbers.
65 = 5 × 13.
 $117={{3}^{2}}\times 13$ .
Now, the LCM is the least number which is a multiple of all of them. Therefore, it must have at least the maximum power of all the prime numbers present in it.

∴ The LCM is ${{3}^{2}}\times 5\times 13$ .

Note:
1) The LCM can also be found out by using the relation: LCM × HCF = Product of the two numbers. This relation works for only two numbers. If LCM of more than two numbers have to be found, then prime factorization is the best approach.
2) The Euclid’s algorithm can also be used for polynomials.