Solve the linear Diophantine equation

[chwala]

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

 

[DrClaude]

$x=1$ $y=-4$
is this correct? Bingo

What happens when you substitute the solution back into the equation?

 

[DrClaude]

Also, never use a . to indicate multiplication. It makes things very hard to read.

 

[chwala]

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

 

[WWGD]

You may have saved some work if you divided through the first equation by 7. Notice condition for solution apply/exist.

 

[chwala]

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...

 

[chwala]

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$

 

[WWGD]

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.

 

[MidgetDwarf]

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?

 

[chwala]

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...

 

[DimsVS]

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

 

[chwala]

Solving the Diophant Equation with Multiple Variables
https://abakbot.com/2019-03-12-19-33-47/diofn
Example

Original diophant equation

View attachment 250094​

A private solution to this equation

View attachment 250095​

how did you get your $x$ values?

 

[DimsVS]

new link

Solving the Diophant Equation with Multiple Variables

 

[HallsofIvy]

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.