If the HCF of 657 and 963 is expressible in the form of 657a + 963b, find the values of a and b.
Answers
Answer: The value of a and b are 22 and -15 respectively.
Step-by-step explanation:
Objectives:
1. to find HCF(657,963).
2. to express HCF as a linear combination of 657 and 963.
Using Euclid's algorithm:
a= qb+r
=> 963= 657*1+306
=> 657=306*2+45
=> 306= 45*6+36
=> 45= 36*1+9
As 9 divides the last term 36, so HCF(657,963)= 9
To express HCF as a linear combination of 657 and 963, we need to run the Euclidean algorithm "backwards" for each steps:
9= 45-36*1
36= 306 - 45*6
45= 657-306*2
306= 963-657*1
Finally, we need to substitute the remainder into the previous equation as follow:
9= 45- (306 - 45*6)*1 ( putting the value of remainder-36)
= -306+7*45
= -306+7(657-306*2) ( putting the value of remainder-45)
= 7*657-15*306
= 7*657-15*(963-657*1) ( putting the value of remainder-306)
= 22*657-15*963
So, we get the HCF(657,963) as a linear combination of 657 and 963
9= 22*657 - 15*963
Equating the above expression with the form 657*a+963*b, we get
a= 22, and b= -15