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.
No comments:
Post a Comment