Pseudoprimes For x^2 - 4x - 9

Let a(n) and b(n), n=0,1,2,... denote integer sequences each
satisfying the linear recurrence s(k) = 4 s(k-1) + 9 s(k-2) with
the initial values {1,0,...} and {0,1,...} respectively.  If N is
a prime congruent to 1, 3, 4, 9, 10, or 12 (mod 13) then

           a(N)=0    and     b(N)=1         (mod N)        (1)

If N is a prime congruent to 2, 5, 6, 7, 8, or 11 (mod 13) then

           a(N)=4    and     b(N)=-1        (mod N)        (2)

A composite integer N with gcd(N,26)=1 and gcd(N,a(N)) = {1 or N}
such that either (1) or (2) is satisfied (according to the residue
class of N mod 13) is called a complete pseudoprime relative to the
characteristic polynomial x^2-4x-9.  Among integers less than 10^8 
there are only 79 complete pseudoprimes (24 of which are also 
Carmichael numbers).  Every one of these pseudoprimes is congruent 
to a square (mod 13).  Robert Harley extended the search up to
861,657,343, which is the 181st complete pseudoprime, and still
found no pseudoprime with a non-square residue modulo 13.  Therefore,
this simple quadratic test (which can obviously be performed in
log(N) steps) is both necessary and sufficient for primality for
all numbers congruent to 2,5,6,7,8, or 11 (mod 13), at least up to
nearly 10^9.  (These non-square residues cover half of all numbers
not divisible by 13).

It would be interesting to know the smallest complete pseudoprime
relative to x^2 - 4x - 9 that is NOT congruent to a square modulo 13.

For more on this subject, see Symmetric Pseudoprimes.