The greatest common divisor (GCD) of two numbers a and b is the largest number that divides both a and b evenly.
Example: GCD(12, 18). Divisors of 12: 1, 2, 3, 4, 6, 12. Divisors of 18: 1, 2, 3, 6, 9, 18. Common divisors: 1, 2, 3, 6. The greatest is 6.
GCD appears in fraction simplification, modular arithmetic, and many algorithms. You will learn an efficient algorithm for it next section.