Euclidean, Bezout, and Coprime Oh My!

Occasionally a programmer loves to play with numbers. Some like to stick gum in their sister’s hair, but that is besides the point. At the heart of some programming is the heart of mathematics and especially number theory. One of the great theoretical algorithms out there is the Extended Euclidean algorithm which is used to find the Greatest Common Divisor (GCD). The GCD is a number which divides both of two numbers. This isn’t factoring of two numbers mind you. The original Euclidean algorithm dates back to the ancient Greeks and is one of the oldest known algorithms. I guess that means that the Greeks could have been some serious kick ass programmers! Playing around with the Extended Euclidean algorithm, we will also stumble upon our friends Bezout and Coprime. So jump on the yellow brick road, because we are going to see the wizardry of algorithms here on the Programming Underground!

It is said that Euclid himself may not have discovered the algorithm, but it was him who published it around 300 BC. The algorithm is a clever way of finding out the greatest common divisor of two numbers. A number that can be divided in both numbers evenly. Like both 6 and 9 can be divided by 3. Later on the algorithm was extended to find out even more useful information including the two numbers that can be combined with the original two numbers to form the famous equation “ax + by = GCD” known as the Bezout Identity. So for our example it would be 6x + 9y = 3. Where it would yield the results x = -1 and y = 1. This is not the only solution, but can be one of many.

When a GCD is also equal to 1, it is said that the two numbers are “coprime” or “partially prime”. This means that only the value 1 can divide both numbers. That is, they share no other divisor but 1. This doesn’t necessarily mean that the two numbers themselves are prime, but only that they share this unique result of only having 1 as a divisor.

In many formulas out there you need to find the GCD of two numbers. C++, to the best of my knowledge, doesn’t provide such a function for finding this divisor. However with a little ingenuity we can find the GCD as well as its friends Bezout and coprime. So lets take a look at how this works…

#include <iostream>
using namespace std;

void extendedGCD(int value1, int value2);

int main() {

	// Make a call to our GCD using some coprime numbers
	extendedGCD(4,9);


	return 0;
}

// This algorithm finds three things. 
// It finds the Greatest Common Divisor (a number that divides both values)
// It finds out the values of X and Y at the same time used for the Bézout's identity
// Notifies us if the values are also Coprime (That is only 1 can divide them both).

void extendedGCD(int value1, int value2) {
	// Setup the first stage variables for our equation
	// eg. value1 = (value1 * 1) + (value2 * 0)
	// eg. value2 = (value1 * 0) + (value2 * 1)

	int x = 0, y = 1;
	int prevx = 1, prevy = 0;

	// We loop while our second value is not zero
	while (value2 != 0) {

		// Hold value2 because it will become our value1 in next iteration (carried forward) 
		int holdValue = value2;

		// Get the quotient and its remainder (remainder will be our new value2)
		int quotient = value1 / value2;
		value2 = value1 % value2;
		value1 = holdValue;


		// X and Y are calculated to use for the Bézout's Identity
		// A set of numbers that satisify the equation ax + by = GCD

		holdValue = x;
		x = prevx - quotient * x;
		prevx = holdValue;

		holdValue = y;
		y = prevy - quotient * y;
		prevy = holdValue;
	}

	// Print out our Bézout results and the GCD
	cout << "X: " << prevx << " Y:" << prevy << endl;
	cout << "Greatest Common Divisor: " << value1 << endl;

	// If the GCD is 1 it also means that they are coprime
	// That is can only be divided by 1. The numbers themselves may not prime.
	if (value1 == 1) { 
		cout << "These numbers are coprime!" << endl;
	}
}

I step through the process with in code comments. Feel free to modify this algorithm to print out or return only the information you want. I created it as void so that I can print out all the information at once. In a production/library of functions environment you may even want to break these up into separate functions. One that finds only the GCD, one for the Bezout identity values and a bool function to check if it is coprime.

The example is one of the iterative form and could also be solved using a recursive approach. For demonstration purposes I figured an iterative approach would also show the steps involved by collecting the quotient, divisor, and the initial x/y values for Bezout. We use the quotient and divisor to then figure out the next iteration of the algorithm until we eventually hit a value2 equal to 0. Once value2 equals zero, value1 will contain the GCD. We can then check the GCD for being coprime. The bi-product of this algorithm is the Bezout identity values.

So how might the GCD be useful in programming? Well, for one it can tell you if two distances from a character in a game share a common divisor unit which then you can have your character move in a turn based game.

For instance, if the haunted woods were 1071 steps away and the enchanted castle of Skyhawk133 was 1029 steps away, you could figure out that, by making your character travel 21 steps an hour, you will reach the woods in exactly 51 hours and the castle in 49 hours (exactly). Presenting this to the user may allow them to choose going to the woods since the cost of only 2 additional hours is no big deal. You could also then make any other destinations you want the character to go to a multiple of 21 steps / hr and thus deal with nice even numbers instead of fractions/decimals. If your character is hurt, you could make them do 7 steps a hour knowing that since 7 is a a multiple of 21 that they still will get to each destination with a nice and even number of hours.

This is only one application, but it can be used in all sorts of time/spacial situations and great for games (as demonstrated above). So feel free to play around with it and hopefully you can find it useful in your projects.

Oh and if you see the wicked witch of mathematics, run like hell because even armed with this mojo of an algorithm, you can’t defeat her powers! Not yet anyways!

Thanks for reading and visiting the Coders Lexicon. 🙂