Question
Wed March 28, 2012 By: Pooja Anand
 

if a,b have hcf or gcd =d and d=ax+by then prove x and y as integers.pleas fast!!!!(with each and every step)please try to give the answer now!!!

Expert Reply
Thu March 29, 2012
In general, we use the following procedure to find the hcf:
 
divide (say) a by b to get remainder r1. Note that one can write r1 in terms of a and b.
 
Then divide b by r1 to get remainder r2. Note that one can write r2 in terms of b and r1 and hence in terms of a and b.
 
Repeat the process getting smaller and smaller remainders r1 , r2 , ... which must eventually lead to a remainder of 0.
 
At each stage ri can be expressed in terms of a and b. the last non-zero remainder d divides all the previous ones and hence both a and b. Hence it divides gcd(a, b). Since d can be written in terms of a and b the gcd(a, b) divides d and must therefore be d.
 
It can be seen that
 
a = p * d , b = q * d where p and q are integers so in the exuation ax + by = d , px + qy = 1 ,
Since p , q are integers , thus x, y can have an integral pair of opposite sign .
Related Questions
Wed October 26, 2016

please answer

Ask the Expert