Question

Find the HCF (306,657) using Euclid’s algorithm.
answer with step by step for class 10 ​

Answer 1

306, 657

Now, applying the Euclid Division Lemma. Then,

306⎞⎠⎟657612−−−045−−−¯¯¯¯¯¯¯¯¯¯¯¯¯¯2306)657612_045_¯2

Now, here b=657b=657 , a=306a=306 , q=2q=2 and r=45r=45 so, we can write 657=306×2+45657=306×2+45 .

Now, consider the divisor 306 and the remainder 45 and apply Euclid Division Lemma again. Then,

45⎞⎠⎟306270−−−036−−−¯¯¯¯¯¯¯¯¯¯¯¯¯¯645)306270_036_¯6

Now, here b=306b=306 , a=45a=45 , q=6q=6 and r=36r=36 , so we can write 306=45×6+36306=45×6+36 .

Now, consider the divisor 45 and the remainder 36 and apply Euclid Division Lemma again. Then,

36⎞⎠⎟4536−−09−−¯¯¯¯¯¯¯¯¯¯¯¯136)4536_09_¯1

Now, here b=45b=45 , a=36a=36 , q=1q=1 and r=9r=9 , so we can write 45=36×1+945=36×1+9 .

Now, consider the divisor 36 and the remainder 9 and apply Euclid Division Lemma again. Then,

9⎞⎠⎟3636−−00−−¯¯¯¯¯¯¯¯¯¯¯¯49)3636_00_¯4

Now, as we see that the remainder has become zero, therefore, proceeding further is not possible and hence the HCF is the divisor a=9a=9 left in the last step. And we can say that the HCF of 306 and 657 is 9.