Question

036,
Use the Euclid's division
algorithm to find the HCF
of 612 and 1314,​

Answer 1

Answer: *We need to find the hcf by Euclid division lemma.

*So we need to consider the largest number first which is 1314.

*We know that according to Euclid Division Lemma, a = bq + r where 0 <=r <=b

*So 1314 = 612 x 2 + 90 (after dividing 1314 by 612 we get 2 as quotient and 90 as remainder)

* Here a = 1314, b = 612, q = 2, r = 90

*Similarly applying Euclid division Lemma we get

612 = 90 x 6 + 72

*Now consider divisor as 90 and remainder as 72 we get

90 = 72 x 1 + 18

*Again consider divisor as 72 and remainder as 18 we get

72 = 18 x 4 + 0

*Now remainder is zero and therefore b is the final step is 18 and so hcf of 612 and 1314 is 18.

OR  

612 ) 1314 (2

       1224

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

           90) 612 (6

                  540

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

                   72)90 (1

                         72

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

                         18 )72( 4

                               72

                           ----------

                                0