CameraIcon
CameraIcon
SearchIcon
MyQuestionIcon
MyQuestionIcon
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 657
To 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,0r<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(30645×6) (from 3rd step of finding HCF)
=45306+45×6
9=45×7306
9=45×7306
But 45=657306×2 (From 4th last step)
9=(657306×2)7306
=657×7306×14306
9=657×7306×15
But 306=963-657 (From 1st step of finding HCF)
9=657×7(963657)15
=657×7963×15+657×15
=657×22963×15
9=(15)963+22(657)=963x+657y.
X=-15, y=22

flag
Suggest Corrections
thumbs-up
7
Join BYJU'S Learning Program
similar_icon
Related Videos
thumbnail
lock
Permutations
MATHEMATICS
Watch in App
Join BYJU'S Learning Program
CrossIcon