Loading...
Loading...
Loading calculator...
Calculate the Greatest Common Divisor (GCD) and Least Common Multiple (LCM) of two or more numbers. See step-by-step solutions using the Euclidean algorithm and prime factorization.
Separate numbers with commas, spaces, or new lines. Only positive integers are accepted.
Please enter at least two positive integers
This calculator provides accurate GCD and LCM calculations for educational and practical purposes.
Results are computed using standard mathematical algorithms including the Euclidean method and prime factorization.
The Greatest Common Divisor (GCD), also known as the Highest Common Factor (HCF), is the largest positive integer that divides two or more numbers without leaving a remainder. The Least Common Multiple (LCM) is the smallest positive integer that is divisible by all the given numbers. These concepts are fundamental in mathematics and have practical applications in simplifying fractions, finding common denominators, and solving problems involving periodic events.
There are two main methods to calculate GCD and LCM:
Euclidean Algorithm: An efficient method that repeatedly applies the division algorithm. For GCD(a,b), divide a by b, then divide b by the remainder, continuing until the remainder is 0. The last non-zero remainder is the GCD.
Prime Factorization Method: Factor each number into prime factors. For GCD, multiply the common prime factors with the lowest exponents. For LCM, multiply all prime factors with the highest exponents.
GCD(a, b) = GCD(b, a mod b) until remainder = 0Example: GCD(48, 18) = GCD(18, 12) = GCD(12, 6) = GCD(6, 0) = 6
LCM(a, b) = |a x b| / GCD(a, b)Example: LCM(48, 18) = (48 x 18) / 6 = 864 / 6 = 144
GCD (Greatest Common Divisor) is the largest number that divides all given numbers evenly. LCM (Least Common Multiple) is the smallest number that all given numbers divide into evenly. For example, for 12 and 18: GCD = 6 (both are divisible by 6) and LCM = 36 (smallest number divisible by both 12 and 18).
Numbers are coprime (or relatively prime) when their GCD equals 1, meaning they share no common factors other than 1. For example, 8 and 15 are coprime because GCD(8, 15) = 1, even though neither is a prime number.
To simplify a fraction, divide both the numerator and denominator by their GCD. For example, to simplify 48/18, find GCD(48, 18) = 6, then divide: 48/6 = 8 and 18/6 = 3, giving the simplified fraction 8/3.
LCM is used when finding common denominators for adding fractions, scheduling recurring events (like when two buses with different schedules will arrive together), and in problems involving cycles or periods.
The Euclidean algorithm is an efficient method to find the GCD of two numbers. It works by repeatedly replacing the larger number with the remainder when the larger is divided by the smaller, until one number becomes 0. The other number at that point is the GCD.
Yes! This calculator handles multiple numbers. For GCD, find GCD of the first two numbers, then find GCD of that result with the third number, and so on. The same approach works for LCM.
Prime factorization is expressing a number as a product of prime numbers. For example, 48 = 2^4 x 3 and 18 = 2 x 3^2. This helps find GCD (use lowest exponents of common primes) and LCM (use highest exponents of all primes).
Every integer divides 0 (since 0 = 0 x any integer), so all factors of 'a' are also common factors with 0. Therefore, the greatest common divisor of any number 'a' and 0 is 'a' itself.