Greatest common divisor

From Algorithmist

Jump to: navigation, search

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

This comes in handy when calculating the least common multiple, since lcm(a,b) = \frac{ a b }{ \gcd(a,b) }.

The gcd can be found by using the Euclidean algorithm.

[edit] Some properties of the gcd

  • Any number that divides both a and b divides gcd(a,b).
  • gcd(a,b) is expressible as ax + by for some integers x and y(Extended Euclidean algorithm).
  • More generally, the equation ax + by = c has integer solutions for x and y if and only if \gcd(a,b)\mid c. If it has one solution (x0,y0), it has infinitely many solutions, all given by (x_0+\frac{b}{gcd(a,b)}t,y_0-\frac{a}{gcd(a,b)}t) as t takes on all integer values.
Retrieved from "http://www.algorithmist.com/index.php/Greatest_common_divisor"
Personal tools