GCD Calculator

The greatest common divider (GCD) — also known as the greatest common divisor or highest common factor (HCF) — is the largest number that divides two or more integers without leaving a remainder.

Ways to Find GCD

1. Listing Factors

   This way is suitable only for small numbers.

   To use this method write down factors of all numbers and choose the highest common one.

   Find the GCD of 18 and 24.

   • Factors of 18: 1, 2, 3, 6, 9, 18
   • Factors of 24: 1, 2, 3, 4, 6, 8, 12, 24
   • Common factors: 1, 2, 3, 6
   • GCD = 6

2. Prime Factorization

   The prime factorization method involves breaking down each number into its prime factors and then multiplying the common primes with the lowest exponents.

   It is not efficient for very large numbers (use the Euclidean Algorithm instead).

   Steps:

   • Factorize each number into its prime factors.
   • Identify all common prime factors between the numbers.
   • Take the smallest exponent for each common prime.
   • Multiply them together to get the GCD.

   GCD(48, 18)

   • 18 = 2¹ × 3²
   • 24 = 2³ × 3¹
   • Common prime factors: 2¹ × 3¹ = 6

   Use our GCD calculator to get detailed solution using prime factorization for any numbers.

3. Euclidean Algorithm

   Euclid’s algorithm is an efficient method to find the GCD of two numbers. It is the most convenient for large numbers.

   Steps:

   • Divide bigger number by smaller and find a remainder.
   • Replace bigger number with smaller and smaller with remainder from step 1.
   • Repeat division until remainder is zero.
   • Last non-zero remainder is GCD.

   GCD(48, 18)

   • 48 ÷ 18 = 2 remainder 12
   • 18 ÷ 12 = 1 remainder 6
   • 12 ÷ 6 = 2 remainder 0

   GCD(48,18) = 6.

   To compute the GCD of several numbers using Euclid’s Algorithm, start with the first two numbers, compute their GCD, then take the result and compute GCD with the next number. Repeat until all numbers are processed. Final result is the GCD of the entire set.

   Use our GCD calculator to get detailed solution using Euclidean Algorithm for any numbers.

Where Do We Use GCD?

1. Simplifying Fractions

   1824

   GCD(18, 24) = 6

   18 ÷ 624 ÷ 6

   =

   34

   GCD helps reduce a fraction to lowest terms.