Re: exponential diophantine equations

*To*: mathgroup at smc.vnet.net*Subject*: [mg62964] 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

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 >> >