Last verified · v1.0

Calculator · math

Greatest Common Divisor (Gcd) Calculator

Calculate the greatest common divisor of two positive integers instantly using the Euclidean algorithm. Enter any two numbers to get accurate GCD results.

FreeInstantNo signupOpen source

Inputs

First Number

Second Number

Greatest Common Divisor

—

Get a plain-English breakdown of your result with practical next steps.

Greatest Common Divisor—

The formula

How the
result is
computed.

What Is the Greatest Common Divisor?

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 integers exactly, leaving no remainder. For example, the GCD of 48 and 18 is 6, since 6 is the largest number that divides both values evenly. The greatest common denominator calculator on this page computes this value instantly for any two positive integers.

The Euclidean Algorithm: Formula and Derivation

The most efficient method for computing the GCD is the Euclidean algorithm, a technique dating to Euclid's Elements (circa 300 BCE). The recursive formula is defined as follows:

gcd(a, b) = a when b = 0 (base case)
gcd(a, b) = gcd(b, a mod b) for all other cases

At each step the algorithm replaces the larger number with the remainder of dividing the two inputs. This process repeats until the remainder equals zero — the last non-zero remainder is the GCD. According to Carnegie Mellon University's number theory course, the Euclidean algorithm is guaranteed to terminate and produces the correct GCD for every pair of positive integers. The number of steps is proportional to the number of digits in the inputs, making it highly efficient even for very large values.

Variable Definitions

First Number (num1): Any positive integer. This value serves as the dividend in the initial division step. The algorithm processes num1 alongside num2 to find their shared divisor.
Second Number (num2): Any positive integer. This value serves as the divisor. When num2 equals zero, the algorithm terminates immediately and returns num1 as the GCD.

Step-by-Step Worked Example

Find the GCD of 252 and 105 using the Euclidean algorithm:

252 divided by 105 gives remainder 42 — so gcd(252, 105) = gcd(105, 42)
105 divided by 42 gives remainder 21 — so gcd(105, 42) = gcd(42, 21)
42 divided by 21 gives remainder 0 — algorithm terminates, returning 21

Therefore, gcd(252, 105) = 21. Both 252 and 105 divide evenly by 21, and no integer larger than 21 divides both.

Alternative Method: Prime Factorization

The GCD can also be found by comparing prime factorizations. For 48 and 36: 48 = 2⁴ × 3 and 36 = 2² × 3². Taking the lowest power of each shared prime gives 2² × 3 = 12. While mathematically sound, this approach becomes impractical for large numbers. The University of Nebraska PreCalculus textbook confirms that the Euclidean algorithm is the standard computational method, preferred for its reliability and speed across all integer sizes.

Real-World Applications

Simplifying fractions: Divide numerator and denominator by their GCD. The fraction 36/48 simplifies to 3/4 because gcd(36, 48) = 12.
Gear ratio engineering: Engineers reduce gear ratios to their simplest integer form using the GCD of tooth counts on meshing gears.
Cryptography: RSA encryption relies on GCD computations to verify that key components are coprime, a prerequisite for secure key generation.
Tile and floor layout: The GCD of two room dimensions in whole units gives the side length of the largest square tile that covers the floor without cutting any tile.
Scheduling and cycles: The GCD of two cycle lengths reveals the longest repeating interval shared by both cycles, useful in manufacturing and task scheduling.

Key Mathematical Properties

Commutative: gcd(a, b) = gcd(b, a) — input order does not affect the result
Associative: gcd(a, gcd(b, c)) = gcd(gcd(a, b), c) — enables chaining for three or more numbers
Identity element: gcd(a, 0) = a for any positive integer a
Coprime condition: When gcd(a, b) = 1, the two integers share no common factors other than 1 and are termed coprime or relatively prime

Reference

Frequently asked questions

What is the difference between greatest common divisor and greatest common denominator?

The greatest common divisor (GCD) and greatest common denominator refer to the same mathematical concept — the largest positive integer that divides two numbers without leaving a remainder. 'Greatest common denominator' is a widely used informal term, while GCD or GCF (greatest common factor) are the mathematically precise designations. Both terms appear in textbooks and calculators interchangeably, so either phrasing leads to the same calculation and result.

How does the Euclidean algorithm calculate the GCD step by step?

The Euclidean algorithm works by repeatedly dividing the larger number by the smaller and replacing the larger with the remainder. For example, to find gcd(98, 56): 98 mod 56 = 42, then 56 mod 42 = 14, then 42 mod 14 = 0, so the GCD is 14. The process terminates when the remainder reaches zero, returning the last non-zero divisor. The algorithm runs in O(log min(a, b)) time, making it efficient for arbitrarily large integers.

What is gcd(0, n) and why does it matter for the calculator?

By mathematical convention, gcd(0, n) = n for any positive integer n. Because every positive integer divides 0 evenly, the greatest such divisor is n itself. This base case is what terminates the Euclidean algorithm: when the remainder drops to zero during computation, the algorithm stops and returns the current divisor as the final GCD. Understanding this rule confirms why entering 0 as one input returns the other number as the result.

Can the GCD be calculated for more than two numbers at once?

Yes. The GCD of three or more numbers is computed by applying the algorithm iteratively using the associative property. For example, gcd(12, 18, 24) = gcd(gcd(12, 18), 24) = gcd(6, 24) = 6. Any order of evaluation produces the same result. Most multi-input GCD calculators use this chaining method, reducing the list of numbers one pair at a time until a single GCD remains.

What does it mean when the GCD of two numbers equals 1?

When gcd(a, b) = 1, the two numbers are called coprime or relatively prime, meaning they share no common factor other than 1. For instance, gcd(14, 15) = 1, so 14 and 15 are coprime despite neither being a prime number itself. Coprimality is fundamental in RSA public-key encryption, where the public exponent must be coprime with the totient of the key modulus to guarantee that decryption remains mathematically possible.

How is the greatest common divisor used to simplify fractions to lowest terms?

To reduce a fraction to its lowest terms, divide both the numerator and the denominator by their GCD. For the fraction 84/126, gcd(84, 126) = 42, so 84 divided by 42 equals 2 and 126 divided by 42 equals 3, producing the fully simplified fraction 2/3. No further reduction is possible because gcd(2, 3) = 1, confirming the two values are coprime and the fraction is already in its simplest form.