If the hcf of 657 and 963 is expressible in the form 657x + 963*(-15) find x
657 and 963
By applying Euclid’s division lemma
963 = 657 × 1 + 306
Since remainder ≠ 0, apply division lemma on division 657 and remainder 306
657 = 306 × 2 + 45
Since remainder ≠ 0, apply division lemma on division 306 and remainder 45
306 = 45 × 6 + 36
Since remainder ≠ 0, apply division lemma on division 45 and remainder 36
45 = 36 × 1 + 19
Since remainder ≠ 0, apply division lemma on division 36 and remainder 19
36 = 19 × 4 + 0
∴ HCF = 657
Given HCF = 657 + 963 × (-15)
⇒ 9 = 657 × −1445
⇒ 9 + 14445 = 657 x
⇒ 657x = 1445y
⇒ x = 1445y/657
⇒ x = 22
Given numbers are 657 and 963 .Here, 657 < 963\xa0By using Euclid\'s Division algorithmm , we get963 = (657 × 1) + 306Here , remainder = 306 .So, On taking 657 as new dividend and 306 as the new divisor and then apply Euclid\'s Division lemma, we get657 = (306 × 2) + 45Here, remainder = 45\xa0So, On taking 306\xa0as new dividend and 45\xa0as the new divisor and then apply Euclid\'s Division lemma, we get306 = (45 × 6) + 36Here, remainder = 36So, On taking 45\xa0as new dividend and 36\xa0as the new divisor and then apply Euclid\'s Division lemma, we get45 = (36 × 1) + 9Here, remainder = 9So, On taking 36\xa0as new dividend and 9\xa0as the new divisor and then apply Euclid\'s Division lemma, we get36 = (9 × 4) + 0Here , remainder = 0 and last divisor is 9.\xa0Hence, HCF of 657 and 963 = 9.∴ 9 = 657x + 963(-15)⇒ 9 = 657x - 14445⇒ 657x = 9 + 14445⇒ 657x = 14454⇒x = 14454/657⇒ x =22