Peter-Lawrence . Montgomery on Sat, 23 Sep 2000 05:21:14 +0200 (MET DST)

 Re: Problem

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

• Follow-Ups:
• References:
• Problem
• From: "James G. McLaughlin" <jgmclaug@math.uiuc.edu>