Find the greatest common divisor (GCD) of two or more integers using the Euclidean algorithm.
📖 Euclidean AlgorithmFill in the fields on the left with your information, then press Calculate to see your result instantly. No sign-up required, and no data is sent anywhere — everything is calculated right in your browser.
The greatest common divisor (GCD, or HCF) calculator finds the largest integer that divides all the entered numbers without a remainder, using the famous and computationally very efficient "Euclidean algorithm," even for large numbers. The algorithm works on a simple, repeated principle: to find the GCD of two numbers a and b, a is divided by b and the remainder is kept, then the remainder replaces a and b replaces the previous remainder, and the process repeats until the remainder becomes zero — at which point the last non-zero remainder is the greatest common divisor. When more than two numbers are entered, the calculator computes the GCD of the first two numbers, then the GCD of that result with the third number, and repeats until all entered numbers are included. GCD is widely used in simplifying fractions, equal-distribution problems, and cryptography and computer science. The Euclidean algorithm's efficiency comes from how quickly the numbers involved shrink at each step, allowing it to find the GCD of even very large numbers in only a handful of division steps.
Finding the greatest common divisor of two numbers by listing every factor of each and comparing the lists works fine for small numbers, but becomes impractical almost immediately as the numbers grow larger — which is exactly the problem the Euclidean algorithm, one of the oldest algorithms in recorded mathematical history, was designed to solve efficiently.
The algorithm's core insight is elegantly simple: the greatest common divisor of two numbers does not change if the larger number is replaced by its remainder after dividing by the smaller number. Repeating this replacement — divide, keep the remainder, replace the larger number with that remainder — shrinks the numbers involved rapidly at each step, until eventually one number divides the other with a remainder of exactly zero. At that point, the last nonzero remainder found along the way is the greatest common divisor of the original two numbers.
This method is dramatically faster than factoring both numbers directly, especially for large numbers, because it never actually requires finding the individual prime factors of either number — an operation that becomes computationally very expensive as numbers grow into the hundreds of digits used in modern cryptography. The Euclidean algorithm, by contrast, generally reaches its answer in a very small number of steps even for enormous numbers, which is precisely why it remains the standard method used inside real computer software today, over two thousand years after it was first documented.
Extending the algorithm to more than two numbers follows a straightforward pattern: the GCD of three or more numbers can always be found by first finding the GCD of any two of them, then finding the GCD of that result together with the next number, and repeating until every number has been included — a direct consequence of the mathematical fact that GCD is associative in this way.
Beyond its most familiar use in simplifying fractions to their lowest terms, GCD calculations underpin fair-division problems (splitting a group of items into the largest possible equal-sized batches), scheduling problems (finding when multiple repeating events last aligned), and modern public-key cryptography, where GCD-related computations (via the related extended Euclidean algorithm) are a core building block of widely used encryption schemes.
GCD stands for Greatest Common Divisor — the largest positive integer that divides every one of the given numbers without leaving a remainder.
You can enter two or more integers separated by commas, and the calculator will find the GCD shared by all of them.
No, the greatest common divisor is the same no matter what order you list the numbers in.