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

Return to MathPages Main Menu