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

contest-mathdivisibilityelementary-number-theorymodular arithmeticsolution-verification

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^{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.