askvity

How to Find GCD?

Published in Number Theory 2 mins read

The Greatest Common Divisor (GCD), also known as the Highest Common Factor (HCF), of two or more integers is the largest positive integer that divides each of the integers. Here are several methods to find the GCD:

1. Listing Factors

This method is suitable for smaller numbers.

Steps:

  1. List all the factors (divisors) of each number.
  2. Identify the common factors of all the numbers.
  3. The largest of these common factors is the GCD.

Example: Find the 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

2. Prime Factorization

This method is more efficient for larger numbers.

Steps:

  1. Find the prime factorization of each number.
  2. Identify the common prime factors.
  3. Multiply the common prime factors, using the lowest power of each common prime factor that appears in any of the factorizations.

Example: Find the GCD of 36 and 60.

  • Prime factorization of 36: 22 × 32
  • Prime factorization of 60: 22 × 3 × 5
  • Common prime factors: 2 and 3
  • Lowest power of 2: 22
  • Lowest power of 3: 31
  • GCD: 22 × 3 = 4 × 3 = 12

3. Euclidean Algorithm

This is the most efficient method, especially for very large numbers.

Steps:

  1. Divide the larger number by the smaller number and find the remainder.
  2. If the remainder is 0, the smaller number is the GCD.
  3. If the remainder is not 0, replace the larger number with the smaller number and the smaller number with the remainder.
  4. Repeat steps 1-3 until the remainder is 0. The last non-zero remainder is the GCD.

Example: Find the GCD of 48 and 18.

  1. 48 ÷ 18 = 2 remainder 12
  2. 18 ÷ 12 = 1 remainder 6
  3. 12 ÷ 6 = 2 remainder 0
  4. GCD: 6

4. LCM Method

As mentioned in the reference, the GCD can also be found using the Least Common Multiple (LCM).

Formula:

GCD(a, b) = (a × b) / LCM(a, b)

Steps:

  1. Find the LCM of the two numbers.
  2. Multiply the two numbers.
  3. Divide the product by the LCM.

Example: Find the GCD of 12 and 18.

  1. LCM(12, 18) = 36
  2. 12 * 18 = 216
  3. GCD(12, 18) = 216 / 36 = 6

In summary, you can find the GCD using listing factors, prime factorization, the Euclidean Algorithm, or the LCM method, each offering its own advantage depending on the size and nature of the numbers involved. The Euclidean Algorithm is generally considered the most efficient for larger numbers.

Related Articles