Euclid's algorithm

The oldest non-trivial algorithm is the way to find the greatest common divisor of two integers - Euclid's algorithm. He was expounded in the works of the ancient Greek mathematician Euclid - the seventh book of "Beginnings" - about 2300 years ago. Of course, you can argue - but what about the ancient Egyptians? Babylonians? Could not they offer a more ancient algorithm? Calculations of ancient Egyptians and Babylonians are found, they are older than Greek for fifteen hundred years, but the Euclidean algorithm has one significant difference - it is iterative, that is, it has repeated repetition of certain actions.

Consider the Euclidean algorithm of finding the greatest common divisor of two positive integers. This is how it is implemented.

"Let A and C be two given positive integers, and find their greatest common divisor. If C divides A, then C is a common divisor of the numbers C and A, since it also divides itself. Obviously, C is also the greatest divisor, since there is no number greater than C, which would divide C.

If C does not divide A, then we start continuously subtracting the smaller of the numbers A and C from the larger until we get a number that completely divides the previous subtrahend. Sooner or later this number will be obtained, because if the difference is unit, then the unit will divide the previous subtrahend.

So, let E be a positive balance from division And on C, F is the positive remainder of dividing C by E, F divides E. Since F divides E, and E divides C-F, F also divides C-F, but F divides itself, hence F divides C. But C divides A-E; therefore F also divides A - E. But it also divides E, therefore it also divides A. Hence, F is a common divisor of the numbers A and C.

Now I say that he is the greatest such divisor. Indeed, if F is not the greatest common divisor of the numbers A and C, then some larger number will divide both of them. Suppose that such a number is B.

Since B divides C, which, in turn, divides A-E, then B divides A-E; B also divides all A, and therefore it also divides the remainder of E. But E divides C-E, so B divides C-E. But B also divides all of C, therefore, it also divides F; thus, a larger number divides less, and this is impossible.

Therefore, there is no such number greater than F that would divide the numbers A and C, and hence F is their greatest common divisor.

In conclusion, I would like to say that the Babylonian and Egyptian algorithms are of exclusively historical interest, while the Euclidean algorithm has not lost its practical significance to this day.