Translations of Encyclopedia about Mathematics

An algorithm is a description of some, mostly mathematical method of solving a function determined for processing by computer. Algorithms often play a major role in information technology. Whenever a mathematical procedure is to be used by a computer, an algorithm must be prepared which will help the computer solve the function.

Example: Euclid’s Algorithm

Using Euclid’s algorithm, the largest common divisor for two natural numbers is determined. Then, the larger of the two numbers is divided by the smaller one and the divisor is divided by the remainder, this process repeating itself until there is no longer any remainder. The last divisor is the largest common divisor of the original two numbers.

Example: what is the largest common divisor of the numbers 672 and 1190?

1190 : 672 = 1, remainder 518
672 : 518 = 1, remainder 154
518 : 154 = 3, remainder 56
154 : 56 = 2, remainder 42
56 : 42 = 1, remainder 14
42 : 14 = 3

Solution: the largest common divisor of the numbers 672 and 1190 is the number 14.

Proof: starting from the bottom, the equations are written one after another like a test:

From this it ensues that the number 14 is the divisor of numbers 672 and 1190. The numbers 48 and 85 do not have a common divisor, for which reason the number 14 is the largest common divisor of 672 and 1190. For any two variables a and b, this approach can be used and proven as was just demonstrated.