Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

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

share|improve this answer
    
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
    
I think the answer is correct if "primitive root" is replaced by "quadratic nonresidue" everywhere. –  Greg Martin Jun 15 '13 at 9:46
    
I fixed the silly mistake. Thankfully it was clear from context. –  Gjergji Zaimi Jun 15 '13 at 10:16
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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