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

```