Find the greatest common divisor (GCD) of two numbers
The Euclidean algorithm finds the GCD by repeatedly dividing the larger number by the smaller and taking the remainder. The process continues until the remainder is zero -- the last non-zero remainder is the GCD. This ancient method is remarkably efficient even for very large numbers.
The GCD is fundamental to simplifying fractions, solving Diophantine equations, and many areas of number theory. It is also used in cryptography (RSA algorithm), computer science, and engineering whenever you need to find common factors between quantities.
The GCD is the largest number that divides both inputs evenly. The calculator also shows the LCM (Least Common Multiple), which equals the product of the two numbers divided by their GCD. Together, GCD and LCM describe the complete factor relationship between two numbers.
Use the GCD to reduce fractions to their simplest form by dividing both numerator and denominator by it. Remember that the GCD of any number and zero is the number itself. For multiple numbers, find the GCD of the first two, then find the GCD of that result with the next number.
The Greatest Common Divisor (GCD), also known as the Greatest Common Factor (GCF) or Highest Common Factor (HCF), is the largest positive integer that divides two or more numbers without leaving a remainder. For example, the GCD of 12 and 18 is 6 because 6 is the largest number that divides both evenly.
The most efficient method is the Euclidean algorithm: divide the larger number by the smaller, then replace the larger number with the remainder and repeat until the remainder is 0. The last non-zero remainder is the GCD. For example, GCD(48, 18): 48 / 18 = 2 remainder 12, then 18 / 12 = 1 remainder 6, then 12 / 6 = 2 remainder 0, so GCD = 6.
The GCD (Greatest Common Divisor) is the largest number that divides both numbers evenly, while the LCM (Least Common Multiple) is the smallest number that both numbers divide into evenly. They are related by the formula: GCD(a, b) x LCM(a, b) = a x b. For example, for 12 and 18, GCD = 6 and LCM = 36, and 6 x 36 = 12 x 18 = 216.