Solve the linear Diophantine equation

  • Thread starter Thread starter chwala
  • Start date Start date
  • Tags Tags
    Linear
chwala
Gold Member
Messages
2,827
Reaction score
415
Homework Statement
solve the linear diophantine equation ##259x+581y = 7##
Relevant Equations
euclidean algorithm
##259x+581y=7##
##581=259.2+63##
##259=63.4+7##
##63=7.9+0##
therefore by reversing...
##7=0.63+1.7##
##7=1.259-4.63###
##x=1## ##y=-4##
is this correct? Bingo
 
Physics news on Phys.org
chwala said:
##x=1## ##y=-4##
is this correct? Bingo
What happens when you substitute the solution back into the equation?
 
Also, never use a . to indicate multiplication. It makes things very hard to read.
 
  • Like
Likes Delta2
i think i figured it out...
##7=1×259-4×63##
##7=1×259-4(581-259×2)##
##7=259×9+581×-4##
on using the general form... we have
##x= 9+83m##
##y = -4-37m##
bingo bingo from Africa:smile:
 
  • Like
Likes Delta2
You may have saved some work if you divided through the first equation by 7. Notice condition for solution apply/exist.
 
WWGD said:
You may have saved some work if you divided through the first equation by 7. Notice condition for solution apply/exist.
can you show how? i have already posted the solution therefore an alternative method would be appreciated...
 
Last edited:
alternatively from my research you can have
##259x+581y=7##
gcd##(581,259)=7##
therefore dividing the diophantine equation by 7 we have
##83y+37x=1##
83/37= 2+ 1/{37/9}
= 2+ 1/{4+{1/9}}
= 2+ 1/4= 9/4 now assigning suitable change sign on the numerator and denominator we have
##83(-4)+37(9)=1##
 
chwala said:
can you show how? i have already posted the solution therefore an alternative method would be appreciated...
Sure, I was referring to the needed conditions for an integer solution for ## ax+by=c ## to exist. We need gcd(a,b)|c . Just for completeness.
 
There are few key ideas you need to know for linear diophantine equations:
(1)The Linear Diophantine Equation
aX+bY=1 has a solution iff gcd(a,b)=1.

(2) The Linear Diophantine Equation aX+bY=n has solution iff gcd(a,b)|n.

(3) Euclid's Lemma: Let D be gcd(a,b). Then the Linear Diophantine Equation aX+bY=D has a solution.

There are two more important results. Can you fill them in?
 
  • Like
Likes Delta2
  • #10
MidgetDwarf said:
There are few key ideas you need to know for linear diophantine equations:
(1)The Linear Diophantine Equation
aX+bY=1 has a solution iff gcd(a,b)=1.

(2) The Linear Diophantine Equation aX+bY=n has solution iff gcd(a,b)|n.

(3) Euclid's Lemma: Let D be gcd(a,b). Then the Linear Diophantine Equation aX+bY=D has a solution.

There are two more important results. Can you fill them in?
Thanks for your insight, i should be fine with the idea of solving the diophantine equations...
 
  • #11
Solving the Diophant Equation with Multiple Variables
https://abakbot.com/2019-03-12-19-33-47/diofn
Example
Original diophant equation
mathtex.png
A private solution to this equation
mathtex.png
 
  • Like
Likes Delta2
  • #12
DimsVS said:
Solving the Diophant Equation with Multiple Variables
https://abakbot.com/2019-03-12-19-33-47/diofn
Example
Original diophant equation
A private solution to this equation
how did you get your ##x## values?
 
  • #14
Did you notice that all three of 259, 581, and 7 are multiples of 7? The first thing I would do is divide by 7 to simplify to 37x+ 83y= 1. What I would now do is essentially what you did. 37 divides into 83 twice with remainder 9: 83- 2(37)= 9. 9 divides into 37 four times with remainder 1: 37- 4(9)= 1. Replacing "9" in that by "83- 2(37)" gives 37- 4(83- 2(37))= 9(37)- 4(83)= 1. Comparing that to "37x+ 83y= 1" we have x= 9 and y= -4. Of course then x= 9+ 83n and y= -4- 37n gives 37(9+ 83n)+ 83(-4- 37n)= 37(9)+ (37)(83n)- 83(4)- (37)(83n)= 1.
 
Back
Top