Positive solution for linear Diophantine equations

pyfgcr

The linear Diophantine equations: ax+by=c, a,b,c is natural numbers.
If c is a multiple of gcd(a,b), there is infinite integer solutions, and I know how to find x,y.
However, I wonder how to find positive integer solution x,y only.

*DonAntonio*

Quote by pyfgcr

The linear Diophantine equations: ax+by=c, a,b,c is natural numbers.
If c is a multiple of gcd(a,b), there is infinite integer solutions, and I know how to find x,y.
However, I wonder how to find positive integer solution x,y only.

They may not exists. For example, the equation [itex]\,7x+6y=5\,[/itex] cannot have positive solutions, but it has

solutions, like [itex]\,(5,-6)\,[/itex]

DonAntonio

Mensanator

Shouldn't that be (5,-5)?

*DonAntonio*

Quote by Mensanator

Shouldn't that be (5,-5)?

Yes, you're right of course. Thanks.

DonAntonio

HallsofIvy

All solutions of the Diophantine equation ax+ by= c (assuming a, b, relatively prime) are of the form x= x₀+ kb, y= y₀- ka for k any integer. If you want both x and y positive, you must be able to choose k so that those are postive. Whether that is possible, of course, depends on a, b, x₀, and y₀.

Similar Threads for: Positive solution for linear Diophantine equations
Thread	Forum	Replies
Linear diophantine equations	Linear & Abstract Algebra	1
number theory - gcd and linear diophantine equations	Calculus & Beyond Homework	1
Linear algebra (impact of solution of theory of linear equations)	Calculus & Beyond Homework	2
Linear Diophantine Equations	Calculus & Beyond Homework	8
General solution to diophantine equations	Linear & Abstract Algebra	3

pyfgcr	Positive solution for linear Diophantine equations Tweet The linear Diophantine equations: ax+by=c, a,b,c is natural numbers. If c is a multiple of gcd(a,b), there is infinite integer solutions, and I know how to find x,y. However, I wonder how to find positive integer solution x,y only.

HallsofIvy Recognitions: Gold Member Science Advisor Staff Emeritus	All solutions of the Diophantine equation ax+ by= c (assuming a, b, relatively prime) are of the form x= x₀+ kb, y= y₀- ka for k any integer. If you want both x and y positive, you must be able to choose k so that those are postive. Whether that is possible, of course, depends on a, b, x₀, and y₀.