Euclidean Algorithm (GCD)

All math tools

Calculate the Greatest Common Divisor (GCD) of two numbers using the step-by-step Euclidean algorithm.

Numbers

Number A

Number B

GCD Analysis

Greatest Common Divisor

Least Common Multiple23562

Simplified Ratio51 : 22

Iterative Process

1.1071=(2 × 462)+147

2.462=(3 × 147)+21

3.147=(7 × 21)+0Done!

About this calculator

The Euclidean Algorithm

The Euclidean algorithm is an efficient method for computing the greatest common divisor (GCD) of two integers. It is based on the principle that the GCD of two numbers also divides their difference. Specifically, GCD(a, b) = GCD(b, a mod b). Repeating this until the remainder is zero reveals the GCD.

💡

Pro Tips

The GCD of any two numbers is always at least 1.
If the GCD is 1, the numbers are said to be 'coprime' or 'relatively prime'.
The algorithm is used in modern cryptography, particularly in the RSA encryption algorithm.

Fun Facts

"Euclid's algorithm is one of the oldest numerical algorithms still in common use, appearing in Euclid's 'Elements' around 300 BC."
"The algorithm can be visualized by tiling a rectangle with squares."
"Lamé's theorem states that the number of steps in the algorithm is at most 5 times the number of digits in the smaller number."

Formula: a = q * b + r