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!!!

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
Mon May 29, 2017

Wed May 10, 2017

Home Work Help