You are not logged in.
#1 2005-12-30 20:49:36
- krassi_holmz
- Real Member
Offline
Solving diophantine equations
I need to make a program that solves different diophantine equations.
Can someone help me?
IPBLE: Increasing Performance By Lowering Expectations.
#2 2005-12-30 20:50:56
- krassi_holmz
- Real Member
Offline
Re: Solving diophantine equations
1. ax+by=c
IPBLE: Increasing Performance By Lowering Expectations.
#3 2005-12-31 06:12:52
- John E. Franklin
- Star Member
Offline
Re: Solving diophantine equations
Code:
ax + by = c
by = -ax + c
y = (-a/b)x + (c/b)
So y = at + ?1? and
x = bt + ?2?
-------
Put into original equation ax + by = c
a(bt + ?2?) + b(at + ?1?) = c
abt + a?2? + bat + b?1? = c
2bat + a?2? + b?1? = c
---------
y=7x + .3
y=7t + ?
x=t + ?
No integer solutions for this 7x + .3
---------
No luck yet.Imagine for a moment that even an earthworm may possess a love of self and a love of others.
#4 2005-12-31 07:56:27
- krassi_holmz
- Real Member
Offline
Re: Solving diophantine equations
For lineal d.e. we can use the this
Last edited by krassi_holmz (2006-01-01 07:10:13)
IPBLE: Increasing Performance By Lowering Expectations.
#5 2006-01-01 05:32:36
- John E. Franklin
- Star Member
Offline
Re: Solving diophantine equations
At wolfram's site, equation # 6 has a "+ 1" in it (Euclidian thing).
I wonder why it always works out to a one, like the example they have?
Last edited by John E. Franklin (2006-01-01 05:33:03)
Imagine for a moment that even an earthworm may possess a love of self and a love of others.
#6 2006-01-01 06:52:50
- John E. Franklin
- Star Member
Offline
Re: Solving diophantine equations
Also equation # 10 at their site has an incorrect sign, I think.
Imagine for a moment that even an earthworm may possess a love of self and a love of others.
#7 2006-01-01 08:28:42
- John E. Franklin
- Star Member
Offline
Re: Solving diophantine equations
I found this a very useful page on this subject.
http://uzweb.uz.ac.zw/science/maths/zimaths/62/dioph.htm
or
Press this to go there.
My favorite part is at the end of the page:
the web page wrote:
(i) The equation 3x + 6y = 22 has no solution since (3, 6) = 3 does not divide 22.
(ii) The equation 7x + 11y = 13 has solution x = -39, y = 26. For
11 = 1·7 + 4, 7 = 1·4 + 3, 4 = 1·3 + 1.
Thus (7, 11) = 1, which divides 13. Further, working from the last equation back to the first,
1 = 4 - 3 = 4 -(7-4) = 2·4 - 7 = 2·11 - 3·7.
Hence
7·(-3) + 11(2) = 1, 7·(-39) + 11(26) = 13.
The other solutions are given by
x = -39 + 11r, y = 26 - 7r
where r is any integer.
Last edited by John E. Franklin (2006-01-01 08:32:35)
Imagine for a moment that even an earthworm may possess a love of self and a love of others.
#8 2006-01-01 22:12:53
- krassi_holmz
- Real Member
Offline
Re: Solving diophantine equations
OK. We have simple alogritm for ax+by. I know it as Euler's reduction algoritm.
The next general case:
ax^2+by=c
IPBLE: Increasing Performance By Lowering Expectations.