Positive solution for linear Diophantine equations

  • Thread starter pyfgcr
  • Start date
22
0
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.
 
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
 
Shouldn't that be (5,-5)?
 

HallsofIvy

Science Advisor
Homework Helper
41,639
837
All solutions of the Diophantine equation ax+ by= c (assuming a, b, relatively prime) are of the form x= x0+ kb, y= y0- 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, x0, and y0.
 

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads

Top