Mathematica 9 is now available
Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2005
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2005

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: Re: Types in Mathematica thread
  • Next by Date: Re: exponential diophantine equations
  • Previous by thread: Re: exponential diophantine equations
  • Next by thread: Re: exponential diophantine equations