Question

what is Euclid's division algorithm?​

Answer 1

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.


#bts army

Answer 2

Answer:

Euclid Division Algorithm :-

Let a and b are any two positive integers , there exits a unique pair of integers q and r satisfying

a = b q + r

Where

a > b , 0 ≤ r < b

◆ By Euclid Division algorithm we can find HCF of any two positive integers .

Example :-

Find the HCF of 15 and 35 by Euclid Division Algorithm .

Step 1 :-

Let

a = 35 b = 15

By Euclid Division algorithm

a = b q + r

35 = 15 × 2 + 5

Now divide 35/ 15

Step 2 :-

Let

a = 15 b = 5

By Euclid Division Algorithm

15 = 5 × 3 + 0

Therefore , the Remainder ( r ) = 0 then ,

HCF = 5