Question

What is Euclid's Division Algorithm?

Answer 1

Euclid's Division Algorithm:

• Euclid's Division Algorithm is a technique to compute the Highest Common Factor(HCF) of two given positive integers $a$ and $b$.
• Euclid's division lemma states that if $a$ and $b$are two positive integers then there exist $q$ and $r$ which satisfies the condition$a=bq+r$, where $0\le r<b$
• If $b$ completely divides $a$ then the remainder $r$ is zero. Otherwise, the condition will be $0<r<b$.

Thus, the Euclid division algorithm states that if $a$ and $b$ are two positive integers there exist $q$ and $r$ which satisfies the condition$a=bq+r$, where $0\le r<b$.