Let $x^2 + 3x +1 = 0$. Is $x^{2048} + \dfrac{1}{x^{2048}}$ divisible by 3? Let $x^2  + 3x +1 = 0$. Solve for $x^{2048} + \dfrac{1}{x^{2048}}$. Is it divisible by 3?
$x^2 + 1 = -3x \Rightarrow x+ \dfrac{1}{x} = -3$
$x^2 + \dfrac{1}{x^2} = (x + \dfrac{1}{x})^2 - 2 = 9 -2 = 7$
$x^4 + \dfrac{1}{x^4} = (x^2 + \dfrac{1}{x^2})^2 - 2 = 49 - 2 = 47$
seeing the pattern, let $s_n = x^{2^n} + \dfrac{1}{x^{2^n}}$
I need $s_{11}$
$s_1 = -3$
$s_2 = 7$
$s_3 = 47$
$s_4 = 47^2 - 2 = 2207$
$\vdots$
$((2207^2 -2)^2 - 2)^2 -2)^2 ... - 2)$
quite big
But I realized I didn't have to simplify it, I just have to check if
$((((((2207^2 - 2)^2 -2)^2 -2)^2 -2)^2 -2)^2 - 2)^2 -2$ is divisible by 3

Say we have checked that $x^n + y^n \equiv 2 \mod d$ for some $n$, $d$. Then $x'=x^n$, $y'=y^n$ are roots of an equation
$$T^2 - (2 + s \cdot d)\,T+1$$
Now, for all such equations, the sums $x'^k + y'^k$ will be the same  $\mod d$. For the particular equation $T^2 - 2 T + 1$ they equal $2$. We conclude that $x^{k n} + y^{k n} \equiv 2 \mod d$ for all $k$.
$\bf{Added:}$ In our case, $x^4 + y^4 = 47 \equiv 2 \mod 45$. We conclude that $x^{4k} + y^{4k} \equiv 2 \mod 45$ for all $k\ge 1$.
Or: $x^3 + y^3 = -18 \equiv 2 \mod 20$, so $x^{3k} + y^{3k} \equiv 2 \mod 20$ for all $k\ge 1$.
$\bf{Added:}$ (This should come first) For the equation $T^2+1=0$ the sums $x^{4k} + y^{4k}=2$. So for any equation $T^2 + a T + b=0$, congruent to $T^2+1$ $\mod d$ the sums $x^{4k} + y^{4k} \equiv 2 \mod d$.
Take home idea: For congruent equations $P_1(T) \equiv P(T) \mod d$ the corresponding symmetric functions will be congruent. Use congruent equations for which those symmetric functions are easy to calculate.
