Skip to content

Greatest Common Factor (GCF)


The Greatest Common Factor (GCF) or Greatest Common Divisor (GCD) of two non-zero integers is the largest positive integer that divides both numbers without remainder.
Example #1:

GCF(6, 18) = ?

Solution #1:

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

The largest factor common to both numbers is 6
∴ GCF(6, 18) = 6

Example #2:

GCF(18, −4) = ?

Solution #2:
(The negative number sign may be ignored as divisibility is not affected)
Factors of 18:  1, 2, 3, 6, 18
Factors of 4:  1, 2, 4

The largest factor common to both numbers is 2
∴ GCF(18, −4) = 2
Properties:
  • Every common divisor of a and b is a divisor of GCF(a, b).
  • GCF(a, b), where a and b are not both zero, may be defined alternatively and equivalently as the smallest positive integer d which can be written in the form d = a·p + b·q where p and q are integers.
  • GCF(a, 0) = |a|, for a ≠ 0, since any number is a divisor of 0, and the greatest divisor of a is |a|.
  • If a divides the product b·c, and GCF(a, b) = d, then a/d divides c.
  • If m is a non-negative integer, then GCF(m·a, m·b) = m·GCF(a, b).
  • If m is any integer, then GCF(a + m·b, b) = GCF(a, b). If m is a nonzero common divisor of a and b, then GCF(a/m, b/m) = GCF(a, b)/m.
  • The GCF is a multiplicative function in the following sense: if a1 and a2 are relatively prime, then GCF(a1·a2, b) = GCF(a1, b)·GCF(a2, b).
  • The GCF is a commutative function: GCF(a, b) = GCF(b, a).
  • The GCF is an associative function: GCF(a, GCF(b, c)) = GCF(GCF(a, b), c).
  • The GCF of three numbers can be computed as GCF(a, b, c) = GCF(GCF(a, b), c), or in some different way by applying commutativity and associativity. This can be extended to any number of numbers.
  • GCF(a, b) is closely related to the Least Common Multiple LCM(a, b): we have
GCF(a, b)·LCM(a, b) = a·b   (This formula is often used to compute least common multiples)

Related Topic: