Greatest Common Divisor (gcd)

The Greatest Common Divisor (gcd), also sometimes called the Greatest Common Factor (gcf), is the largest positive integer that divides two non-zero integers without remainder.

The Greatest Common Divisor of two number, say a and b, is usually written in the form gcd(a,b). Here are some examples:

gcd(9,18) = 9

gcd(4,18) = 2

gcd(9, 28) = 1 *

* Note in the case when the gcd of two numbers is 1 the numbers are called coprime or relatively prime.

How to calculate the gcd:

We know from the Fundamental Theorem of Arithmetic that every number can be broken down to a product of prime numbers. This is called the number's unique prime factorization. One we find this for the two number we wish to calculate the gcd of, we simply take the numbers that match exactly in each number's unique factorization and multiply them together. Here's a simple example:

gcd(120, 156)

Well, first we find the unique factorization of each number:

120 = 2 * 2 * 2 * 2 * 3 * 5
156 = 2 * 2 * 3 * 13

The numbers that have an exact match in the other's factorization (noted above in red) are multiplied together:

2 * 2* 3 = 12

So,

gcd(120,156) = 12