Eukidean Algorithm

This Algorithm calculates the greatest common divisor of two
whole number a and b.

All the numbers in the following (or variables) shall be
whole number like 0,1,2,3,4,... or -1,-2,-3,...
We say a number a divides a number b - in symbols a|b -
if there is a another positive number k so that b = a*k (of course then
also k|b).
If a|b then a is a factor of b.

We say a number d is a common divisor of numbers a and b,
if d|a and d|b, i.e. d sticks as a factor of in a as well
as in b.

Observation (A)

If d is a common divisor of a,b then
d divides also (a+b).

Proof.

Since d|a and d|b there are numbers k₁, k₂
with a=d*k₁ and b=d*k₂ so
a+b = d*k₁ + d*k₂ = d*(k₁+k₂) and
and therefore d|(a+b) q.e.d.

Observation (B)

If d|a and d|b then
d divides also (a*q+b) where
q is a arbitrary number.

Proof.

Since d|a there is a number k
with a = d*k. And therefore
a*q = d*(k*q).
This means that d|(a*q)
and we can apply observation (A). q.e.d.


A number g is called the greatest common divisor of numbers
a and b - in symbols g=gcd(a,b) -, if g is a common divisor
of a and b AND EVERY other common divisor d of a and b divides g, i.e.
g has as factors EVERY other common divisor
Example: Consider 24 = 2*2*2*3, 36 = 2*2*3*3
common divisors of 24 and 36 are:
2, 4, 6, 12.
And 12 is the greatest common divisor because
the other common divisors 2,4,6 all divide 12.
Conversely 6 could not be the greatest common
divisor of 24 and 36 because the other common
divisor 12 does NOT divide 6.

Before we come to the actual algorithm we need to remind
ourselves what division with remainder is:
13/5 = 2 remainder 3, that means in product notation
13 = 5*2 + 3 , where 3<5, i.e. the rest is smaller then
the divisor but still positive

Descri ption of the Euklidean Algorithm

Then division of a by b with remainder r is
a = b*k + r with rThe following euklidean Algorithm of
two number a,b - where a>b - consist
of a series of division with remainder in product form:
Let p(1)=a and p(2)=b.

p(1) = p(2)*k(1) + p(3) with p(3)p(2) = p(3)*k(2) + p(4) with p(4)p(3) = p(4)*k(3) + p(5) with p(5). . .
. . .
. . .
. . .
p(n-1) = p(n)*k(n-1) + p(n+1) with p(n+1)p(n) = p(n+1)*k(n) + 0. (I5)
The Algorithm stops, if the remainder is 0.
Then the last remainder p(n+1) is the greatest
common divisor (GCD) of a and b.


Example: We consider the two numbers p1=36 and p2=24
36 = 24*1 + 12 with 12<24
24 = 12*2 + 0
Therefore 12 is the greatest common divisor of 24 and 36.

Another example: p(1)=2520 p(2)=540
2520 = 1980*1 + 540
1980 = 540*3 + 360
540 = 360*1 + 180
360 = 180*1 + 0

Therefore 180 is the greatest common divisor of
2520 and 540.

Now we want to prove that the euklidean algorithm
is well defined i.e. calculates the greatest
common divisor.

Proof.

1) The Algorithm stops after a finite number of steps.
The s-th step of this algorithm looks like
p(s) = p(s+1)*k(s) + p(s+2) with p(s+2)