LCM and HCF
Factors and multiples:
- All numbers that divide a number completely, i.e., without leaving any remainder, are called factors of that number.
- For example, 24 is completely divisible by 1, 2, 3, 4, 6, 8, 12, 24. Each of these numbers is called a factor of 24 and 24 is called a multiple of each of these numbers.
HCF or GCD :
The largest number that divides two or more numbers is the highest common factor (HCF) for those numbers.
For example, consider the numbers 30 (2 x 3 x 5), 36 (2 x 2 x 3 x 3), 42 (2 x 3 x 7), 45 (3 x 3 x 5). 3 is the largest number that divides each of these numbers, and hence, is the HCF for these numbers.
To find the HCF of two or more numbers, express each number as their prime factorization. The product of the minimum powers of common prime terms in both of the prime factorization gives the HCF. This is the method we illustrated in the above step.
Also, for finding the HCF of two numbers, we can also proceed by long division method. We divide the larger number by the smaller number (divisor). Now, we divide the divisor by the remainder obtained in the previous stage. We repeat the same procedure until we get zero as the remainder. At that stage, the last divisor would be the required HCF.
GCD Application : Tiling a rectangle with squares
Naive approach:
1const GCD = (a, b) => {
2 //WKT., Max GCD can be min of two given numbers, so begin with min of a & b.
3 let res = Math.min(a, b);
4 while (res > 0) {
5 if (a % res == 0 && b % res == 0) break;
6 res--;
7 }
8 return res;
9}; //TC : O(min(a,b))
Euclidian Algorithm
The Euclidean algorithm is based on the below facts:
GCD doesn’t change, if we subtract the smaller number from larger (we reduce larger number). So if we keep subtracting repeatedly the larger of two, we end up with GCD.
If b is smaller than a. gcd(a,b) = gcd(a-b)
- Let g be the gcd of a,b . where a = gx, b = gy & gcd(x,y) = 1
- (a-b) = gcd(x-y) We need to show that b and (a-b) also have gcd = 1
Approach 2 (Euclidian algorithm):
1const GCD = (a, b) => {
2 //stop when a & b are equal and return either of them
3 while (a != b) {
4 if (a > b) a = a - b;
5 else b = b - a;
6 }
7 return a; // or return b;
8};
- Now instead of doing subtraction, if we divide the smaller number, the algorithm stops when the remainder is found to be 0
Optimized euclidian algorithm:
1const GCD = (a, b) => {
2 if (b == 0) return a;
3 else return GCD(b, a % b); //TC :O(log(min(a,b)))
4};
LCM :
LCM is a smallest number other than 0 & 1 that is a multiple of each number.
LCM of 4 & 6
- Multiples of 4: 4,8,12,16,20,24,28,32…
- Multiples of 6: 6,12,18,24,30,36,…
- common multiples: 12,24,36,48 => Least common multiple = 12
The lowest number which is exactly divisible by each of the given numbers is called the least common multiple of those numbers. For example, consider the numbers 3, 31 and 62 (2 x 31). The LCM of these numbers would be 2 x 3 x 31 = 186.
To find LCM of given numbers: express each number as their prime factorization. The product of highest power of the prime numbers that appear in the prime factorization of any of the numbers gives us the LCM.
consider the numbers 2, 3, 4 (2 x 2), 5, 6 (2 x 3). The LCM of these numbers is 2 x 2 x 3 x 5 = 60. The highest power of 2 comes from prime factorization of 4, the highest power of 3 comes from prime factorization of 3 and prime factorization of 6 and the highest power of 5 comes from prime factorization of 5.
Naive approach:
1const lcm = (a, b) => {
2 //LCM would >= larger of 2 numbers
3 let res = Math.max(a, b);
4 while (res) {
5 if (res % a == 0 && res % b == 0) return res;
6 res++;
7 }
8 return res;
9}; // TC: O(ab-max(a,b))
Efficient soln:
a* b = gcd(a,b) * lcm(a,b)
- lcm(a,b) = (a*b) / gcd(a*b)
1const lcm = (a, b) => {
2 return (a * b) / GCD(a, b);
3}; //TC: O(log(min(a,b)))
Important properties of LCM and HCF:
- For two numbers say, ‘a’ and ‘b’, LCM x HCF = a x b.
- HCF of co-primes = 1.
- For two fractions,
- HCF = HCF (Numerators) / LCM (Denominators)
- LCM = LCM (Numerators) / HCF (Denominators)