Question

how to find a hcf using Euclid's division algorithm with example step by step.... ​

Answer 1

Answer:

The largest positive integer which divides two or more integers without any remainder is called (Highest Common Factor) (HCF)

Explanation:

We can find the [HCF] of two numbers using Euclid division algorithm

Euclids division algorithm is based on Euclids division lemma According to this the {HCF} of any two positive integer a and b with a> b is obtained as follow:

• Step 1:- apply the division lemma to find q and r where a=bq+r0<- r<
• step 2:- if r= 0 the HCF is b if r is not equal to 0, apply Euclids lemma to b and r
• step 3 :- continue the process till the remainder is zero The divisor at this stage will be the HCF of a and b