The greatest common factor is the largest integer that divides every number in a set exactly. NIST's Dictionary of Algorithms and Data Structures defines the greatest common divisor as the greatest integer which is a divisor of given positive integers, gives the example GCD(30, 42) = 6, and lists highest common factor as another name. The GCF is used to reduce fractions and ratios to lowest terms and to factor expressions in algebra. Two numbers whose GCF is 1 are called coprime.
Formula
Two standard methods:
- Prime factorization: write each number as a product of primes; the GCF is the product of the shared primes, each raised to the smallest exponent that appears.
- Euclid's algorithm: replace the larger number with the remainder of dividing it by the smaller, and repeat until the remainder is 0. The last non-zero remainder is the GCF.
The GCF is linked to the least common multiple by GCF(a, b) × LCM(a, b) = a × b for positive integers a and b.
Example
Find GCF(48, 180).
- Prime factorization: 48 = 2⁴ × 3 and 180 = 2² × 3² × 5. Shared primes at their smallest powers: 2² × 3 = 12.
- Euclid's algorithm: 180 = 3 × 48 + 36; 48 = 1 × 36 + 12; 36 = 3 × 12 + 0. The GCF is 12.
Use: the fraction 48/180 reduces to 4/15 by dividing both parts by 12. Check: LCM(48, 180) = 48 × 180 ÷ 12 = 8,640 ÷ 12 = 720.
The GCF calculator shows these steps, the factor calculator lists every factor of a number, and the LCM calculator handles the companion problem. The ratio calculator and decimal to fraction calculator use the GCF to simplify results.
Common mistakes
- Taking the largest exponent of each prime, which gives the LCM instead.
- Stopping at a common factor that is not the greatest, such as 6 for 48 and 180.