Find the HCF of 963 and 657 using euclid division lemma.
Answers
Using Euclid’s Division Lemma
a = bq+r , o ≤ r < b
963 = 657×1 + 306
657 = 306×2 + 45
306 = 45×6+36
45 = 36×1+9
36 = 9×4+0
∴ HCF (657, 963) = 9.
Step-by-Step-explanation :-
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.
Final Answer :-
Hence, H.C.F of ( 657, 963 ) is 9.
Additional Information :-
★ EUCLID'S DIVISION LEMMA ★
➩Euclid's Division Lemma states that for any two positive integers a and b, there exists unique integers q and r such that a = bq + r where r must satisfy 0 ≤ r < b