Re: exponential diophantine equations

*To*: mathgroup at smc.vnet.net*Subject*: [mg62965] Re: [mg62922] exponential diophantine equations*From*: Andrzej Kozlowski <akoz at mimuw.edu.pl>*Date*: Fri, 9 Dec 2005 05:10:43 -0500 (EST)*Sender*: owner-wri-mathgroup at wolfram.com

The ReleaseHold in the definition of test[k,p] is not needed (it was needed in my earlier attempt to define this function and I forgot to remove it) so it should now be: test[k_Integer, p_Integer] := Block[ {$Messages = {}}, Check[SqrtMod[f[k, p], p]; True, False] ] Andrzej On 9 Dec 2005, at 12:40, Andrzej Kozlowski wrote: > Here is one approach. We will need the package: > > << NumberTheory`NumberTheoryFunctions` > > Let's start with a primitive approach and then improve it to run > much faster. The primitive approach would be like this. First we > write your equation as > > 2^k*3*(k + 5)^2 + 131*k + 7 == (5*x)^2 > > Let us define a function f[k] as follows: > > f[k_Integer] := 2^k*3*(k + 5)^2 + 131*k + 7 > > What we are looking for is values of k for which the the following > are true: > > 1. f[k] is 0 mod 25. > 2. f[k] is a perfect square. > > It is easy to write a slow function that looks for such k. First of > all, we need a function f[k_,n_] which efficiently computes Mod[f > [k],n]. Here is this function: > > f[k_Integer, p_Integer] := > Mod[PowerMod[2, k, p]*Mod[3, p]*PowerMod[k + 5, 2, p] + Mod > [131*k + 7, > p], p] > > The test for divisibility of f[k] by 25 takes the form > > test25[k_Integer] := f[k, 25] == 0 > > We also need a test to check if a number is a perfect square. Here > is the obvious one: > > > test1[x_Integer] := IntegerQ[Sqrt[f[x]]] > > Now let's define a function that combines both tests: > > h = Function[x, Evaluate[And @@ Prepend[{test1[x]}, test25[x]]]]; > > > Let's check that this will work well on the one solution we know: > > > h[6] > > True > > On the other hand: > > > h[7] > > False > > OK, using this function we can now try to find any solutions for k > between 1 and 10000: > > > Select[Range[10000],h]//Timing > > > {36.1681 Second,{6}} > > > This is rather slow so we try something more sophisticated. Instead > of checking is f[k] is a square root we will check if it is a > square root modulo a prime p. We will use a large number of primes > and this will still be faster than doing an integer check. Here is > the test function: > > test[k_Integer, p_Integer] := ReleaseHold[Block[ {$Messages = {}}, > Check[SqrtMod[f[k, p], p]; True, False] > ]] > > I do not have the time at this moment to explain exactly what this > does. The key function is SqrtMod from the NumberTheoryFunctions > package. it computes square roots modulo a prime. Here is now a > function that will check if f[k] of a number is a square module the > first n -primes (it also checks if f[k] is divisible by 25) > > g[k_] := Function[ > x, Evaluate[And @@ Prepend[Table[test[x, Prime[i]], {i, 1, k}], > test25[x]]]] > > I am going to use g[200] which checks the first 200 primes. > > let7s try the above computation with g[200]: > > > Select[Range[10000],g[200]]//Timing > > > {3.41956 Second,{6}} > > Note that we still correctly identified the solution 6, but we got > it a lot faster. So we can try looking at larger ranges. If we find > a some possible solutions we still have to run the primitive test > on them to check if they are real solutions and not just solutions > modulo the first 200 primes. > > In[21]:= > Select[Range[20000],g[200]]//Timing > > Out[21]= > {6.82253 Second,{6}} > > Still no luck, but performance seems to scale quite well. I have no > time now to try looking for more solutions (as my lecture will > begin in half an hour) but we know that for k between 1 and 20000 > there is only one solution, which is the one you already knew. > > Andrzej Kozlowski > > > > > > > > On 9 Dec 2005, at 02:02, Andrea wrote: > >> Dear Andrzej, >> >> Oh those signs! I typed +7. Mistake. It should be -7. >> >> Andrea >> >> At 01:38 AM 12/8/2005, Andrzej Kozlowski wrote: >> >>> On 8 Dec 2005, at 17:27, Andrea wrote: >>> >>>> >>>> I'm trying to find out how to use Mathematica to find solutions to >>>> exponential diophantine equations like the following: >>>> >>>> (5x)^2 - 2^k * 3 * (5+k)^2 - 131 * k + 7 = 0. I want to >>>> obtain >>>> solutions for x and k. (One solution is x = 31, k = 6, but I didn't >>>> find >>>> this using Mathematica!) >>> >>> Are you sure you have found a solution? I get: >>> >>> In[30]:= >>> (5x)^2 - 2^k * 3 * (5+k)^2 - 131 * k + 7 /.{x->31,k->6} >>> >>> Out[30]= >>> 14 >>> >>> >>> One can certianly try some "educated searches" but before >>> starting it >>> woudl be better to be sure that this is really the equation you want >>> to solve! >>> >>> Andrzej Kozlowski >>> >> >