Question

Find the hcf of 657, 963 by euclid division algoritham method?

Answer 1

Given:- Two numbers i.e. 657 and 963.

To Find:- The HCF of 657 & 963 by the Euclid division algorithm.

Solⁿ:- We know the Euclid division algorithm is expressed in the form:

$a = b \times q + r$

where a= Dividend , b= divisior , q= quotient and r= remainder.

Now,

→963= 657 × 1 + 306

→657=306 ×2 +45

→306=45 ×6 +36

→45= 36 ×1 +9

→36= 9 ×4 +0

Thus, HCF of 657 & 963 is 9.

Answer 2

★ By using Euclid's division algorithm (a = b × q + r)

Step 1 :

657) 963 ( 1

657

-----------

306

963 = 657 × 1 + 306

Step 2 : As remainder is 306 which is not zero. so, now will take 306 as divisor and 657 as dividend.

306) 657 ( 2

612

---------

45

657 = 306 × 2 + 45

Step 3 : As remainder 45 which is not zero. Hence, now will take 45 as divisor and 306 as dividend.

45 ) 306 ( 6

270

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

36

306 = 45 × 6 + 36

Step 4 : Now ,we consider the divisor 45 as dividend and the remainder 36 as divisor.

36) 45 ( 1

36

-----------

9

45 = 36 × 1 + 9

Step 5 : Now ,we consider the divisor 36 as dividend and the remainder 9 as divisor.

9) 36 ( 4

36

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

0

36 = 9 × 4 + 0

Finally , We get a remainder as 0.

Hence, H.C.F of ( 657, 963 ) is 9.