If $x_1, x_2$ are roots of $P(x)=x^2-6x+1$, prove that $5 \nmid x_1^n+x_2^n$ 
Given $x_1$ and $x_2$ are roots of $P(x)=x^2-6x+1$ prove using Binomial expansion that $x_1^n+x_2^n$ is not divisible by 5 if $n\in \Bbb N\setminus\{0\}$.

Source: list of problems for the preparation for math contests. 
Notice: this problem is different from other SE question, as it requires a specific proof that was suggested by @DeepSea in a comment in that post, but not developed.
My attempt:  By solving the roots of $P(x)$ it is easy to see that
$$x_1=3+2\sqrt{2}\ \ \text{and}\ \ \ x_2=3-2\sqrt{2}$$
and, using the Binomial expansion,
$$x_1^n+x_2^n=(x_1+x_2)^n-\sum_{k=1}^{n-1}{{n-1}\choose {k}} x_1^{n-k}x_2^k=6^n-\sum_{k=1}^{n-1} {{n-1}\choose {k}}x_1^{n-k}x_2^k$$
It is easy to see that $6^n\equiv 1\pmod{5}$ for all possible $n$. Therefore the problem is showing that for $$A(n)=\sum_{k=1}^{n-1}{{n-1}\choose {k}}x_1^{n-k}x_2^k,\ \ A(n)\not\equiv 1\pmod{5},\ \forall n\in \Bbb N\setminus\{0\}.$$
My problem is on how to proceed with the proof of this last statement. Hints and answers are welcomed.
 A: Here is a solution inspired by Pell's equations, which tangentially is related to Binomial expansion. $(3,2)$ is a solution for
$$x^2-2y^2=1 \tag{1}$$
but then any $(x,y)$ of the form
$$x=\frac{\left(3+2\sqrt{2}\right)^n+\left(3-2\sqrt{2}\right)^n}{2} \space\space\space\text{ and }\space\space\space
y=\frac{\left(3+2\sqrt{2}\right)^n-\left(3-2\sqrt{2}\right)^n}{2\sqrt{2}}$$
where
$$x+y\sqrt{2}=\left(3+2\sqrt{2}\right)^n \space\space\space\text{ and }\space\space\space
x-y\sqrt{2}=\left(3-2\sqrt{2}\right)^n$$
is also a solution. Using binomial expansion it is easy to check $x,y \in \mathbb{Z}$ and
$$2x=x_1^n+x_2^n \tag{2}$$
Now, proof by contradiction. If $5 \mid x_1^n+x_2^n \overset{\color{red}{(2)}}{\Rightarrow} 5 \mid x$, this is from Euclid's lemma. But then
$$5\mid x^2 \overset{\color{red}{(1)}}{\Rightarrow} 5 \mid 2y^2+1$$
However $2y^2+1$ is never divisible by $5$. This is easy to see from $y^4 \equiv 1 \pmod{5}$ (LFT) or $5 \mid \left(y^2-1\right)\left(y^2+1\right)$ (applying the same Euclid's lemma)

*

*if $5 \mid y^2+1 \Rightarrow 5 \nmid 2y^2+1=y^2+1+y^2$, otherwise $5 \mid y^2$ leading to $5 \mid 1$.

*if $5 \mid y^2-1 \Rightarrow 5 \nmid 2y^2+1=2(y^2-1)+3$, otherwise $5 \mid 3$.

Alternatively, it's easy to check that $2y^2+1$ never has $0$ or $5$ as the last digit.
$$2\cdot \color{blue}{0}^2+1=1 \text{, }\space\space
2\cdot \color{blue}{1}^2+1=3 \text{, }\space\space
2\cdot \color{blue}{2}^2+1=9 \text{, }\space\space
2\cdot \color{blue}{3}^2+1=19 \text{,}\\ 
2\cdot \color{blue}{4}^2+1=33 \text{, }\space\space
2\cdot \color{blue}{5}^2+1=51 \text{, }\space\space
2\cdot \color{blue}{6}^2+1=73 \text{, }\space\space
2\cdot \color{blue}{7}^2+1=99 \text{,}\\
2\cdot \color{blue}{8}^2+1=129 \text{, }\space\space
2\cdot \color{blue}{9}^2+1=163$$
So we have a contradiction.
A: I think you misinterpreted the suggestion by @DeepSea.  He probably meant expanding $(3\pm2\sqrt{2})^n$ instead of $(x_1+x_2)^n$.
So if we follow this and binomial expand $(3\pm 2\sqrt{2})^n$, we have
$$
x_1^n+x_2^n=\sum_{k=0}^n\binom{n}{k}3^{n-k} (2\sqrt{2})^k \underbrace{[1+(-1)^k]}_{=\begin{cases}2&k\text{ even}\\0&k\text{ odd}\end{cases}}
$$
So we cancel the odd $k$ terms and are left with
$$
x_1^n+x_2^n=2\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n}{2k}3^{n-2k} (2\sqrt{2})^{2k}
\equiv 2\cdot3^n\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n}{2k}3^{-k}\pmod{5}.
$$
Hence we want to prove
$$
\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n}{2k}(-3)^k\not\equiv 0\pmod{5}
$$
which I don't see a way without
Cheating
So we look at an equivalent problem with roots $1\pm\sqrt{-3}\pmod{5}$, which if we take out a common factor of $2$ (doesn't change mod 5 nonzero) becomes a problem with roots $y_\pm=\frac12(1\pm\sqrt{-3})$ (which are of course the roots of $y^2-y+1$, what you get from reducing coefficients of $P$ mod $5$).  Now these roots are sixth roots of unity, so $y_+^n+y_-^n$ only take values $\pm 1,\pm 2$.
This leaves the question: why not reduce $P$ mod 5 right at the start and be done with it?
A: Let $a_n = x_1^n+x_2^n$. Then modulo $5$,  $a_1 =1, a_2= 2, a_n = a_{n-1}-a_{n-2}$ 
We can see that the terms of the sequence are periodic. They go 1,2,1,-1,-2,-1,1 and the cycle continues so that no term is $0$ modulo 5
