Procedure Solver

Chanwc from Hong Kong, Matthew from QEB, Alpha Lee from Yew Chung International School, Phil from Garforth Community College and Andrei from Tudor Vianu National College all correctly worked out that the algorithm produces the greatest common factor of two whole numbers .

Aneesh correctly applied the algorithm for the cases X = 4 and Y = 1 and conjectured that the algorithm was to produce the output 1, whereas Alpha started with this example:

initial x_i = 25 y_i = 5
1. x_1 = 25-5 = 20 y_1 = 5 since x_i> y_i
2. x_2 = 20-5 =15 y_2 = 5 since x_1> y_1
3. x_3 = 15-5 =10 y_3 = 5 since x_2> y_2
4. x_4 =10-5 =5 y_4 = 5 since x_2> y_2
5. x = output = 5 since x_4 = y_4 gcd(25,5) = 5 since 25 = 5*5 5 = 5*1

The algorithm (which was discovered by the Greek mathematician Euclid over 2000 years ago) makes use of the fact that the greatest common divisor of two numbers (a ,b) equals the greatest common divisor of (a, b-a). Andre, Alpha and Phil all noticed this fact, giving good, clear proofs. Phil's notation was particularly clear :

Rename the two integers X and Y as AH and BH, meaning 'A multiples of the HCF' and 'B multiples of the HCF'. The difference between them, AH-BH, factorises to H(A-B). The difference between integers X and Y must be an integer, as must the difference between A and B, so the difference between X and Y must be a multiple of the HCF. Phil then noted that As the algorithm cycles, the numbers X and Y will always be replaced with lower multiples of the HCF of the original X and Y. The algorithm continues to subtract until only the HCF remains.


Matthew from QEB also solved the problem and, interestingly, converted the procedure into Javascript, a programming language most commonly used in webpages :

function getHCF(x,y) {
while (x != y) {
if (x > y) { x = x-y }
if (x < y) { y = y-x }
}
return x;
}

Matthew gave a clear and extended description of his code, which you can read about here .This is recommended for any budding programmers!