Question

If the hcf of 657 and 963 is expressible in the form of 657 x and 963 y . find x and y

Answer 1

According to Euclid's division lemma

a=bq+r, 0<=r<b

963=657*1+306

657=306*2+45

306=45*6+36

45=36*1+9

36=9*4+0

9=[45-(36*1)]

9=[45-{306-(45*6)}*1]

9=[45-(306*1)+(45*6)]

9=[{657-(306*2)}*(6+1)-306*1]

9=[657*7-306*14-306*1]

9=[657*7-306*15]

9=[657*7-{963-(657*1)}*15]

9=[657*7-963*15+657*15]

9=[657*22-963*15]

9=657x+963y

x = 22, y = (-15)