## The Euclidean Algorithm

The greatest common divisor of two numbers and may be found from the prime – power factorizations of and are known. Considerable computing power may be needed to find the prime power factorizations however and there is a procedure – Euclid's algorithm - that requires less computation.

We need the following theorem

Theorem 1 The Division Algorithm

Given two numbers and with there exists a unique pair of integers called the quotient and called the remainder such that with Moreover, if and only if divides Proof: Let be the set of nonnegative integers given by This is a nonempty set of nonnegative integers so it has a smallest member, say Let then and Now we show that Assume then but since hence is a member of smaller than it's smallest member, This contradiction shows that The pair is unique for if there were another such pair, say then so hence divides If then a contradiction therefore and Finally if and only if divides The above theorem gives us a method for finding q and r. We subtract from or add to a enough multiples of b until we have found the sammlest nonnegative number of the form a-bx.

Theorem 2 The Euclidean Algorithm

Given positive integers a and b where let r-0 =a and r-1 =b and apply the division algorithm repeatedly to obtain a set of remainders r-2 , r-3 , ..., r-n , r-{n+1} defined recursively by the relations     Then the last nonzero remainder in this process, is the greatest common divisor of a and b.

Proof: There is a stage at which because the are decreasing and nonnegative. The last relation shows that divides The next to last shows that divides so by induction divides each In particular and so is a common divisor of and Let be any common divisor of and The definition of shows that divides then the line below shows that divides so by induction divides each so divides hence Example: Find the greatest common divisor of 19 and 7. (1) (2) (3) The greatest common divisor of 19 and 7 is thus 1.

We can use the Euclidean algorithm to write the greatest common divisor of two numbers and as a linear combination of and For the example above and we have from (3) (4)

Rearrange (2) to give and substitute into (4) (5)

Rearrange (1) to give and substitute into (5) which rearranges to give  