Greatest common divisor

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