# Finding the GCD of three numbers?

I have found an algorithm called the Binary GCD/Stein Algorithm which takes two non-negative integers and finds the greatest common factor of the two.

What I am trying to do is take three numbers and find if each pair is relatively prime (where the GCD is one). For example, if I have non-negative variables a b and c, then:

a = 1
b = 1
c = 2


Would satisfy this because none of these numbers have a GCD that is larger than one. Using a variation of the Stein Algorithm in Java, I would like to be able to find the GCD of all three pairs of numbers (ab bc ac) with each side being able to go up to five, for the sake of simplicity.

Is there a way I could tweak the algorithm to compute the GCD of three numbers, or would I have to compute three groups of two pairs?

Thanks for any and all help.

-
Please note, there is an example of the implementation of this algorithm, in Java, on the link above. – nmagerko Dec 23 '11 at 18:07
If you treat $\gcd$ as an operator, much like addition or multiplication, it's commutative and associative. – J. M. Dec 23 '11 at 18:17
you could call your gcd function twice $d={\rm gcd}(a,b)$, $e={\rm gcd}(d,c)$ – yoyo Dec 23 '11 at 18:19
It may be commutative if I have two of the same number, but if the sides are 11,6,1, I don't see how they could be commutative. Maybe I am misunderstanding your comment? – nmagerko Dec 23 '11 at 18:20
$\gcd(a,b,c) = \gcd(\gcd(a,b),c) = \gcd(a,\gcd(b,c))=\gcd(\gcd(a,c),b)$ – Álvaro Lozano-Robledo Dec 23 '11 at 18:21

As others say, one way to do it is using the identity $\gcd(a,b,c)=\gcd(a,(\gcd(b,c))$. This identity is true since the "gcd" is the maximal element of the intersection of the sets of factors of the inputs. For example, taking $\gcd(6,10)$, the set of factors of $6$ is {$6, 3, 2, 1$}, the set of factors of $10$ is {$10, 5, 2, 1$}, their intersection is {$2, 1$}, and the maximal element is $2$. The identity follows since intersections of sets are commutative and associative.

However, it's also possible to extend Stein's algorithm to handle more than two inputs. Wikipedia gives 5 steps to Stein's algorithm, and we can change them to the following to compute the gcd of a set $S$ of numbers:

1. If anything in $S$ is zero, remove it.
2. If everything in $S$ is even, divide everything in $S$ by 2, and then multiply the final answer by 2 at the end.
3. If some numbers in $S$ are even and some are odd, divide all the even numbers by 2.
4. If every number in $S$ is odd, then choose an arbitrary element of $S$ and call it $k$. Replace every other element, say $n$, with $|n-k|/2$.
5. Repeat steps 1–4 until there is only one remaining element in $S$. After you remember to multiply in the twos that you got from step 2, that's your gcd!
-
I do believe that this algorithm takes the minimal element of the intersection, doesn't it? – nmagerko Dec 23 '11 at 19:26

Here is J.M. s algorithm implemented as a c++ template class

// Template for GCD
template<typename AType> AType VARGCD(int nargs, ...)
{
va_list arglist;
va_start(arglist, nargs);

AType *terms = new AType[nargs];
AType result = 0;

// put values into an array
for (int i = 0; i < nargs; i++)
{
terms[i] = va_arg(arglist, AType);
if (terms[i] < 0)
{
va_end(arglist);
return (AType)0;
}
}
va_end(arglist);

int shift = 0;
int numEven = 0;
int numOdd = 0;
int smallindex = -1;

// Step 1 count number of even and odd
do
{
numEven = 0;
numOdd = 0;
smallindex = -1;
for (int i = 0; i < nargs; i++)
{
if (terms[i] == 0)
continue;

if (terms[i] & 1)
numOdd++;
else
numEven++;

if ((smallindex < 0) || terms[i] < terms[smallindex])
{
smallindex = i;
}
}

// check for exit
if (numEven + numOdd == 1)
continue;

// If everything in S is even, divide everything in S by 2, and then multiply the final answer by 2 at the end.
if (numOdd == 0)
{
shift++;
for (int i = 0; i < nargs; i++)
{
if (terms[i] == 0)
continue;

terms[i] >>= 1;
}
continue;
}

// If some numbers in S  are even and some are odd, divide all the even numbers by 2.
if (numEven > 0 && numOdd > 0)
{
for (int i = 0; i < nargs; i++)
{
if (terms[i] == 0)
continue;

if ((terms[i] & 1)  == 0)
terms[i] >>= 1;
}
continue;
}

//If every number in S is odd, then choose an arbitrary element of S and call it k.Replace every other element, say n, with | n−k / 2.
if (numEven == 0)
{
for (int i = 0; i < nargs; i++)
{
if (i == smallindex || terms[i] == 0)
continue;

terms[i] = abs(terms[i] - terms[smallindex]) >> 1;
}
}

} while (numEven + numOdd > 1);

// only one remaining element multiply the final answer by 2s at the end.
for (int i = 0; i < nargs; i++)
{
if (terms[i] == 0)
continue;

return terms[i] << shift;
}

return 0;
};

-