Skip to main content

Greatest Common Divisor (GCD) and Least Common Multiple (LCM)

The Greatest Common Divisor (GCD) and Least Common Multiple (LCM) are fundamental algorithms in number theory used to determine the divisibility relationships between integers.

Greatest Common Divisor (GCD)​

Definition​

The GCD of two integers is the largest positive integer that divides both numbers without leaving a remainder. It is often used to simplify fractions and solve problems involving divisibility.

Algorithm​

The Euclidean algorithm is the most efficient method for computing the GCD. It works on the principle that the GCD of two numbers also divides their difference.

Steps:​

  1. Given two integers aa and bb :
    • If bb = 0, then GCD(a,b)GCD(a, b) = a
    • Otherwise, GCD(a,b)GCD(a, b) = GCD(b,a mod b).GCD(b,a \ mod \ b ).

Least Common Multiple (LCM)​

Definition​

The LCM of two integers is the smallest positive integer that is divisible by both numbers. It is often used in problems involving fractions and synchronization of cycles.

Relationship with GCD​

The LCM can be calculated using the GCD with the following formula:

LCM(a,b)LCM(a, b) = a×bGCD(a,b)\dfrac{a \times b}{\text{GCD}(a, b)}.

Implementations​

C++​

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int lcm(int a, int b) {
    return (a / gcd(a, b)) * b;
}

int main() {
    int a = 12, b = 15;
    cout << "GCD: " << gcd(a, b) << endl;
    cout << "LCM: " << lcm(a, b) << endl;
    return 0;
}

Java​

public class GCDLCM {
    public static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    public static int lcm(int a, int b) {
        return (a / gcd(a, b)) * b;
    }

    public static void main(String[] args) {
        int a = 12, b = 15;
        System.out.println("GCD: " + gcd(a, b));
        System.out.println("LCM: " + lcm(a, b));
    }
}

Python​

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def lcm(a, b):
    return abs(a * b) // gcd(a, b)

a = 12
b = 15
print("GCD:", gcd(a, b))
print("LCM:", lcm(a, b))

Pseudo Code​

function gcd(a, b):
    while b != 0:
        temp = b
        b = a mod b
        a = temp
    return a

function lcm(a, b):
    return (a / gcd(a, b)) * b

Time Complexity​

  • Best Case: O(1)
  • Average Case: O(log(min(a, b)))
  • Worst Case: O(log(min(a, b))) where a and b are the two integers.

Space Complexity​

  • O(1) for the iterative implementations since they only require a few variables for computation.

Explanation​

The Euclidean algorithm effectively computes the Greatest Common Divisor in logarithmic time O(log(min(a, b))) by continually replacing the larger number by the remainder of the two numbers. The Least Common Multiple relies directly on the GCD and takes the same time. The space complexity is constant O(1) because the iterative version uses minimal auxiliary memory.

Conclusion​

The Greatest Common Divisor (GCD) and Least Common Multiple (LCM) are essential algorithms in number theory that help in understanding the divisibility of integers. Their efficient computation using the Euclidean algorithm and the relationship between GCD and LCM makes them powerful tools in both theoretical and practical applications.