Question

write the euclids division algorithm for the numbers a and b.​

Answer 1

Answer:

We have seen that the said lemma is nothing but a restatement of the long division process which we have been using all these years. In this section, we will learn one more application of Euclids division lemma known as Euclids Division Algorithm.

An algorithm means a series of well defined steps which provide a procedure of calculation repeated successively on the results of earlier steps till the desired result is obtained.

Theorem : 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.

Proof : Let c be a common divisor of a and b. Then,

c| a ⇒ a = cq1 for some integer q1

c| b ⇒ b = cq2 for some integer q2.

Now, a = bq + r

⇒ r = a – bq

⇒ r = cq1 – cq2 q

⇒ r = c( q1 – q2q)

⇒ c | r

⇒ c| r and c | b

⇒ c is a common divisor of b and r.

Answer 2

⬇ᴀɴꜱᴡᴇʀ_

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.