Question

write a note on Euclid division Lemma

Answer 1

According to Euclid’s Division Lemma if we have two positive integers a and b, then there exist unique integers q and r which satisfies the condition a = bq + r where 0 ≤ r ≤ b.

The basis of the Euclidean division algorithm is Euclid’s division lemma. To calculate the Highest Common Factor (HCF) of two positive integers a and b we use Euclid’s division algorithm. HCF is the largest number which exactly divides two or more positive integers. By exactly we mean that on dividing both the integers a and b the remainder is zero.

Answer 2

Answer is given below.

Step-by-step explanation:

Write a note on Euclid division Lemma.

Definition:

                 Euclid's Division Lemma states that, if two positive integers “a” and “b”, then there exists unique integers “q” and “r” such that which satisfies the condition $a = bq + r$ where $0 \leq r \leq b$. ... In this example, $9$ is the divisor, $58$ is the dividend, $6$ is the quotient and $4$ is the remainder.

Example:

Find the HCF of $81$ and $675$ using the Euclidean division algorithm.

Solution:

The larger integer is $675$, therefore, applying the Division Lemma $a = bq + r$where $a = bq + r$, we have

$a=675$ and $b=81$

⇒$675 = 81\times8 + 27$

Applying the Euclid’s Division Algorithm again we have,

$81 = 27\times3 + 0$

We cannot proceed further as the remainder becomes zero. According to the algorithm divisor, in this case, is $27$ which is the HCF of  $675$ and $81$.