When does $x + x^{-1}$ divide $x^n +x^{-n}$?

I have been attempting to solve the following problem and am not sure if I have solved it correctly and how to prove a certain case at the end,

Let x be a real number such that $t = x + x^{−1}$ is an integer greater than 2. Prove that $t_n = x^n + x^{−n}$ is an integer for all positive integers n. Determine the values of n for which t divides $t_{n}$.

For the first part I noted that $t_{n+1} = t*t_n-t_{n-1}$ which is very simple to prove just by multiplying the ts together. Then I proved that $t_{2}$ was an integer employing a similar method to the formula and argued that $t_{n}$ must then be an integer by induction.

For the second part of the question I first considered $x+x^{-1} \cong 0\mod( x+x^{-1})$ which then implies $x\cong-x^{-1}$. With this fact consider $x^n + x^{-n}$ where n is odd. I get $x^{2k+1} + x^{-(2k+1)}\cong x^{2k+1} + (x^{-1})^{2k+1}\cong x^{2k+1} - x^{2k+1} \cong 0 \mod (x+x^{-1})$.

My question is then how do I prove that n cannot be even for t to divide $t_n$ and also is it okay to use modular arithmetic for this question since x is not actually an integer.

For the first bit I was thinking I could maybe do something with infinite descent since $t_{n+2}\cong -t_n$ so if t divides $t_n$ then it must divide all $t_{n}$ with the same parity. So if t doesn't divide $t_{2}$ there is a contradiction I'm just not sure how to show this.

Recall the identity

$$a^{n+1} + b^{n+1} = (a+b)(a^n + b^n) - ab(a^{n-1} + b^{n-1}).$$ So letting $a = x$, $b = 1/x$, then $ab = 1$ and we obtain $$x^{n+1} + x^{-(n+1)} = (x + x^{-1})(x^n + x^{-n}) - (x^{n-1} + x^{-(n-1)}),$$ or $$t_{n+1} = t_1 t_n - t_{n-1},$$ where I have slightly modified your notation: $t = t_1 = x + x^{-1}$. So, if $t$ is an integer, then $t_2$ is also an integer since $t_2 = t_1 t_1 - t_0$ and $t_0 = 2$ for any nonzero $x$. The rest follows by induction on $n$.

As for divisibility, note that if $t_1$ is an integer greater than $2$, then $t_1$ cannot divide $t_0 = 2$. So $t_2 = t_1^2 - t_0$ is not divisible by $t_1$. But $t_3 = t_1 t_2 - t_1$ is divisible by $t_1$, and $t_4 = t_1 t_3 - t_2$ is not. By now we can see the pattern: $t_n$ is divisible by $t_1$ if and only if $n$ is odd. I leave the formal proof of this fact as an exercise for the reader.

Define a sequence of polynomials $\{T_n\}_{n\ge 0}$ in $\mathbb{Z}[X]$ by $T_0=1$, $T_1=X$ and $$ T_{n+1} = 2XT_n-T_{n-1}. $$ These are called the Chebyshev Polynomials of the first kind, and they have many fascinating properties. For example,

Claim: For all $n$, we have $T_n\left(\frac{x^{-1}+x}{2}\right)=\frac{x^n+x^{-n}}{2}\in\mathbb{Q}[x,x^{-1}]$.

Proof: By induction on $n$. The cases $n=0,1$ are clear. Now, for the induction step, $$ \begin{align*} T_{n+1}\left(\frac{x+x^{-1}}{2}\right)&=2\left(\frac{x+x^{-1}}{2}\right)T_n\left(\frac{x^{n}+x^{n-1}}2\right)-\frac{x^{n-1}+x^{1-n}}{2}\\ &= \frac12\left[(x+x^{-1})\left(x^{n}+x^{-1}\right)-x^{n-1}-x^{1-n}\right]\\ &=\frac{x^{n+1}-x^{-n-1}}{2} \end{align*} $$ as desired. $\square$

Corollary: Putting $x=e^{i\theta}$, we find that $T_n(\cos \theta)=\cos(n\theta)$ for all $\theta\in\mathbb{R}$. In fact, $T_n$ is the unique polynomial with this property.

To answer your question, we consider a slightly altered version of the Chebyshev polynomials. Define a sequence $\{f_n\}_{n\ge 1}$ by $f_n=2T_n(\frac X2)$. Note that $f_0=2$ and $f_1=X$. Furthermore, for all $n\ge 1$, we have $$ f_{n+1} = 2T_{n+1}(\frac{X}{2}) = 2\left(2\cdot \frac X2T_n(X/2)-T_{n-1}(X/2)\right)=X\cdot 2T_{n}(X/2) - 2T_{n-1} = Xf_n-f_{n-1}, $$ so the $f_n$ still have integer coefficients. Moreover, the property of $T_n$ turns into $$ f_n(x+x^{-1}) = x^n+x^{-n}. $$ Now, suppose that we have some $a\in\mathbb{C}$ such that $k:=a+a^{-1}$ is an integer. Then $a^{n}+a^{-n}=f_n(a+a^{-1})=f_n(k)$ must also be an integer, since we are evaluating a polynomial with integer coefficients at an integer!

Next, we can write $f_n=Xg+f_n(0)$, where $g$ is some polynomial, and $f_n(0)$ is the constant coefficient of $f_n$. Suppose that $a+a^{-1}=k$ is an integer, then $$ a^{n}+a^{-n} = f_n(a+a^{-1}) = k\cdot g(k)+f_n(0). $$ Because $g(k)$ is a polynomial with integer coefficients evaluated in an integer, it must be an integer. Therefore, $a^{n}+a^{-n}\equiv f_n(0)\pmod k$, so $a+a^{-1}$ divides $a^n+a^{-n}$ if and only if it divides $f_n(0)$.

Evaluating the recursion in $0$, we find that $f_0(0)=2$ and $f_1(0)=0$ and $$ f_{n+1}(0) = -f_{n-1}(0). $$ We find that (this can very easily be proven by induction) $$ f_n(0) = \begin{cases}0\quad&\text{if $2\nmid n$}\\(-1)^{n/2}2&\text{if $2\mid n$}\end{cases} $$ So if $n$ is odd, we have $a+a^{-1}\mid 0 = f_n(0)$ and $a+a^{-1}\mid a^{n}+a^{-n}$. However, if $n$ is even, then $a^n+a^{-n}\equiv \pm 2 \pmod{a+a^{-1}}$. Because it was given that $a+a^{-1}>2$, we do not have divsibility in this case.