Greatest Common Factor

From Teach And Discover Wiki

Back to Pre-Algebra

In Mathematics, the greatest common factor (also known as the greatest common divisor), or gcf, of two non-zero integers is the largest positive integer that divides both numbers without leaving a remainder.

Overview

The greatest common factor of a and b is written as gcf(a, b), or sometimes simply as (a, b). For example, gcf(12, 18) = 6, gcf(−4, 14) = 2 and gcf(5, 0) = 5. Two numbers are called coprime or relatively prime if their greatest common divisor equals 1. For example, 9 and 28 are relatively prime.

The greatest common divisor is useful for reducing improper fractions to be in lowest terms. For example, gcd(42, 56)=14, therefore,

Calculating the gcd

Greatest common divisors can in principle be computed by determining the prime factorizations of the two numbers and comparing factors, as in the following example: to compute gcd(18,84), we find the prime factorizations 18 = 2·3² and 84 = 2²·3·7 and notice that the "overlap" of the two expressions is 2·3; so gcd(18,84) = 6. In practice, this method is only feasible for very small numbers; computing prime factorizations in general takes far too long.