• Support PF! Buy your school textbooks, materials and every day products via PF Here!

Solve the linear Diophantine equation

  • Thread starter chwala
  • Start date

chwala

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

DrClaude

Mentor
6,817
2,937

DrClaude

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

chwala

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

WWGD

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

chwala

Gold Member
488
26
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
488
26
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
4,138
1,726
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.
 
894
193
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" You must log in or register to reply here.

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
Top