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).

Return to MathPages Main Menu