Do diophantine equations ax+by =C with gcd (a,b) = 1 have a solution?
Consider the following diophantine equations
30x + 17y = 30
158x-57y=7
gcd of both these equations are 1. So does that mean these equations have no solution?
Do diophantine equations ax+by =C with gcd (a,b) = 1 have a solution?
Consider the following diophantine equations
30x + 17y = 30
158x-57y=7
gcd of both these equations are 1. So does that mean these equations have no solution?
Dear mlsbbe,
The diaphantine equation, $\displaystyle ax+by=c$ have solutions iff $\displaystyle (a,b)\mid{c}$. So in your case (a,b)=1 and since $\displaystyle 1\mid{c},~ ax+by=c $ have solutions.
Therefore 30x + 17y = 30 and 158x-57y=7 have solutions.
Hope this helps.
Dear mlsbbe,
First of all (a,b)=d (the greatest common divisor of a and b is d) means the greatest positive integer that divides both a and b is d. Therefore by definition the greatest common divisor is always positive.
When finding the greatest common divisor and the general solution to a Diophantine equation use the method I have given below.
$\displaystyle 158x-57y = 7$
Using Euclid's algorithm,
Since 158>57
$\displaystyle 158=(57\times{2})+44$
57>44
$\displaystyle 57=(44\times{1})+13$
44>13
$\displaystyle 44=(13\times{3})+5$
13>5
$\displaystyle 13=(5\times{2})+3$
5>3
$\displaystyle 5=(3\times{1})+2$
3>2
$\displaystyle 3=(2\times{1})+1$
Therefore, (158,57)=1
Now using reverse substitution,
$\displaystyle 1=3-2$
$\displaystyle 1=3-(5-3)=-5+(2\times{3})$
$\displaystyle 1=-5+2{13-(5\times{2})}=(-5\times{5})+(2\times{13})$
$\displaystyle 1=(2\times{13})-5[44-(13\times{3})]=(17\times{13})-(5\times{44})$
$\displaystyle 1=(-5\times{44})+17[57-44]=(-22\times{44})+(17\times{57})$
$\displaystyle 1=(17\times{57})-22[158-(57\times{2})]=(61\times{57})-(22\times{158})$
$\displaystyle 7=(158\times{(-22\times7)})-(57\times{(-61\times{7})})$
Therefore, $\displaystyle x=-154~and~y=-427~is~a~particular solution.$
The general solution,
$\displaystyle x=-154-57t~and~y=-427-158t~;~t\in{Z}$
Hope this will help you to understand Diophantine equations.