Euclid's Algorithm.

     Euclid's algorithm for the greatest common divisor (GCD) of numbers a and b.

     Step 1. If a < b, change the places of a and b.

     Step 2. If a > b, change a into a - b and turn to step 1.

     Step 3. If a = b, then a is the GCD of initial numbers.

     It's obvious, that after fulfilling of each step, the GCD of considered couple of numbers doesn't change. Every time after fulfilling step 2 the sum of considered couple of numbers decreases at least by 1, and the same time the numbers remain natural. All this shows, that sooner or later we will reach step 3. At the step 3 the GCD of the couple of equal numbers, obviously, is equal to each of these numbers. By force of the remark made above, it will be the GCD of the initial numbers.

     Let's denote initial numbers by a₀ and a₁, and besides consider, without breaking the community, that a₀ > a₁. Repeated use of step 2 is equivalent to dividing a₀ by a₁ :

a₀= a₁ q₁ + a₂, where 0 £ a₂ < a₁.

     If a₂ = 0, then the GCD(a₀, a₁) = a₁, otherwise use step 1 and change the places of a₁ and a₂. Continuing the same way we get one after another:

     At every step the GCD of the divident and divisor is equal to the GCD of the divisor and remainder. The last non-zero remainder a_nwill be the greatest common divisor of the initial numbers.