What is the difference between Euclid's division lemma and Euclid's division algorithm? My textbook claims that Euclid's division algorithm depends upon Euclid's division lemma but can you elaborate?
 A: 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.
A: 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$.
