# Pell Numbers and the Primes

I have observed that the Pell Numbers: a(0) = 1, a(1) = 2; for n > 1, a(n) = 2*a(n-1) + a(n-2)

and the related integer sequence: a(0) = 2, a(1) = 0; for n > 1, a(n) = 2*a(n-1) + a(n-2) together share an interesting property.

For any index number 'n', if n is a prime number, then it divides exactly into a(n) in just one, and only one, of the two sequences. If n does not divide into a(n) in either sequence, then n is non-prime.

The sequences, and the primes that they generate, begin thus:

1 2 5 12 29 70… 3 5 11 13 19 29 …

2 0 2 4 10 24 … 2 7 17 23 31 41 …

I would like to find further information on this, such as who first discovered it, and whether it has been proved.

The sequence 2, 0, 2, 4, 10, 24, ... is not listed in OEIS, so this may not be very well known.

• Note that your second sequence $\\{2, 0, 2, 4, 10, 24,\ldots\\}$ is just the doubles of your first sequence, shifted right by one step. So it probably would not appear in the OEIS. – ARupinski Jun 15 '13 at 1:27

Your claim is true. Note that we can solve the recurrences to give $$a_p=\frac{1}{\sqrt{2}}\left((1+\sqrt{2})^{p+1}-(1-\sqrt{2})^{p+1}\right)$$ for the first sequence. So for a prime $p$, we have that $p$ divides $a_p$ iff $p$ divides $2+2^{\frac{p+1}{2}}$, that is iff $2$ is a quadratic nonresidue modulo $p$, or in other words $p$ is $\pm 3 \pmod{8}$. (I used the fact that $\binom{p+1}{k}\equiv 0\pmod{p}$ for $2\le k\le p-1$.)
Similar analysis shows that for the second sequence we have $$a_p=\sqrt{2}\left((1+\sqrt{2})^{p-1}-(1-\sqrt{2})^{p-1}\right),$$ and so $a_p\equiv 2^{\frac{p+1}{2}}-2\pmod{p}$. So in the second sequence $p$ divides the $p$th term iff $2$ is a quadratic residue mod $p$, or in other words $p$ is $\pm 1\pmod{8}$.
• Your first condition implies $2$ is a quadratic nonresidue mod $p$; does it imply $2$ is a primitive root? – Gerry Myerson Jun 15 '13 at 5:44