The diophantine equation ax+by=c has solutions if and only if gcd(a,b)|c. If so, it has infinitely many solutions, and any one solution can be used to generate all the other ones.
To see this, note that the greatest common divisor of a and b divides both ax and by, hence divides c if there is a solution. This gives the necessity of the condition (which you have backwards). (fixed in edits)
The converse is actually a constructive proof, that you can find in pretty much every elementary number theory course or book, and which is essentially the same as yunone's answer above (but without dividing through first).
From the Extended Euclidean Algorithm, given any integers a and b you can find integers s and tsuch that as+bt=gcd(a,b); the numbers s and t are not unique, but you only need one pair. Once you find s and t, since we are assuming that gcd(a,b) divides c, there exists an integer k such that gcd(a,b)k=c. Multiplying as+bt=gcd(a,b) through by k you get
a(sk)+b(tk)=gcd(a,b)k=c.
So this gives one solution, with x=sk and y=tk.
Now suppose that ax1+by1=c is a solution, and ax+by=c is some other solution. Taking the difference between the two, we get
a(x1−x)+b(y1−y)=0.
Therefore, a(x1−x)=b(y−y1). That means that a divides b(y−y1), and therefore agcd(a,b)divides y−y1. Therefore, y=y1+ragcd(a,b) for some integer r. Substituting into the equation a(x1−x)=b(y−y1) gives
a(x1−x)=rb(agcd(a,b))
which yields
gcd(a,b)a(x1−x)=rba
or x=x1−rbgcd(a,b).
Thus, if ax1+by1=c is any solution, then all solutions are of the form
x=x1−rbgcd(a,b),y=y1+ragcd(a,b)
exactly as yunone said.
To give you an example of this in action, suppose we want to find all integer solutions to
258x+147y=369.
First, we use the Euclidean Algorithm to find gcd(147,258); the parenthetical equation on the far right is how we will use this equality after we are done with the computation.
25814711136=147(1)+111=111(1)+36=36(3)+3=3(12).(equivalently, 111=258−147)(equivalently, 36=147−111)(equivalently, 3=111−3(36))
So gcd(147,258)=3. Since 3|369, the equation has integral solutions.
Then we find a way of writing 3 as a linear combination of 147 and 258, using the Euclidean algorithm computation above, and the equalities on the far right. We have:
3=111−3(36)=111−3(147−111)=4(111)−3(147)=4(258−147)−3(147)=4(258)−7(147).
Then, we take 258(4)+147(−7)=3, and multiply through by 123; why 123? Because 3×123=369. We get:
258(492)+147(−861)=369.
So one solution is x=492 and y=−861. All other solutions will have the form
xy=492−147r3=492−49r,=−861+258r3=86r−861,r∈Z.
You can reduce those constants by making a simple change of variable. For example, if we let r=t+10, then
xy=492−49(t+10)=2−49t,=86(t+10)−861=86t−1,t∈Z.
index.xml