<s>[INST] Show that $2^n(\cos^n(\frac{2\pi}{9})+\cos^n(\frac{4\pi}{9})+\cos^n(\frac{8\pi}{9}))\in\mathbb{Z}$ 
*

*$a_n=2^n\left[\cos^n\left(\dfrac{2\pi}{9}\right)+\cos^n\left(\dfrac{4\pi}{9}\right)+\cos^n\left(\dfrac{8\pi}{9}\right)\right]$. Show that $a_n\in\mathbb{Z}$ for all $n\in\mathbb{Z}$.

*Find the last digit in $a_{10^6}$.
My progress:


*

*I believe it can be solved by expressing $a_n$ as a linear recurrence by using the cubic equation $x^3-3x+1=0$ which has the roots $x_1=2\cos\left(\dfrac{2\pi}{9}\right),x_2=2\cos\left(\dfrac{4\pi}{9}\right),x_3=2\cos\left(\dfrac{8\pi}{9}\right)$. I'm just not really sure how to connect $a_n$ to this cubic equation.

*I guess that if you could find a linear recurrence to $a_n$, the last digit would be cyclic and could be found that way. I was hoping to solve it without using computer work, but maybe that's tough.
Sorry if my $\TeX$ writing isn't correct. I'm still learning. Thanks!
 [/INST] The observation on the zeros of $x^3 - 3 x + 1$ means that:
$$
1 - \frac{12}{z} + \frac{8}{z^3}
$$
has $2 \cos \frac{2 \pi}{9}, 2 \cos \frac{4 \pi}{9}, 2 \cos \frac{8 \pi}{9}$ as inverses of its zeros,
which means that the recurrence:
$$
a_{n + 3} - 12 a_{n + 2} + 8 a_n = 0
$$
has general solution:
$$
a_n
  = c_1 2^n \cos^n \frac{2 \pi}{9}
     + c_2 2^n \cos^n \frac{4 \pi}{9}
     + c_3 2^n \cos^n \frac{8 \pi}{9}
$$
From the recurrence it is obvious that $a_n \in \mathbb{Z}$ for all $n$ if $a_0, a_1, a_2 \in \mathbb{Z}$. Would need to check those three cases of the above... in any case, $a_0 = 3$ is an integer. One down, two to go.
</s>