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
- 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.