PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (210)
Orphanage
Unclass'd (1)
Unproven (473)
Corrections (37)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Low Entry average rating: Very high
Euclid's algorithm (Algorithm)

Euclid's algorithm describes a procedure for finding the greatest common divisor of two integers.

Suppose $ a,~b \in \mathbb{Z}$, and without loss of generality, $ b > 0$, because if $ b < 0$, then $ \gcd(a,b) = \gcd (a, \vert b\vert )$, and if $ b = 0$, then $ \gcd (a,b) = \vert a\vert $. Put $ d := \gcd (a,b)$.

By the division algorithm for integers, we may find integers $ q$ and $ r$ such that $ a = q_0 b + r_0 $ where $ 0 \leq r_0 < b$.

Notice that $ \gcd(a,b) = \gcd(b, r_0)$, because $ d \mid a$ and $ d \mid b$, so $ d \mid r_0 = a - q_0b$ and if $ b$ and $ r_0$ had a common divisor $ d'$ larger than $ d$, then $ d'$ would also be a common divisor of $ a$ and $ b$, contradicting $ d$'s maximality. Thus, $ d = \gcd(b, r_0)$.

So we may repeat the division, this time with $ b$ and $ r_0$. Proceeding recursively, we obtain

$\displaystyle a$ $\displaystyle =$ $\displaystyle q_0b + r_0 ~$ with $\displaystyle 0 \leq r_0 < b$  
$\displaystyle b$ $\displaystyle =$ $\displaystyle q_1r_0 + r_1$    with $\displaystyle 0 \leq r_1 < r_0$  
$\displaystyle r_0$ $\displaystyle =$ $\displaystyle q_2r_1 + r_2$    with $\displaystyle 0 \leq r_2 < r_1$  
$\displaystyle r_1$ $\displaystyle =$ $\displaystyle q_3r_2 + r_3$    with $\displaystyle 0 \leq r_3 < r_2$  
  $\displaystyle \vdots$    

Thus we obtain a decreasing sequence of nonnegative integers $ b > r_0 > r_1 > r_2 > \dots$, which must eventually reach zero, that is to say, $ r_n = 0$ for some $ n$, and the algorithm terminates. We may easily generalize the previous argument to show that $ d = \gcd(r_{k-1}, r_k) = \gcd(r_k, r_{k+1})$ for $ k = 0, 1, 2, \dots$, where $ r_{-1} = b$. Therefore,
$\displaystyle d = \gcd(r_{n-1}, r_n) = \gcd(r_{n-1}, 0) = r_{n-1}.$
More colloquially, the greatest common divisor is the last nonzero remainder in the algorithm.

The algorithm provides a bit more than this. It also yields a way to express the $ d$ as a linear combination of $ a$ and $ b$, a fact obscurely known as Bezout's lemma. For we have that

$\displaystyle a -q_0b$ $\displaystyle =$ $\displaystyle r_0$  
$\displaystyle b -q_1r_0$ $\displaystyle =$ $\displaystyle r_1$  
$\displaystyle r_0 - q_2r_1$ $\displaystyle =$ $\displaystyle r_2$  
$\displaystyle r_1 - q_3r_2$ $\displaystyle =$ $\displaystyle r_3$  
  $\displaystyle \vdots$    
$\displaystyle r_{n-3} - q_{n-1}r_{n-2}$ $\displaystyle =$ $\displaystyle r_{n-1}$  
$\displaystyle r_{n-2}$ $\displaystyle =$ $\displaystyle q_nr_{n-1}$  

so substituting each remainder $ r_k$ into the next equation we obtain
\begin{table} % latex2html id marker 133 \begin{displaymath} \begin{array}{ccccc... ...=& k_{n-1} a + l_{n-1} b &=& r_{n-1} \ \end{array}\end{displaymath}\end{table}

Sometimes, especially for manual computations, it is preferable to write all the algorithm in a tabular format. As an example, let us apply the algorithm to $ a=756$ and $ b=595$. The following table details the procedure. The variables at the top of each column (without subscripts) have the same meaning as above. That is to say, $ r$ is used for the sequence of remainders and $ q$ for the corresponding sequence of quotients. The entries in the $ k$ and $ l$ columns are obtained by multiplying the current values for $ k$ and $ l$ by the $ q$ in this row, and subtracting the results from the $ k$ and $ l$ in the previous row.


\begin{table} % latex2html id marker 157 \begin{displaymath} \begin{array}{c@{~\... ... 14 \ 7 & 2 & 37 & -47 \ 0 & & & \ \end{array}\end{displaymath}\end{table}

Thus, $ gcd(756, 595) = 7$ and $ 37 \cdot 756 - 47 \cdot 595 = 7$.

Euclid's algorithm was first described in his classic work Elements (see propositions VII 1 and VII 2), which also contained procedures for geometrical constructions. These are the first known formally described algorithms. Prior to this, informally defined algorithms were in common use to perform various computations, but Elements contained the first attempt to rigorously describe a procedure and explain why its results are admissible. Euclid's algorithm for greatest common divisor is still commonly used today; since Elements was published in the fourth century BC, this algorithm has been in use for nearly 2400 years!



"Euclid's algorithm" is owned by rmilson. [ full author list (4) | owner history (3) ]
(view preamble)

View style:

See Also: Bezout's lemma (number theory), Euclidean domain

Other names:  Euclidean algorithm

Attachments:
Euclid's coefficients (Algorithm) by pahio
Log in to rate this entry.
(view current ratings)

Cross-references: admissible, contained, propositions, row, current, quotients, subscripts, column, variables, equation, Bezout's lemma, linear combination, remainder, argument, algorithm, eventually, sequence, decreasing, division, divisor, division algorithm for integers, without loss of generality, integers, greatest common divisor
There are 25 references to this entry.

This is version 17 of Euclid's algorithm, born on 2001-11-17, modified 2007-06-28.
Object id is 939, canonical name is EuclidsAlgorithm.
Accessed 26900 times total.

Classification:
AMS MSC: 11A05 (Number theory :: Elementary number theory :: Multiplicative structure; Euclidean algorithm; greatest common divisors)
Pending Errata and Addenda
None.
[ View all 6 ]
Discussion
Style: Expand: Order:
forum policy
Oops. I feel a bit like a thief by NeuRet on 2002-05-27 11:55:27
I think it was a rash decision of mine to adopt this object. My approach to the Euclidean algorithm would be entirely different, so I would completely rewrite this entry, proving its O(log n) complexity and accepting Logan's suggestion of showing why consecutive Fibonacci numbers are the worst case. I don't know when I'll do this, probably within the next two days.
[ reply | up ]
Interact
post | correct | update request | add example | add (any)