Question

# Find the HCF of the following pairs of integers and express it as a linear combination of them.

A
963 and 657
Right on! Give the BNAT exam to get a 100% scholarship for BYJUS courses
B
592 and 252
No worries! We‘ve got your back. Try BYJU‘S free classes today!
C
506 and 1155
No worries! We‘ve got your back. Try BYJU‘S free classes today!
D
1288 and 575
No worries! We‘ve got your back. Try BYJU‘S free classes today!
Open in App
Solution

## The correct option is A 963 and 657To express HCF (of 963 and 657) as a linear combination of them means HCF = 963x + 657y. Using Euclid Division Lemma we get HCF as 9. 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 ∴ HCF (657, 963)=9. Now we have to express 9 as a linear combination of 963 and 657. 9 = 963x + 657y. To do this we have to use the relations obtained in finding the HCF using Euclid Division Lemma. 9= 45-36(1) (From 2nd lost step of finding HCF) =45–(306−45×6) (from 3rd step of finding HCF) =45−306+45×6 9=45×7−306 9=45×7−306 But 45=657−306×2 (From 4th last step) ∴ 9=(657−306×2)7−306 =657×7−306×14−306 9=657×7−306×15 But 306=963-657 (From 1st step of finding HCF) ∴ 9=657×7−(963−657)15 =657×7−963×15+657×15 =657×22−963×15 ∴9=(−15)963+22(657)=963x+657y. X=-15, y=22

Suggest Corrections
7
Join BYJU'S Learning Program
Related Videos
Permutations
MATHEMATICS
Watch in App
Join BYJU'S Learning Program