# Solve the linear Diophantine equation

#### chwala

Gold Member
Problem 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

Related Calculus and Beyond Homework News on Phys.org

#### DrClaude

Mentor
$x=1$ $y=-4$
is this correct? Bingo
What happens when you substitute the solution back into the equation?

#### DrClaude

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

#### chwala

Gold Member
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

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

#### chwala

Gold Member
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:

#### chwala

Gold Member
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

Science Advisor
Gold Member
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?

### Want to reply to this thread?

"Solve the linear Diophantine equation"

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