Positive solution for linear Diophantine equations


by pyfgcr
Tags: diophantine, equations, linear, positive, solution
pyfgcr
pyfgcr is offline
#1
Nov27-12, 06:28 PM
P: 22
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.
Phys.Org News Partner Mathematics news on Phys.org
Math modeling handbook now available
Hyperbolic homogeneous polynomials, oh my!
Researchers help Boston Marathon organizers plan for 2014 race
DonAntonio
DonAntonio is offline
#2
Nov27-12, 07:08 PM
P: 606
Quote Quote by pyfgcr View Post
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
Mensanator is offline
#3
Nov29-12, 12:40 AM
P: 105
Shouldn't that be (5,-5)?

DonAntonio
DonAntonio is offline
#4
Nov29-12, 05:40 AM
P: 606

Positive solution for linear Diophantine equations


Quote Quote by Mensanator View Post
Shouldn't that be (5,-5)?

Yes, you're right of course. Thanks.

DonAntonio
HallsofIvy
HallsofIvy is offline
#5
Nov29-12, 08:08 AM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 38,900
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.


Register to reply

Related Discussions
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