Question

What do you mean by Euclid's division
algorithm.

Answer 1

Euclid's Division Algorithm (Lemma)

We know that how to divide a positive integer 'a' by another positive integer 'b' by long division method.

Let us consider a = 217 , b = 5 and make the division of 217 by 5 as under :

Dividend

↓

Divisor → 5)217(43 ← Quotient

20

--------

17

15

-----

2 ←Remainder

Clearly, 217 = 5 x 43 + 2

i, e.,

Dividend = Divisor × Quotient + Remainder

Let us consider some more pairs of integers as given below :

(i). a = 191; b = 2; 191 = 2 x 95 + 1

(ii).a = 321; b = 3; 321 = 3 x 107+0

(iii).a = 205; b = 7; 205 = 7 x 29 + 2

(iv). a = 1047; b = 11; 1047=11 x 95+ 2

From the above, we conclude that for each pair of positive integers, a and b, there exists a pair of whole numbers q and r such that a = b × q + r, 0 ≤ r < b, where6q = quotient and r = remainder.

Formal statement of Euclid's Division Lemma

For any two given positive integers a and b, there exist unique integers q and r such that a = bq + r, 0 ≤ r < b, where a = dividend, b = divisor, q = quotient and r = remainder.

Brainly Extra Knowledge

• Euclid's division Lemma and algorithm are so closely interlinked that people often called former as the division algorithm also.

• Although euclid's division algorithm is state for only positive integers, it can be extended for all integers except zero, i.e., b ≠ 0.

Answer 2

Step-by-step explanation:

If p(x) and g(x) are two

polynomials with

g(x) ≠ 0,

then-

p(x) = g(x) x q(x) + r(x)

where,

r(x) = 0 or degree of r(x) < degree of g(x)