Question

Q state Euclid's division
algori
them?
​

Answer 1

Answer:

Step-by-step explanation:

This was aa algorithm discovered by Euclid to calculate the highest common factor (hcf)of numbers .

HCF of two positive integers a and b is the largest positive integer d that divides both a and b.

Hope this helps .

Please mark me as the brainliest .

Thank you :):)

Answer 2

             Euclids Division Algorithm

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.

Hence, a common divisor of a and b is a common divisor of b and r.

Euclids Division Algorithm is a technique to compute the Highest Common Factor (HCF) of two given positive integers. Recall that the HCF of two positive integers a and b is the largest positive integer d that divides both a and b.

--------------------------------------------------------------------------------------------------------------

To obtain the HCF of two positive integers, say c and d, with c > d, follow the steps below:

Step 1 : Apply Euclid’s division lemma, to c and d. So, we find whole numbers, q and r such that c = dq + r, 0 ≤ r < d.

Step 2 : If r = 0, d is the HCF of c and d. If r ≠ 0, apply the division lemma to d and r.

Step 3 : Continue the process till the remainder is zero. The divisor at this stage will be the required HCF.

This algorithm works because HCF (c, d) = HCF (d, r) where the symbol HCF (c, d) denotes the HCF of c and d, etc.

Hope it helps u plz mark me as a brainlister!!!!!

and follow me!!!!!