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.
 A: 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.
A: 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.
