Re: Solving Diophantine Equations

*To*: mathgroup at smc.vnet.net*Subject*: [mg61252] Re: [mg61185] Solving Diophantine Equations*From*: Andrzej Kozlowski <andrzej at yhc.att.ne.jp>*Date*: Fri, 14 Oct 2005 05:53:39 -0400 (EDT)*References*: <121B726C-F342-49E8-AC5A-028B2431CE24@yhc.att.ne.jp> <D3177184-B465-40C1-B883-22709E67ECA1@yhc.att.ne.jp>*Reply-to*: Andrzej Kozlowski <andrzej at akikoz.net>*Sender*: owner-wri-mathgroup at wolfram.com

Sorry, I was wrong last time. This new bound lower bound for x, namely y is actually worse than my earlier one, namely y^((n - 1)/ 2), except when n<=3. Let me quickly show how I got that the earlier bound. We look at the equation x^2+x == y^(n-1)+ y^(n-2)+... If x< y^((n-1)/2) then x^2 < y^(n-1) and x^2+x < y^(n-1)+ y^(n-1)/2 which is less then y^(n-1) + y^(n-2)+.... So actually the best bound I know at this moment is: y^((n-1)/2) <= x <= y^(n-2)+y^(n-3)+...+y Andrzej Kozlowski On 13 Oct 2005, at 19:59, Andrzej Kozlowski wrote: > Actually it is easy to find a better bound. > > Consider your equality: > > (x^3 - 1)/(x - 1)==(y^n - 1)/(y - 1) > > Assuming that n is a positive integer this can be written in the form: > > x^2+x == y^(n-1)+ y^(n-2)+... > > Factorising both sides we get > > x*(x+1) == y* (y^(n-2)+y^(n-3)+...+1) > > This means however that we must have > > x>=y and x+1 <= y^(n-2)+y^(n-3)+...+ 1 > > because the other case x<y and x+1>y^(n-2)+y^(n-3)+...+ 1 is > obviously impossible. So we see that > > y<=x <= y^(n-2)+y^(n-3)+...+y > > > This is at least better than making searches over independent > ranges for x and y. > > > Andrzej Kozlowski > > > > On 13 Oct 2005, at 15:58, Andrzej Kozlowski wrote: > > > >> >> >> On 12 Oct 2005, at 14:42, Diana wrote: >> >> >> >> >> >>> Math group, >>> >>> I am trying to start doing numerical solving of Diophantine >>> Equations. I >>> want to do extensive calculations, but the kernel aborts for lack >>> of memory. >>> >>> For example, the following command aborts midstream: >>> >>> Table[If[(x^3-1)/(x-1)==(y^n-1)/(y-1) && x!=y, >>> {{x,y,n},}],{x,2,1000},{y,2,1000},{n,1,1001,2}] >>> >>> I have tried doing many smaller steps, but then I have a very >>> long file of >>> multiple commands. >>> >>> Would you make a suggestion as to how to process these solving >>> commands with >>> large values of the variables? >>> >>> Thanks, >>> >>> Diana >>> -- >>> ===================================================== >>> "God made the integers, all else is the work of man." >>> L. Kronecker, Jahresber. DMV 2, S. 19. >>> >>> >>> >>> >>> >>> >> >> >> I doubt this will be of much help, but there are some obvious >> inequalities that must hold between the possible values of x and >> y, which can reduce the number of possible cases that need to be >> looked at. For example, you must have >> >> x > y^((n - 1)/2) >> >> Since if this were not true the LHS of >> >> (x^3-1)/(x-1)==(y^n-1)/(y-1) >> >> would be too large. Similarly it is also obvious that, >> >> x < (n - 1)*(y^(n - 1)/2) >> >> >> These are very rough bounds and as I spent only about 1 minute >> looking for them you should be able to work out better ones. In >> this way you can at least reduce the number of x's that need to be >> looked at for a given y and n. Even so this looks like a pretty >> tough task to attempt on a present day computer. >> >> Andrzej Kozlowski >> >> >> >> >> Andrzej Kozlowski >> Tokyo, Japan >> >> >> >> >> >> >> > > Andrzej Kozlowski > Tokyo, Japan > > > > > Andrzej Kozlowski Tokyo, Japan

**DSolve and matrix form of system of equations**

**Re: Solving Diophantine Equations**

**Re: Solving Diophantine Equations**

**Re: Solving Diophantine Equations**