5. Lowest common multiple

VC2M5N10: level 5: Follow a mathematical algorithm involving branching and repetition (iteration); create and use algorithms involving a sequence of steps and decisions and digital tools to experiment with factors, multiples and divisibility; identify, interpret and describe emerging patterns

  • identifying lowest common multiples and highest common factors of pairs or triples of natural numbers; for example, the lowest common multiple of {6, 9} is 18, and the highest common factor is 3, and the lowest common multiple of {3, 4, 5} is 60 and the highest common factor is 1

5.1. LCM

The lowest common multiple, LCM, of two or more numbers is the smallest positive integer that is divisible by each of the numbers.
For example, the LCM of 4 and 6 is 12, because 12 is the smallest positive integer that is divisible by both 4 and 6.

5.2. LCM of 2 numbers using HCF

The Pseudocode to find LCM of two numbers has the steps to find the lowest common multiple of two numbers:
FUNCTION HCF_SUB(a, b)
    WHILE a ≠ b DO
        IF a > b THEN
            a ← a - b
        ELSE
            b ← b - a
        ENDIF
    ENDWHILE
    RETURN a
ENDFUNCTION

FUNCTION LCM(a, b)
    hcf ← HCF_SUB(a, b)
    lcm ← (a * b) ÷ hcf
    RETURN lcm
ENDFUNCTION

BEGIN
    a ← 48
    b ← 18
    result ← LCM(a, b)
    PRINT "LCM of ", a, " and ", b, " is ", result
END
The Python code below implements this algorithm.
 1def hcf_sub(a, b):
 2    """Find HCF using subtraction-based Euclidean algorithm."""
 3    while a != b:
 4        if a > b:
 5            a -= b
 6        else:
 7            b -= a
 8    return a
 9
10def lcm(a, b):
11    """Find LCM using HCF."""
12    hcf = hcf_sub(a, b)
13    return (a * b) // hcf
14
15def main():
16    num1 = int(input("Enter the first number: "))
17    num2 = int(input("Enter the second number: "))
18
19    result = lcm(num1, num2)
20    print(f"LCM({num1}, {num2}) = {result}")
21
22if __name__ == "__main__":
23    main()
24
25
26'''
27Enter the first number: 12
28Enter the second number: 18
29LCM(12, 18) = 36
30'''

5.3. LCM of multiple numbers

The pseudocode to find LCM of multiple numbers has the steps to find the lowest common multiple of multiple numbers:
FUNCTION HCF_SUB(a, b)
    WHILE a ≠ b DO
        IF a > b THEN
            a ← a - b
        ELSE
            b ← b - a
        ENDIF
    ENDWHILE
    RETURN a
ENDFUNCTION

FUNCTION LCM(a, b)
    hcf ← HCF_SUB(a, b)
    lcm ← (a * b) ÷ hcf
    RETURN lcm
ENDFUNCTION

FUNCTION LCM_LIST(numbers)
    result ← numbers[0]
    FOR i ← 1 TO LENGTH(numbers) - 1 DO
        result ← LCM(result, numbers[i])
    ENDFOR
    RETURN result
ENDFUNCTION

BEGIN
    numbers ← [12, 18, 30]
    result ← LCM_LIST(numbers)
    PRINT "LCM of ", numbers, " is ", result
END
The code below handles multiple positive integers.
 1def hcf_sub(a, b):
 2    """Find HCF using subtraction-based Euclidean algorithm."""
 3    while a != b:
 4        if a > b:
 5            a -= b
 6        else:
 7            b -= a
 8    return a
 9
10def lcm(a, b):
11    """Find LCM using HCF."""
12    hcf = hcf_sub(a, b)
13    return (a * b) // hcf
14
15def lcm_list(numbers):
16    """Find LCM of a list of numbers."""
17    result = numbers[0]
18    for n in numbers[1:]:
19        result = lcm(result, n)
20    return result
21
22def main():
23    # Prompt the user for a list of numbers separated by spaces
24    nums = list(map(int, input("Enter numbers separated by spaces: ").split()))
25
26    result = lcm_list(nums)
27    print(f"LCM({nums}) = {result}")
28
29if __name__ == "__main__":
30    main()

5.4. LCM using gcd

The Python math.gcd() function is a built-in function that returns the greatest common divisor (GCD) of two or more integers.
The GCD of two or more numbers is the largest positive integer that divides each of the numbers without leaving a remainder.
Use the formula lcm = (a * b) // gcd(a, b)
 1# Import the math module to use the gcd function
 2import math
 3
 4# Define a function to find the lcm of two numbers
 5def lcm(a, b):
 6    # Use the formula lcm = (a * b) // gcd(a, b)
 7    return (a * b) // math.gcd(a, b)
 8
 9# Prompt the user to enter two numbers
10num1 = int(input("Enter the first number: "))
11num2 = int(input("Enter the second number: "))
12
13# Call the lcm function and print the result
14print("The LCM of", num1, "and", num2, "is", lcm(num1, num2))
15
16
17a = 48
18b = 18
19# Display the LCM
20print(f'LCM({a}, {b}) is {lcm(a , b)}.')
21

5.5. LCM of multiple numbers using gcd

The code below handles multiple positive integers.
 1# Import the math module to use the gcd function
 2import math
 3
 4# Define a function to find the lcm of any number of numbers
 5def lcm(*args):
 6    # Use the formula lcm(a, b, c) = lcm(lcm(a, b), c)
 7    result = args[0]
 8    for num in args[1:]:
 9        result = (result * num) // math.gcd(result, num)
10    return result
11
12# Prompt the user to enter any number of numbers separated by commas
13nums = input("Enter the numbers separated by spaces: ")
14nums = [int(num) for num in nums.split(",")]
15
16# Display the LCM
17print(f'The LCM of {", ".join(str(num) for num in nums)} is {lcm(*nums)}.')
18
19'''Enter the numbers separated by spaces: 12 15 16
20The LCM of 12, 15, 16 is 240.'''
21