Greatest Common Divisor (GCD)

The greatest common divisor (GCD) of two or more integers is the largest positive integer that divides each of the integers without a remainder.

Methods for Finding GCD

1. Prime Factorization: Express each number as a product of prime factors, then identify the common prime factors and multiply them together to find the GCD.
2. Euclidean Algorithm: A more efficient method involving division and remainder operations, which is especially useful for large numbers.

Example 1: Finding GCD using Prime Factorization

Find the GCD of 24 and 36.

Prime factorization of 24: 2 * 2 * 2 * 3

Prime factorization of 36: 2 * 2 * 3 * 3

Common prime factors: 2 and 3

GCD(24, 36) = 2 * 2 * 3 = 12

Example 2: Finding GCD using Euclidean Algorithm

Find the GCD of 1071 and 462 using the Euclidean Algorithm.

Step 1: Divide 1071 by 462 to get a quotient of 2 and a remainder of 147. (1071 = 2 * 462 + 147)

Step 2: Divide 462 by 147 to get a quotient of 3 and a remainder of 21. (462 = 3 * 147 + 21)

Step 3: Divide 147 by 21 to get a quotient of 7 and a remainder of 0. (147 = 7 * 21 + 0)

Since the remainder is 0, the GCD is the divisor in the last division, which is 21. Therefore, GCD(1071, 462) = 21.

Properties of GCD

• The GCD of two numbers a and b can be expressed as a linear combination of a and b, i.e., there exist integers x and y such that GCD(a, b) = ax + by.
• If a is a multiple of b, then the GCD of a and b is b.
• If a and b are both even, then GCD(a, b) = 2 * GCD(a/2, b/2).