Recurrences and Pell Equations

For any sequence s[0], s[1], s[2],... that satisfies the second-
order linear recurrence

                s[n] = A s[n-1] + B s[n-2]
 
with arbitrary constants A and B we have the algebraic identity

                             /                  \      n-1
 s[n]^2 - s[n-1] s[n+1]  =  ( s[1]^2 - s[0] s[2] ) (-B)
                             \                  /

for all n.  If B = 1, it follows that this quantity has constant 
magnitude with alternating sign.  Denoting this quantity by D, we
can express it's magnitude in terms of the initial values s[0] 
and s[1] as

                    |                            |
           |D|  =   | s[1]^2 - s[0]s[1] - s[0]^2 |
                    |                            |

For convenience, let n and m denote the initial values s[0] and s[1]
respectively.  Then we have a magnitude D corresponding to every
pair of integers n,m such that D = +-(m^2 - mn - n^2).  If we solve
the quadratic equation

                 m^2 - nm - (n^2 +- D) = 0

for m we have
                          ___________
                    n +- / 5n^2 + 4D
               m =  -----------------
                            2

(and the same for -D) which implies that the quantity in the square
root must be a square, i.e., there must be an integer k such that 
5n^2 + 4D = k^2.  Hence we seek solutions of the Pell equation

                      k^2 - 5n^2 = 4D

If D is a prime p, this equation signifies that k^2 = 5n^2 (mod p),
which has solutions if and only if 5 is a square modulo p.  Now, by 
quadratic reciprocity, this is the case if and only if p is a square
modulo 5, which means that p is congruent to either +1 or -1 mod 5 
(and therefore mod 10 as well).  Thus all and only primes of the 
form 10j+1 and 10j-1 have solutions.

The first several solution pairs (n,m) for D = 1 are listed below.
For each n there are two m values, given by the two roots of the
quadratic.

s[0] =  n   =  1   3    8    21   55   144   377   987
s[1] =  m1  =  2   5   13    34   89   233   610  1597 
        m2  = -1  -2   -5   -13  -34   -89  -233  -610

As we would expect, the soutions with D=-1 are essentially the same,
but shifted by one index.  Clearly these (n,m) solutions are all 
equivalent in the sense that they all lie within the same recurring
sequence, i.e., the Fibonacci sequence.  Therefore, we say there is
essentially just one solution for D = +-1.

Similarly if D equals the "special" prime 5 (special because 5 is 
the discriminant of the characteristic polynomial of the Fibonacci
recurrence, as shown by the 5 appearing in the Pell equation), there
is essentially just one equivalence class of solutions, as shown
below.

s[0] =  n   =  1   4   11    29    76   199   521
s[1] =  m1  =  3   7   18    47   123   322   843
        m2  = -2  -3   -7   -18   -47  -123  -322

However, if D is an odd prime congruent to +1 or -1 modulo 5, there
are two equivalence classes of solutions, in the sense that the 
(n,m) solutions all lie within one of two distinct sequences.  To
illustrate, the first several (n,m) solutions for D=11 are listed 
below.

s[0] =  n   =  1    2    5    7   14   19   37   50   97  131
s[1] =  m1  =  4    5    9   12   23   31   60   81  157  212
        m2  = -3   -3   -4   -5   -9  -12  -23  -31  -60  -81

In this case the solution pairs (n,m) all lie in one of TWO distinct
recurring sequences, namely

         1  4  5   9  14  23  37  60   97  157 ...
    or
         2  5  7  12  19  31  50  81  131  212 ...

We could, however, regard this as just a single doubly-infinite
sequence by proceding to negative indices (since we are assuming
B=1).  Tis leads to the single sequence

   ... -19  12  -7  5  -2  3  1  4  5  9  14  23  37  60 ...

The sequences for the special values D=1 and D=5 are symmetrical
about the origin, so they give only one distinct forward sequence,
whereas for all other primes (congruent to +-1 mod 5) the sequences
are not symmetrical, so they give two distinct forward sequences.

If we consider (square-free) composite values of D, it's clear that
they must be products of the special numbers 1 and 5, and the primes
congruent to +-1 modulo 5.  These must include all the numbers given
by j^2 - j - 1, meaning the sequence

  -1  1  5  11  19  29  41  55  71  89  109  131  155  181  209 ...

The reason we know solutions exist for all these values is because 
if we solve the equation 

                 j^2 - j - (1+D) = 0

for j we give the same Pell equation as before, with n=1.  However,
some of the D values with solutions (such as D=31) do not have a 
solution with n=1, so those are not given by this function.  If a
D value has a solution with n=2, it is in the sequence of values
given by (2j+1)^2 - 2(2j+1) - 4  =  4j^2 - 5.  And so on.

The first square-free product of two distinct primes from the set
of primes congruent to +-1 modulo 5 is 209.  For such a value of D
we expect to find double the number of solutions for an individual
prime, because solutions of the Pell equation are multiplicative
based on the famous algebraic identity

      (a^2 - 5b^2)(x^2 - 5y^2) = (ax + 5by)^2 - 5(ay+bx)^2

This enables us to "multiply" a solution for D=11 times a solution
for D=19 to give a solution for D = (11)(19) = 209.  Since there are
two forward solutions for each prime, we can get four distinct
product solutions.  The Pell solutions for D=209 are

s[0] =  n   =   1   5   8  13  16  23  29  40  47   64   79  107 ...
s[1] =  m1  =  15  18  21  27  31  41  50  67  78  105  129  174 ...

These give the four distinct forward sequences for D=209

            1  15  16  31  47  78 ...

            5   8  23  41  64  105 ...

            8  21  29  50  79  129 ...

           13  27  40  67  107  174 ...

In general, if D is the product of k distinct primes congruent to
+-1 (mod 5), then there are 2^k distinct forward solution sequences,
because each prime factor doubles the number of ways of multiplying
the solutions.  The reason multiplying by 1 or 5 doesn't double the
solutions is that 1 and 5 each have just a single forward solution
(because they are symmetrical).