Question

1. What do you mean by Euclid's division algorithm or Euclid's division Lemma theorem ? Explain with example.​

Answer 1

Step-by-step explanation:

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. ... That means, on dividing both the integers a and b the remainder is zero. Let us now get into the working of this Euclidean algorithm.

If a and b are positive integers such that a=bq+r, then every common divisor of a and b is a common divisor of b and r, and vice-versa. 

Example: Find HCF of 420 and 130.

Since 420>130 we apply the division lemma to 420 and 130 to get ,Since 300 , we apply the division lemma to 130 and 30 to get 

130=30×4+10

420=130×3+30 

Since 100 , we apply the division lemma to 30 and 10 to get 

30=10×3+0

The remainder has now become zero, so our procedure stops. Since the divisor at this step is 10, the HCF of 420 and 130 is 10. 

Answer 2

Step-by-step explanation:

A division algorithm is an algorithm which, given two integers N and D, computes their quotient and/or remainder, the result of Euclidean division. Some are applied by hand, while others are employed by digital circuit designs and software. ... Variants of these algorithms allow using fast multiplication algorithms