The greatest common factor, also known as the greatest common divisor and greatest common factor, refers to the largest of the divisors shared by two or more integers.
The greatest common divisor of a, b is denoted as (a, b). Similarly, the greatest common divisor of a, b, c is denoted as (a, b, c). The greatest common divisors of multiple integers have the same sign.
There are many ways to find the greatest common divisor. Common factors include prime factorization, short division, rolling phase division, and more subtraction.
The concept corresponding to the greatest common divisor is the least common multiple, and the least common multiple of a, b is recorded as [a, b].
If the number a is divisible by the number b, a is called a multiple of b, and b is called a divisor of a.
Both divisors and multiples represent the relationship of one integer to another, and cannot exist alone. For example, we can only say that 16 is a multiple of a certain number and 2 is a divisor of a certain number, but we cannot say in isolation that 16 is a multiple and 2 is a divisor.
The Greatest Common Divisor (GCD), also called the Greatest Common Factor (GCF), of two or more integers is the largest positive number that divides all of them exactly (without leaving a remainder).
For example, the GCD of 18 and 24 is 6, because 6 is the biggest number that divides both evenly.
The GCD is useful for:
Simplifying fractions to their lowest terms.
Factoring and solving mathematical equations.
Reducing ratios to their simplest form.
Solving number theory problems involving divisibility or modular arithmetic.
Finding common patterns in integers or optimizing algorithms that rely on repeated structures.
It helps eliminate redundancy and find efficiency in mathematical and real-world applications.
There are several methods to find the GCD of two numbers:
Listing factors: List all divisors of each number and find the largest one they have in common.
Prime factorization: Break both numbers into their prime factors and multiply the common ones.
Euclidean Algorithm: Repeatedly subtract the smaller number from the larger or use division with remainders until the remainder is zero. The last non-zero remainder is the GCD.
Example of the Euclidean Algorithm for GCD(a, b):
GCD(48, 18):
48 ÷ 18 = 2 remainder 12
18 ÷ 12 = 1 remainder 6
12 ÷ 6 = 2 remainder 0
→ GCD is 6
Use the GCD when:
Reducing fractions or ratios to simplest form.
Solving Diophantine equations (equations with integer solutions).
Optimizing algorithms that involve cycles, rotations, or partitions.
Determining if two numbers are relatively prime (i.e., their GCD is 1).
Dividing items into groups with the largest equal size possible (e.g., splitting something evenly among people or containers).
GCD is fundamental in both basic arithmetic and more advanced number theory or algorithm design.