All I've managed to observe up until now is that $x_n=r_1^n+r_2^n+r_3^n+r_4^n$, where $r_i$ are the roots of the equation $x^4-cx^2-bx-a=0$. Maybe it's not important, but it's interesting, isn't it?

This was a super-hard problem, a memorable one. So, this year it seems that each THS comes with a super-hard problem.

Actually, that idea up there might yield a solution. I think we can show that $p|(r_1+r_2+r_3+r_4)^{p^m}-(r_1^{p^m}+r_2^{p^m}+r_3^{p^m}+r_4^{p^m})$ by using the fact that all symmetric polynomials in $r_1,r_2,r_3,r_4$ have integer values and all binomial coefficients $C_{p^m}^k,\ 0<k<p^m$ are divisible by $p$. On the other hand, $r_1+r_2+r_3+r_4=0$, so we would have $p|(r_1^{p^m}+r_2^{p^m}+r_3^{p^m}+r_4^{p^m})$.

For $p<>3$ that idea solves the problem pretty quickly: The expression $3[(r_1+r_2+r_3+r_4)^{p^m}-(r_1^{p^m}+r_2^{p^m}+r_3^{p^m}+r_4^{p^m})]$ can be written as a sum of expressions of the form $C_{p^m}^k[(r_1+r_2)^k(r_3+r_4)^{p^m-k}+(r_3+r_4)^k(r_1+r_2)^{p^m-k}+(r_1+r_3)^k(r_2+\nolinebreak r_4)^{p^m-k}+\nolinebreak (r_2+\nolinebreak r_4)^k(r_1+\nolinebreak r_3)^{p^m-k}+(r_1+r_4)^k(r_2+r_3)^{p^m-k}+(r_2+r_3)^k(r_1+r_4)^{p^m-k}],\ 0<\nolinebreak k<p^m$, which are symmetric in $r_i$, and thus have integer values. This, combined with the fact that $p|C_{p^m}^k,\ 0<k<p^m$ shows that $p|(r_1+r_2+r_3+r_4)^{p^m}-(r_1^{p^m}+r_2^{p^m}+r_3^{p^m}+r_4^{p^m})=-(r_1^{p^m}+r_2^{p^m}+r_3^{p^m}+r_4^{p^m})=\nolinebreak -x_{p^m}$, and we're done. You can see that I used $p<>3$ in order to eliminate the $3$ in front of the first expression. Maybe we can do it separately, by induction, for $p=3$, or maybe we can give a nicer proof of the fact that $p|(r_1+r_2+r_3+r_4)^{p^m}-(r_1^{p^m}+r_2^{p^m}+r_3^{p^m}+r_4^{p^m})$, without multiplying with 3. Is there anything wrong with this? [sorry it looks so messy; I got tired of typing "\nolinebreak" ; what else can be done in order to prevent Tex from looking like this?]

hi imho the followin could be applied when having r1^n+r2^n+r3^n+r4^n= x_n by induction on m we need to prove that when r1+r2+r3+r4 = 0 mod p we have r1^p+r2^p+r3^p+r4^p = 0 mod p using the multinomial expansion, we get that the first expression to the pth power equals the second one plus a series of symmetric polynomials on r1 r2 r3 and r4 that are therefore integers multiplied with combinatorial numbers with four arguments divisible by 3, which solves the ptoblem generally, could it be that b is odd is redundant, that keeps me doubting about the correctness of my solution

I totally forgot about $b$ being odd Now I also have some doubts about this idea. How about it Valentin? Could you post the official solution? I'd like to see how we can use the fact that $b$ is odd.

I agree that no assumption on $b$ is necessary. Another (equivalent, but maybe clearer) way to express the previous solutions is to remark that $x_n$ equals the trace of the $n$th power of the (companion) matrix \[ C = \left[\begin{array}{cccc} 0 & 0 & 0 & a \\1&0&0&b \\ 0&1&0&c\\ 0&0&1&0\end{array}\right], \] and to apply ($m$ times) Fermat's little theorem \[\text{trace} (C^p) \equiv \text{trace} (C) \mod p.\] By the way, the problem is not original, since it appeared as Problem 10655 in the April 1998 American Mathematical Monthly, Vol. 105, No. 4. under the following form: ``Define a sequence $x_0, x_1, x_2, \dots$ by $x_0 = 4, x_1 = x_2 = 0, x_3 = 3$, and $x_{m+4} = x_{m+1} + x_m$ for $m \geq 0$. Prove that $x_p$ is divisible by $p$ for every prime $p$.'' For completeness, note that (pseudo-)primality tests based on such kind of recurrences are well known in the litterature and generalize precisely Fermat's test. A classical recurrence is that of Perrin's, see for instance \[\texttt{http://mathworld.wolfram.com/PerrinSequence.html}\] and the references therein, and also \[\texttt{http://www.math.niu.edu/\~{}rusin/known-math/99/perrin}\] \[\texttt{http://www.math.niu.edu/\~{}rusin/known-math/94/primalty.tst}\]

Thanks! I was beginning to have doubts about the solution. I can't help wondering, however, about the solution the author thought of. He must have used the fact that $b$ is odd.

very interesting generalization of Fermats theorem. I wonder whether you know more results of this type? psykyk

jeje, I was reading A Classical introduction to modern number theory, We can make congruences in the ring of algebraic integers and ve always have: (w1+w2+w3...+wk)^p=w1^p+w2^p+w3^p....wk^p (modp), from here one can prove the main result by induction, but also it is easy to see that , like you said before, that the quotinet is an integer because the symetric polynomial are integers........It is nice working with fields...

we first prove $x_n=\sum_{i=1}^{4}x_i^n$,where $x_i$ are the 4 roots of equation$x^4+0x^3-cx^2-bx-a=0$ then we only need the expansion of $(x_1+x_2+x_3+x_4)^{p^m}$,where all coefficients are multiples of $p$ except $\sum_{i=1}^{4}x_i^{p^m}$.

https://artofproblemsolving.com/community/q4h290384p1569981 EDIT: I think there are possiby easier ways of proving the second half of the problem (proving that $p \mid {(r_1+\dots+r_n)}^{p^m}-({r_1}^{p^m}+\dots+{r_n}^{p^m}))$ can be done in a similair way for proving that $p \mid {(r_1+\dots+r_n)}^{p}-({r_1}^{p}+\dots+{r_n}^{p})$, which is done by induction starting at $n=2$, and using the binomial formula and properties of algebraic integers

Let $\alpha_1$, $\dots$, $\alpha_4$ be the roots of \[X^4-cX^2-bX-a=0\]Can't lie, the hardest part is the following claim. Claim: We have $a_n=\alpha_1^n+\dots+\alpha_4^n$. Proof: Induction and Vieta. $\blacksquare$ Work in $\mathbb{F}_{p^2}$ now. Due to the fact that Frobenius Endomorphism fixes roots of polynomials we have that \[\{\alpha_1^p,\alpha_2^p,\alpha_3^p,\alpha_4^p\}=\{\alpha_1,\alpha_2,\alpha_3,\alpha_4\} \implies \alpha_1^p+\alpha_2^p+\alpha_3^p+\alpha_4^p=\alpha_1+\alpha_2+\alpha_3+\alpha_4=0\]And then through induction, we are done.

Isn't that too obvious? You have a necklace of $n$ beads, then divide it into parts of length $2$, $3$, $4$. Then you paint each part of length $2$ with one of $c$ colors, paint each part of length $3$ with one of $b$ colors, paint each part of length $4$ with one of $a$ colors. Then the way to do this is this sequence. Now, if the amount of beads is a prime power, just rotate the necklace.

Nguyen wrote: Isn't that too obvious? You have a necklace of $n$ beads, then divide it into parts of length $2$, $3$, $4$. Then you paint each part of length $2$ with one of $c$ colors, paint each part of length $3$ with one of $b$ colors, paint each part of length $4$ with one of $a$ colors. Then the way to do this is this sequence. Now, if the amount of beads is a prime power, just rotate the necklace. Can you show your solution more explained?

If you have a necklace of length $2$, there are $2$ places to cut it into one segment of length $2$. Then you color it, you get $2c$ possibilities. If you have a necklace of length $4$, you can cut it into one segment of length $4$ in four ways, or two segments of length $2$ in two ways, yielding $4a+2c^2$. To prove the recursion $x_{n+3} = ax_{n-1}+bx_n + cx_{n+1}$ indeed holds, for a necklace with $n+3$ beads, number the beads clockwise from $1$ through $n+3$. Consider the segment containing bead $1$, then consider the segment directly after it when reading clockwise. It may have length $2$, $3$ or $4$, removing it yields the recursion formula. If $p$ is prime, for the necklaces with $p^m$ beads, if two of them can coincide upon rotation, then they are in the same equivalent class. Each equivalent class must have size $p^k$ where $k$ is a positive integer not larger than $m$. PIRISH wrote: Nguyen wrote: Isn't that too obvious? You have a necklace of $n$ beads, then divide it into parts of length $2$, $3$, $4$. Then you paint each part of length $2$ with one of $c$ colors, paint each part of length $3$ with one of $b$ colors, paint each part of length $4$ with one of $a$ colors. Then the way to do this is this sequence. Now, if the amount of beads is a prime power, just rotate the necklace. Can you show your solution more explained?