Note: Due to changes in the Riesel prime template, most of those pages (and related) are not shown properly.
This will take some time!
Wanna help? Please move any Riesel prime page first, then edit/add the base parameter.
Topics Register • News • History • How to • Sequences statistics • Template prototypes

Greatest common divisor

From Prime-Wiki
Jump to: navigation, search

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