Divisibility and PrimesGcd

Once again, we can use the prime factorisation to calculate the gcf of any two numbers. Remember that any factor of a number must have some of the prime factors of that number.

Suppose that X is the gcf of 18 and 30. Then X divides 18 so the prime factors of X must be among 2, 3 and 3. Also, X divides 30 so the prime factors of X must be among 2, 3 and 5.