“GCD (Greatest Common Divisor)” or “HCF (Highest Common Factor)” is the largest number that can exactly divide two or more numbers, meaning there is no remainder after division.

There are three common methods to calculate the GCD:

• Listing Factors Method 
• Prime Factorization Method 
• Euclidean Algorithm

Determine GCD/HCF Using Listing Factors Method

In this method, we list all the factors of each number and find the largest one they share in common.

Steps:

• List all the factors of each number.
• Identify the common factors.
• The largest common factor is the GCD.

Examples

Example 1: Find GCD of 12 and 18 

– Factors of 12: 1, 2, 3, 4, 6, 12 

– Factors of 18: 1, 2, 3, 6, 9, 18 

– Common factors: 1, 2, 3, 6 

– GCD = 6

Example 2: Find GCD of 8, 12, and 16 

– Factors of 8: 1, 2, 4, 8 

– Factors of 12: 1, 2, 3, 4, 6, 12 

– Factors of 16: 1, 2, 4, 8, 16 

– Common factors: 1, 2, 4 

– GCD = 4

Example 3: Find GCD of 10, 20, 30, and 40 

– Factors of 10: 1, 2, 5, 10 

– Factors of 20: 1, 2, 4, 5, 10, 20 

– Factors of 30: 1, 2, 3, 5, 6, 10, 15, 30 

– Factors of 40: 1, 2, 4, 5, 8, 10, 20, 40 

– Common factors: 1, 2, 5, 10 

– GCD = 10

Determine GCD/HCF Using Prime Factorization Method

This method involves breaking each number into its prime factors, then multiplying the common prime factors.

Steps:

• Write the prime factorization of each number.
• Identify the common prime factors (including the count).
• Multiply the common prime factors to find the GCD.

Examples

Example 1: Find GCD of 12 and 18 

– 12 = 2 × 2 × 3 

– 18 = 2 × 3 × 3 

– Common primes: 2 × 3 

– GCD = 6

Example 2: Find GCD of 8, 12, and 16 

– 8 = 2 × 2 × 2 

– 12 = 2 × 2 × 3 

– 16 = 2 × 2 × 2 × 2 

– Common primes: 2 × 2 

– GCD = 4

Example 3: Find GCD of 10, 20, 30, and 40 

– 10 = 2 × 5 

– 20 = 2 × 2 × 5 

– 30 = 2 × 3 × 5 

– 40 = 2 × 2 × 2 × 5 

– Common primes: 2 × 5 

– GCD = 10

Determine GCD/HCF Using Euclidean Algorithm

This method repeatedly divides the larger number by the smaller one until the remainder is 0. The last non-zero remainder is the GCD. It is especially useful for large numbers.

Steps for two numbers:

• Divide the larger number by the smaller one.
• Replace the pair with (smaller number, remainder).
• Repeat until the remainder is 0.
• The last non-zero remainder is the GCD.

Steps for three or more numbers:

• Find the GCD of the first two numbers.
• Use that result to find the GCD with the third number.
• Continue this process until all numbers are included.
• The final result is the overall GCD.

Examples

Example 1: Find GCD of 12 and 18 

– 18 ÷ 12 = 1, remainder = 6 

– 12 ÷ 6 = 2, remainder = 0 

– GCD = 6

Example 2: Find GCD of 105, 60, and 30 

– GCD(105, 60): 

  – 105 ÷ 60 = 1, remainder = 45 

  – 60 ÷ 45 = 1, remainder = 15 

  – 45 ÷ 15 = 3, remainder = 0 → GCD1 = 15 

– GCD(15, 30): 

  – 30 ÷ 15 = 2, remainder = 0 → GCD = 15

– Final GCD = 15

Example 3: Find GCD of 84, 120, 156, and 204 

– GCD(84, 120): 

  – 120 ÷ 84 = 1, remainder = 36 

  – 84 ÷ 36 = 2, remainder = 12 

  – 36 ÷ 12 = 3, remainder = 0 → GCD1 = 12 

– GCD(12, 156): 

  – 156 ÷ 12 = 13, remainder = 0 → GCD2 = 12 

– GCD(12, 204): 

  – 204 ÷ 12 = 17, remainder = 0 → GCD3 = 12 

– Final GCD = 12

Determine GCD Using Calculator

If you want to skip manual calculations, try below Calculator! Just enter numbers, and the tool will instantly calculate the Greatest Common Divisor (GCD) or Highest Common Factor (HCF). It’s quick, accurate, and works for both small and large numbers.