Prove that $\alpha^n+\beta^n+\gamma^n \equiv 4^n+5^n+(-6)^n \pmod{17}$ 
Let $\alpha,\beta,\gamma$ be the roots of $x^3-3x^2+1 = 0$. Prove that $$\alpha^n+\beta^n+\gamma^n \equiv 4^n+5^n+(-6)^n \pmod{17}$$ where $n$ is an integer.

It sort of makes sense why they are congruent since we can say $x^3-3x^2+1 \equiv (x-4)(x-5)(x+6) \pmod{17}$, but since $\alpha,\beta,\gamma$ aren't integers, how do we prove this?
 A: Hint $\ $ Both sides satisfy the associated recurrence $\,f_{n+3} = \cdots$ with same initial conditions, thus they are equal for all $\,n\,$ by a trivial induction (i.e.  uniqueness theorem for recurrences).
To obtain the associated recurrence  sum the following for $\,a\,$ over all $\,3\,$ roots.
$$ a^{n+3}-3a^{n+2} +a^n =\, a^n(a^3-3a^2+1) = 0,\ \ {\rm  for\ any\ root}\ \ a$$
yielding $\ \  \alpha^{n+3} +\beta^{n+3} + \gamma^{n+3} - 3 (\alpha^{n+2} +\beta^{n+2} + \gamma^{n+2}) + (\alpha^{n} +\beta^{n} + \gamma^{n}) \ =\  0$
therefore  $\,\ f_{n+3} - 3f_{n+2} + f_n = 0,\ $ for $\ f_n = \alpha^{n} +\beta^{n} + \gamma^{n}$
TIP $ $ note that $\,4,5, -6\,$ are the roots of the polynomial mod $17.$
A: I think something basic should be emphasized here. Take $\alpha, \beta, \gamma$ as complex numbers (this particular time they are all real, does not matter).
What are the three numbers
$$ \alpha + \beta + \gamma, $$
$$ \beta \gamma + \gamma \alpha + \alpha \beta,  $$
$$ \alpha \beta \gamma?  $$
A: A higher (but not very high) tech solution would be to work inside the ring of $17$-adic integers $\Bbb{Z}_{17}$ (not to be confused with the residue class ring $\Bbb{Z}/17\Bbb{Z}$). Hensel's lemma tells us that the zeros $\alpha,\beta,\gamma$ of this polynomial are integers in the ring $\Bbb{Z}_{17}$ . Furthermore $\alpha\equiv4\pmod{17\Bbb{Z}_{17}}$ and similarly $\beta$ and $\gamma$ are congruent to the respective modular roots. 
The claim then follows from the usual rules of congruences, if we can show that the power sums of the roots are the "same" irrespective of whether we view them as complex numbers or $17$-adic numbers. But actually the power sums $\alpha^n+\beta^n+\gamma^n$ are rational integers. This is immediate from Galois theory. Therefore we are done.
A: Newton's identities for a cubic polynomial suggests that in this scenario $P_n = \alpha^n + \beta^n + \gamma^n = 3P_{n-1} - P_{n-3}$, and $P_0 = 3, P_1 = 3, P_2 = 9$.
For the other root sum it suggests polynomial $(x-4)(x-5)(x+6) = x^3-3 x^2-34 x+120$ which has recurrence $P_n = 4^n + 5^n + (-6)^n = 3P_{n-1} - 34P_{i-2} - 120P_{n-3}$, and $P_0 = 3, P_1 = 3, P_2 = 77$.
Taken mod $17$ you get $3P_{n-1} - P_{n-3}$ with $P_0 = 3, P_1 = 3, P_2 = 9$, the same recurrence as before.
