According to this Wikipedia page, "it has been proven that for all primes $p$, $p$ divides $P(p)$" where $P(p)$ is the $p$th Perrin number, which is defined recursively as $P(n) = P(n − 2) + P(n − 3)$ for $n > 2$ and initial values with $P(0) = 3, P(1) = 0, P(2) = 2$.
Why is this true? Where can I find a proof of this?
I recently wanted to prove this and tracked down two different arguments.
Algebraic
Using standard recurrence techniques, we have $P(n) = x^n + y^n + z^n$, where $x$, $y$, and $z$ are the distinct roots of the characteristic polynomial $t^3 - t - 1$. Note that $x + y + z = 0$, since the coefficient on $t^2$ is $0$.
By the multinomial theorem,
$$0 = (x + y + z)^p = x^p + y^p + z^p + \sum_{\substack{k_1 + k_2 + k_3 = p \\ k_1, k_2, k_3, < p}} {p \choose k_1, k_2, k_3} x^{k_1} y^{k_2} z^{k_3}.$$ It is well-known that ${p \choose k_1, k_2, k_3}$ is divisible by $p$ when all the $k_i$ are less than $p$, so we have $$x^p + y^p + z^p = -p \sum_{\substack{k_1 + k_2 + k_3 = p \\ k_1, k_2, k_3, < p}} A(k_1, k_2, k_3) x^{k_1} y^{k_2} z^{k_3}$$ for some integer-valued function $A$. This sum is a symmetric polynomial in $x$, $y$, and $z$, and there is a famous theorem which implies that it is therefore a polynomial in the coefficients of $t^3 - t - 1$. Hence it is an integer, which shows that $p$ divides $P(p) = x^p + y^p + z^p$.
Combinatorial
This idea is due to Vatter, V., 2022. Social Distancing, Primes, and Perrin Numbers. Math Horizons, 29(1), pp.5-7.
Let $b(n)$ be the number of circular binary words of length $n \geq 3$ that do not contain 000 or 11. (A circular binary word is a binary string where the first and last entries are considered adjacent.) Don't consider rotations to be the same word: 100 and 010 and 001 are all different strings.
Claim: $b(n + 3) = b(n + 1) + b(n)$.
Proof: Given a word of length $n + 3$, remove the "last" 1 which appears. There are now exactly three or four 0's touching. If there are three, then remove one, and if there are four, then remove two. In the first case, we obtain a word of length $n + 1$, and in the second case we obtain a word of length $n$. This process is invertible, so $b(n + 3) = b(n + 1) + b(n)$.
Claim: $b(n) = P(n)$ for $n \geq 3$.
Proof: Check that $b(3) = P(3)$, $b(4) = P(4)$, and $b(5) = P(5)$. The recurrences and initial values after $3$ are the same, so the sequences are equal.
Claim: If $p$ is prime, then $p$ divides $P(p)$.
Proof: Circular binary words can be partitioned into equivalence classes by rotations. The size of an equivalence class is the period of any of its elements (the smallest number of rotations needed for a repetition). The period of a word divides any number of rotations that gives a repetition, which includes the length of the word. If the word has length $p$, then the period is either $1$ or $p$. Since no constant words (period $1$) meet our definition for words of length at least 3, all equivalence classes must have size $p$. Therefore $P(p) = b(p) = p \cdot (\text{number of equivalence classes})$. This leaves $p = 2$, but just check that $P(2) = 2$.