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.




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)


Rearrange (2) to giveand substitute into (4)


Rearrange (1) to giveand substitute into (5)

which rearranges to give

Add comment

Security code