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.
Best Answer
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: