# Greatest common divisor

Jump to navigation
Jump to search

The **greatest common divisor** of two numbers, and is the biggest integer that divides both and .

This comes in handy when calculating the least common multiple, since .

The *gcd* can be found by using the Euclidean algorithm.

## Some properties of the gcd[edit]

- Any number that divides both and divides .
- is expressible as for some integers and (Extended Euclidean algorithm).
- More generally, the equation has integer solutions for and if and only if . If it has one solution , it has infinitely many solutions, all given by as takes on all integer values.