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,
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.
Using Euclid's algorithm,
Since 158>57
57>44
44>13
13>5
5>3
3>2
Therefore, (158,57)=1
Now using reverse substitution,
Therefore,
The general solution,
Hope this will help you to understand Diophantine equations.