Currently there may be errors shown on top of a page, because of a missing Wiki update (PHP version and extension DPL3).
Navigation
Topics Help • 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.

Error checking method

This method may be used to error-check a GCD computation. It was suggested by Robert Gerbicz in a MersenneForum post, and may possibly be found elsewhere as well.

To calculate [math]\displaystyle{ gcd(x,y) }[/math]:

  1. Take a random 64-bit prime: [math]\displaystyle{ q }[/math].
  2. Calculate [math]\displaystyle{ v=gcd(q*x,q*y) }[/math].
  3. If [math]\displaystyle{ q }[/math] does not divide [math]\displaystyle{ v }[/math], then there was an error, otherwise [math]\displaystyle{ gcd(x,y)=v/q }[/math] (with large probability).

External links