Greatest common divisor

The Greatest common divisor (gcd) of two numbers, commonly expressed by [math]\displaystyle{ gcd(a, b) }[/math], where [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math] are positive integers, is the maximum number that divides both [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math].

We can also define [math]\displaystyle{ gcd(a, 0) = a }[/math] and [math]\displaystyle{ gcd(a, b) = gcd(|a|, |b|) }[/math] thus defining the operations for all integers.

When the greatest common divisor is 1, both numbers are coprime or relatively prime. This does not mean that either of these numbers are prime.

Although the GCD can be readily computed if the prime factors of both numbers are known, in the context of this wiki the numbers are not factored in advance and the GCD helps find a factor of these numbers, so an alternate method is required.

Fortunately Euclid discovered such an algorithm more than 2000 years ago. Expressed in modern notation the algorithm is:

1. If [math]\displaystyle{ b = 0 }[/math], terminate the algorithm with [math]\displaystyle{ a = 0 }[/math] as the answer.
2. Set a temporary variable [math]\displaystyle{ r }[/math] to [math]\displaystyle{ a\,\mathrm{mod}\,b }[/math].
3. Set the variable [math]\displaystyle{ a }[/math] to [math]\displaystyle{ b }[/math].
4. Set the variable [math]\displaystyle{ b }[/math] to [math]\displaystyle{ r }[/math].
5. Go back to step 1.

There are faster methods, especially when number of thousands or millions of digits are used, as in GIMPS, but they are much more complex than the one presented above.

External links

• Wikipedia