The Euclidean Algorithm

Title:
The Euclidean Algorithm
Language:
C++
Author:
Philip J. Erdelsky
Date:
April 30, 2001
Usage:
Public domain; no restrictions on use
Portability:
Any C++ environment
Keywords:
Euclidean Algorithm, Greatest Common Divisor
Abstract:
A C++ package to perform the Euclidean Algorithm
source Code:
euclid.txt

The Euclidean algorithm is a simple but useful procedure to find the greatest common divisor (GCD) of two positive integers. (There are variations for polynomials and other more general numbers.)

This package uses the Euclidean algorithm on numbers of an arbitrary unsigned integer type called UITYPE. You should add an appropriate "typedef" statement to define this type. If your application uses two or more different unsigned integer types, you might consider using templates instead.

The package accesses numbers of type UITYPE by reference because in some applications (such as cryptography) they may be quite large.

The package defines two functions. The first one merely computes the GCD of two positive integers:

```     GreatestCommonDivisor(x, y, g);

const UITYPE &x;    positive integer

const UITYPE &y;    positive integer

UITYPE &g;          filled in with the GCD of x and y
```

The second one is a little more sophisticated:

```     EuclideanAlgorithm(x, y, a, b, g);

const UITYPE &x;    positive integer

const UITYPE &y;    positive integer

UITYPE &a;          see below

UITYPE &b;          see below

UITYPE &g;          filled in with the GCD of x and y
```

This function computes the GCD g of x and y and also two integers a and b such that:

```     ax - by = g,  1 <= a <= y,  0 <= b < x.
```

These functions will fail in undefined ways if either x or y is zero, or if there is a numeric overflow. However, if the UITYPE type can hold x and y, it can hold all intermediate values and results without overflow.

The Euclidean algorithm is recusive. If x <= y, we divide y by x to obtain a quotient and remainder with the properties

```     y = qx + r, 0 <= r < x.
```

If r = 0, the GCD of x and y is x, so a = 1, b = 0, and g = x.

If r is not 0, then we notice first that every divisor of x and y is also a divisor of r, and that every divisor of x and r is also a divisor of y. Hence the GCD of x and r is the same as the GCD of x and y. We use the algorithm on x and r to obtain:

```     a'x - b'r = g,  1 <= a' <= r,  0 <= b' < x.
```

Then it is easy to show that the following values of a and b meet all the requirements:

```     a = a' + b'q,

b = b'.
```

If x > y, we can use the algorithm with x and y reversed to obtain b'y - a'x = g, 1 <= b' <= x, 0 <= a' < y.

Then

```     (-a')x - (-b')y = g,
```

but this isn't quite what we want, because -a' and -b' are out of range in nearly all cases. We can fix this by adding the identity yx - xy = 0 to obtain

```    (y-a')x - (x-b')y = g,
```

in which the coefficients are in the desired ranges.

The coefficients are unique within their specified ranges if g = 1. If g > 1, they are not unique, but application of the same algorithm to x/g and y/g yields a and b such that

```     a(x/g) - b(y/g) = 1,  1 <= a <= (y/g),  0 <= b <= (x/g)-1,
```

or, equivalently

```     ax - by = g,  1 <= a <= (y/g),  0 <= b <= (x/g)-1,
```

and these coefficients are unique within these narrower ranges.