       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
>
> 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
>
> True
>
> On the other hand:
>
>
> h
>
> False
>
> OK, using this function we can now try to find any solutions for k
> between 1 and 10000:
>
>
> Select[Range,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 which checks the first 200 primes.
>
> let7s try the above computation with g:
>
>
> Select[Range,g]//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:=
> Select[Range,g]//Timing
>
> Out=
> {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:=
>>> (5x)^2 - 2^k * 3 * (5+k)^2 - 131 * k + 7 /.{x->31,k->6}
>>>
>>> Out=
>>> 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
>>>
>>
>

```

• Prev by Date: Re: exponential diophantine equations
• Next by Date: Re: Types in Mathematica, a practical example
• Previous by thread: Re: exponential diophantine equations
• Next by thread: Re: exponential diophantine equations