Define the Perrin sequence by $k(1)=0$, $k(2)=2$, $k(3)=3$, and $k(n)=k(n-2)+k(n-3)$. We find that mostly $n$ divides $k(n)$ iff $n$ is prime, although there are a few exceptions called "Perrin Pseudo-primes."
But the obvious conjecture only fails for $n$ composite, for we find that whenever $p$ is prime, $p | k(p)$. However, the usual proof goes as follows.
Let $\alpha$, $\beta$, and $\gamma$ be the roots of the characteristic polynomial $x^3-x-1$. Then a simple induction argument shows that $k(n)=\alpha^n+\beta^n+\gamma^n.$
Now consider $(\alpha+\beta+\gamma)^p = \alpha^p+\beta^p+\gamma^p+p\sum(things)$. Since we have $p$ times something, when we consider this module $p$ we get:
$$(\alpha+\beta+\gamma)^p = \alpha^p+\beta^p+\gamma^p$$
and we're done, because $\alpha+\beta+\gamma = 0$. And that would be fine if the things in the summation were integers.
But they're not.
So my question is: why is that summation always considered to be an integer, when the things in the summation are the roots of the cubic, and not integral?
All the papers I've read seem to take this for granted, so I'm sure I must be missing something simple.