The Euclidean Algorithm

The greatest common divisor of two numbersandmay be found from the prime – power factorizations ofandare 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 numbersandwiththere exists a unique pair of integerscalled the quotient andcalled the remainder such thatwithMoreover,if and only ifdivides

Proof: Letbe the set of nonnegative integers given by This is a nonempty set of nonnegative integers so it has a smallest member, sayLetthen andNow we show thatAssumethenbut sincehenceis a member ofsmaller than it's smallest member,This contradiction shows thatThe pairis unique for if there were another such pair, saythen sohencedividesIfthen a contradiction thereforeandFinallyif and only ifdivides

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 wherelet 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

Thenthe last nonzero remainder in this process, isthe greatest common divisor of a and b.

Proof: There is a stage at whichbecause theare decreasing and nonnegative. The last relationshows thatdividesThe next to last shows thatdivides so by inductiondivides eachIn particularandsois a common divisor ofandLetbe any common divisor ofandThe definition ofshows that dividesthen the line below shows thatdividesso by inductiondivides eachso divideshence

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 numbersandas a linear combination ofand

For the example aboveandwe have from (3)

(4)

Rearrange (2) to giveand substitute into (4)

(5)

Rearrange (1) to giveand substitute into (5)

which rearranges to give