Re: Problem

[Peter-Lawrence.Montgomery@cwi.nl]

    If F_n is a 13-th power, then (F_n mod p) is a 13-th residue (or 0)
modulo all primes p.  

    Choose 10 primes p_j == 1 mod 13, starting with 53, 79, 131, 157, ...
If you know  F_{2i-1} mod p_j  and  F_{2i-3} mod p_j, then

                 F_{2i+1} == 3*F_{2i-1} - F_{2i-3}   (mod p_j)

Use F_{2i+1} mod p_j as an array subscript, where the array
tells you whether the index a 13-th power mod p_j.  
If the test passes for all j, output 2i+1 as a possible solution.
The test should take only a few seconds.  I anticipate no solutions.

    Peter Montgomery

------------

> From: "James G. McLaughlin" <jgmclaug@math.uiuc.edu>

This is probably not a bug question but I just do not know of the fastest
way to get pari to do it.

Let  F_{1}=F_{2}=1 and F_{n+1}= F_{n} + F_{n-1} for  n >= 2
      (The Fibonacci sequence)  

I wish to test the sequence { F_{2*i+1} : 1 <= i <= 69,700 }
for 13th powers. 

As you can imagine, as i gets up to 69,700,  F_{2*i+1} gets very big  
(around 10^(23,000)). I have not been able to
write a gp program that would do this in any reasonable time.

I wrote a very simple program in magma that would have done it in around 
3 - 4 hours (extrapolating) but it crashes around i = 52,000.

Am I missing something very simple and can gp do this easily or is it also
beyond gp to do this in a reasonable time?