Euclidean Algorithm
Compute the greatest common divisor (GCD) of two integers using the Euclidean algorithm with step-by-step division. Free online number theory calculator.
About This Calculator
The Euclidean Algorithm Calculator computes the greatest common divisor (GCD) of two positive integers using the ancient and efficient Euclidean method. Named after the Greek mathematician Euclid, this algorithm is one of the oldest numerical algorithms still in widespread use, dating back to approximately 300 BCE.
The calculator shows every step of the division process: for each iteration, it displays the current dividend (a), divisor (b), quotient, and remainder. At the end, the final GCD is highlighted, and the LCM is also computed automatically using the formula LCM(a, b) = |a x b| ÷ GCD(a, b).
How it works: Given two numbers a and b, the algorithm repeatedly divides a by b and replaces a with b and b with the remainder. When the remainder becomes zero, the last non-zero b is the GCD. For example, for a = 56 and b = 98: 98 ÷ 56 -> remainder 42, 56 ÷ 42 -> remainder 14, 42 ÷ 14 -> remainder 0, so GCD = 14.
Applications: GCD computation via the Euclidean algorithm is fundamental in cryptography (RSA), fraction arithmetic, modular arithmetic, computer algebra systems, and engineering design (gear ratios, signal processing).
Frequently Asked Questions
What is the Euclidean Algorithm?
The Euclidean algorithm is an ancient method for computing the greatest common divisor (GCD) of two integers. It works by repeatedly replacing the larger number by the remainder of dividing the larger by the smaller until the remainder is zero -- the last non-zero remainder is the GCD.
How do you find GCD using the Euclidean Algorithm?
To find GCD(a, b): (1) Divide a by b, getting quotient q and remainder r. (2) Replace a with b and b with r. (3) Repeat until r = 0. The last non-zero b is the GCD. For example, GCD(56, 98): 98 ÷ 56 = 1 rem 42, 56 ÷ 42 = 1 rem 14, 42 ÷ 14 = 3 rem 0 -> GCD = 14.
What is the GCD used for in real life?
GCD is used in fraction simplification (reducing fractions to lowest terms), cryptography (RSA encryption relies on GCD for key generation), modular arithmetic, gear ratio calculations in engineering, and computer science algorithms like checksums and hash functions.
Can the Euclidean Algorithm handle negative numbers?
The standard Euclidean algorithm works with positive integers. For negative inputs, the GCD is defined as the GCD of their absolute values. Most calculators, including this one, automatically take the absolute value of negative inputs.
What is the time complexity of the Euclidean Algorithm?
The Euclidean algorithm runs in O(log min(a, b)) steps, making it extremely efficient even for very large numbers. In the worst case (consecutive Fibonacci numbers), it takes about 5 log10(min) divisions. This logarithmic complexity is why it is widely used in cryptography.
How is the LCM related to the GCD?
The least common multiple (LCM) of a and b is directly related: LCM(a, b) = |a x b| ÷ GCD(a, b). Once the Euclidean algorithm finds the GCD, the LCM can be computed in constant time. This calculator displays both GCD and LCM.
Is the Euclidean Algorithm taught in schools globally?
Yes, the Euclidean algorithm is a standard topic in mathematics curricula across India (CBSE/ICSE Class 10), the US (Common Core standards in middle school), and the UK (GCSE and A-Level mathematics). It forms a foundation for number theory and cryptography.