Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2005-12-29 21:49:36

krassi_holmz
Real Member
Registered: 2005-12-02
Posts: 1,905

Solving diophantine equations

I need to make a program that solves different diophantine equations.
Can someone help me?


IPBLE:  Increasing Performance By Lowering Expectations.

Offline

#2 2005-12-29 21:50:56

krassi_holmz
Real Member
Registered: 2005-12-02
Posts: 1,905

Re: Solving diophantine equations

1. ax+by=c


IPBLE:  Increasing Performance By Lowering Expectations.

Offline

#3 2005-12-30 07:12:52

John E. Franklin
Member
Registered: 2005-08-29
Posts: 3,588

Re: Solving diophantine equations

              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.

igloo myrtilles fourmis

Offline

#4 2005-12-30 08:56:27

krassi_holmz
Real Member
Registered: 2005-12-02
Posts: 1,905

Re: Solving diophantine equations

For lineal d.e. we can use the this

Last edited by krassi_holmz (2005-12-31 08:10:13)


IPBLE:  Increasing Performance By Lowering Expectations.

Offline

#5 2005-12-31 06:32:36

John E. Franklin
Member
Registered: 2005-08-29
Posts: 3,588

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 (2005-12-31 06:33:03)


igloo myrtilles fourmis

Offline

#6 2005-12-31 07:52:50

John E. Franklin
Member
Registered: 2005-08-29
Posts: 3,588

Re: Solving diophantine equations

Also equation # 10 at their site has an incorrect sign, I think.


igloo myrtilles fourmis

Offline

#7 2005-12-31 09:28:42

John E. Franklin
Member
Registered: 2005-08-29
Posts: 3,588

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 (2005-12-31 09:32:35)


igloo myrtilles fourmis

Offline

#8 2005-12-31 23:12:53

krassi_holmz
Real Member
Registered: 2005-12-02
Posts: 1,905

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.

Offline

Board footer

Powered by FluxBB