Quadratic Congruences

Suppose we have a fourth order recurrence such as

                 s[n] = 4 s[n-3] - 5 s[n-4]

with arbitrary initial values, say, s[0] = s[1] = s[2] = s[3] = 1.
For any prime p (other than 2 or 7) the value of s[p] (mod p) must 
satisfy one of the following four congruences, depending on the 
Legendre symbols [-1/p] and [2/p]:

    [-1/p]   [2/p]              congruence (mod p)
   -------- -------       ------------------------------
      1       1                 7x^2 -  2x -  5  =  0
      1      -1                49x^2 - 14x + 17  =  0
     -1       1                 7x^2 +  2x -  7  =  0
     -1      -1                49x^2 + 14x +  3  =  0

Now suppose we want to know all the primes p such that s[p] is
congruent modulo p to some arbitrary number, say, q=9876543210.  We 
can see that the first congruence gives no solutions, because none 
of the prime factors of 7q^2-2q-5 has the right Legendre symbols.
However, the remaining congruences give seven possibilities

             13     21627869606482291837
           5903       57349454965063
              3          1567771       1016253688263811

These are the only primes that could possibly satisfy the stated 
condition.  Of these, we can easily verify that 13 works, as does 
1567771.  However, the primes 3 and 5903 do not work.  The reason
is that although these primes ensure that q is a root of the 
quadratic congruence of which s[p] is also a root, they do not
ensure that q and s[p] are the same root.  For example, with p=5903
we have q=3693 (mod p), whereas s[p]=3053 (mod p).  These are the
two roots of 7x^2 + 2x - 7 (mod p).

Anyway, this leaves the three unresolved possibilities

   21627869606482291837     57349454965063     1016253688263811

With a little multi-precision number crunching we can check 
s[p] (mod p) for each of these primes to see if they are congruent
to q, but I'm wondering if there is a smarter way of figuring out
which of the two roots (mod p) is equal to s[p] for the given fourth 
order sequence.  Anyone have any ideas?



In case anyone is interested, the crunching method shows that s[p]
is not congruent to q for the first of these primes, but it is
for the second and third.  Therefore, s[p] = 9876543210 (mod p)
if and only if p is one of the four primes 
 
      13     1567771       57349454965063      1016253688263811