Suppose that gcdab1 Prove that for every integer c the equat

Suppose that gcd(a,b)=1. Prove that for every integer c, the equation ax+by=c has a solution in integers x and y. [Hint: Find a solution to au+bv=1 and multiply by c]

Find a solution to 37x + 47y = 103. Try to make x and y as small as possible

Solution

Since, gcd(a,b)=1 so by Euclid algorithm we can find u,v so that

au+bv=1

Multipluying by c gives

a(cu)+b(cv)=c

SO, x=cu,y=cv

gcd(37,47)=1

Now let\'s apply Euclid Algorithm

47=37+10 , 10=47-37

37=10*3+7, 7=37-10*3=37-3(47-37)=4*37-3*47

10=7+3, 3=10-7=47-37-4*37+3*47=-5*37+4*47

7=2*3+1   , 1=7-2*3=4*37-3*47-2*(-5*37+4*47)=14*37-11*47

SO,

1=14*37-11*47

Note that:14+47m,-11+37m, where m is any integer is also a solution

(14+47m)37-(11+37m)47=14*37-11*37+47*37m-37*47m=1

MUltiplying by 103 gives

103=103(14+47m)37-103(11+37m)47

So, x=103(14+47m),y=-103(11+37m)

For smallest x,y let m=0

So, x=103*14,y=-103*11