gcd by subtraction - the logic

I previously described how it is possible to find the greatest common divisor of two natural numbers by using Euclid's subtraction algorithm. The logic for that algorithm is as follows:-

Label 0
Input A
Input B
If A = B then
   Goto Label 2
EndIf
If B>A then
   Store A in X
   Store B in A
   Store X in B
EndIf
Label 1
Store A-B in C
Store B in X
If X>C then
   Store B in A
   Store C in B
Else
   Store C in A
EndIf
If A is not equal to B then
   Goto Label 1
EndIf
Label 2
Display A
Goto Label 0

This processing carries out the following. The two numbers whose gcd is sought are input as A and B. If A equals B then the gcd(A,B) is simply A (or B) and there is no more work to be done. If B is greater than A, then we swap the values of A and B. Euclid's subtraction algorithm then begins after Label 1. We calculate A-B. If B is greater than A-B then we store B in A and A-B in B otherwise B remains unchanged and we store A-B in A. We repeat the process until A equals B and then we display A and stop the processing. After A is displayed, we then have the otption of returning to the beginning to process another pair of numbers.

gcd by subtraction

The greatest common divisor (gcd) of two natural numbers is the largest natural number that divides both. For example, the gcd of 72 and 15 is 3 since 3 is the largest number that divides both 72 and 15. We can see this more clearly if determine the prime factors of these two numbers. We have that 72=8x9=2x2x2x3x3 and 15=3x5 and we have only one prime factor, 3, that is common to both.

Euclid came up with a very neat algorithm for finding the gcd of two numbers that is based on subtraction and this algorithm is easy to implement on the fx-50F. Using the above example of 72 and 15 above, the method goes as follows.

Our first pair of numbers is (72, 15) and in each pair we want the first entry to be the larger of the two numbers. To form the next pair we subtract 15 from 72 to give 57 and form the pair (57, 15). We carry on in a similar way obtaining (42,15) and (27, 15). Then subtracting 15 from 27 we get 12 and this is smaller than 15, so they next pair is (15, 12). Then 15 minus 12 is 3 and so we get (12,3), then (9,3), then (6,3) and finally (3,3). When the two pairs of numbers are equal then either number is the gcd of 72 and 15, as we found out above.

I have described the method in more detail in my maths blog.