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.

  • $\begingroup$ 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. $\endgroup$
    – ARupinski
    Jun 15, 2013 at 1:27

1 Answer 1


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}$.

  • $\begingroup$ Your first condition implies $2$ is a quadratic nonresidue mod $p$; does it imply $2$ is a primitive root? $\endgroup$ Jun 15, 2013 at 5:44
  • $\begingroup$ I think the answer is correct if "primitive root" is replaced by "quadratic nonresidue" everywhere. $\endgroup$ Jun 15, 2013 at 9:46
  • $\begingroup$ I fixed the silly mistake. Thankfully it was clear from context. $\endgroup$ Jun 15, 2013 at 10:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.