What is the difference between Euclid's division lemma and Euclid's division algorithm?

Question

My textbook claims that Euclid's division algorithm depends upon Euclid's division lemma but can you elaborate?

Answer 1

Euclid's Division Lemma states: for $a$, $b\in\mathbb{Z}$, $b\ne0$, there exist unique $q$, $r\in\mathbb{Z}$ such that $$a=qb+r, \qquad 0\le r<|b|\tag{$\star$}$$
We call $q$ the quotient, and $r$ the remainder. The lemma itself can be proved by induction on $a$. Euclid's Division Algorithm is an algorithm to find the greatest common divisor ($\gcd$) of two natural numbers facilitated by repeated use of the Division Lemma until in the last use of $(\star)$ we get a zero remainder and the process terminates with the $\gcd$ given by the last non-zero remainder. Each time the Division Lemma is invoked in the Division Algorithm, the new $a$ and $b$ are the preceding steps $b$ and $r$ respectively.

For example to find $\gcd(267,126)$ the Division Algorithm takes four steps to get to a zero-remainder, each step a usage of the Division Lemma:

• Step 1: Find the remainder when $267$ is divided by $126$. By Euclid's Division Lemma with $a_1=267$, $b_1=126$, we have $$267=2\times126+15\tag{1}$$ and so $q_1=2$, $r_1=15$.

• Step 2: Find the remainder when $126$ is divided by $15$. By Euclid's Division Lemma with $a_2=126$, $b_2=15$, we have $$126=8\times15+6\tag{2}$$ and so $q_2=8$, and $r_2=6$.

• Step 3: Find the remainder when $15$ is divided by $6$. By Euclid's Division Lemma with $a_3=15$, $b_3=6$, we have $$15=2\times6+3\tag{3}$$ and so $q_3=2$, $r_3=3$.

• Step 4: Find the remainder when $6$ is divided by $3$. By Euclid's Division Lemma with $a_4=6$, $b_4=3$, we have $$6=2\times3+0\tag{4}$$ and so $q_4=2$, $r_4=0$. Here the Division Algorithm terminates since $r_4=0$, and $\gcd(267,126)=r_3=3$ is the last non-zero remainder from Step 3.

Answer 2

Putting it simply,

Euclid's Division Lemma is the statement that any non negative integer $n$ can be expressed in $n=aq+b$ form where $0\leq b<q$.

Division algorithm is a method to compute the Greatest Common Divisor of two numbers which is based on repeated application of Euclid's Divsion Lemma until the remainder comes out to be $0$.