Let $x^2 + 3x +1 = 0$. Is $x^{2048} + \dfrac{1}{x^{2048}}$ divisible by 3?

Question

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

Answer 1

Let $a_n = x^n + \dfrac{1}{x^n}\implies a_1 = 3, a_2 = 7, a_{n+1}= x^{n+1}+\dfrac{1}{x^{n+1}}= \left(x^n+\dfrac{1}{x^n}\right)\left(x+\dfrac{1}{x}\right) - \left(x^{n-1}+\dfrac{1}{x^{n-1}}\right)= 3a_n-a_{n-1}\implies a_{n+1} - 3a_n + a_{n-1} = 0$. From here you can use characteristic equation for difference equation and find the general term $a_n$ and from it you can find a closed form for $a_{2048}$.

Answer 2

To get a "closed form" solution, you can do the following:

• Simply evaluate roots, and write the answer as $\big(\frac{-3+\sqrt{5}}{2}\big)^{2048}+\big(\frac{-3-\sqrt{5}}{2}\big)^{2048}$

• Or, you could solve the recurrence relation as follows:

$s_n$ is defined in the question. $s_{n+1}=(s_n)^2-2$, where $s_0=-3$.
A solution is: $$s_n=2\cos(\cos^{-1}(-1.5)\cdot2^n)$$ Note the use of the identity $\cos(2\theta)=2\cos^2(\theta)-1$.
To compute $\cos^{-1}(-1.5)$, let $\cos(x+iy)=-1.5$, and proceed ($i$ is the imaginary unit). This gives a closed form.

Answer 3

Let $x$ be a root of $x^2 + 3x + 1$. Then $y = 1/x$ is also a root, since $$y^2 + 3y + 1 = (1/x)^2 + 3/x + 1 = \frac{1 + 3x + x^2}{x^2}$$ and $x \ne 0$. Moreover, for each positive integer $n$,

$$x^{n+1} + y^{n+1} = (x+y)(x^n + y^n) - xy(x^{n-1} + y^{n-1}).$$

Since $x + y = -3$ and $xy = 1$, it follows that

$$x^{n+1} + y^{n+1} = -3(x^n + y^n) - (x^{n-1} + y^{n-1}).$$ Taken modulo $3$, we see that if $f_n = x^n + y^n$,

$$f_{n+1} \equiv -f_{n-1} \pmod 3.$$

So for instance, with $f_0 = x^0 + y^0 = 2$, we have $$f_2 \equiv -f_0 \pmod 3, \\ f_4 \equiv -f_2 \equiv f_0 \pmod 3, \\ f_6 \equiv -f_4 \equiv -f_0 \pmod 3, \\ \vdots \\f_{2048} \equiv (-1)^{2048/2} f_0 = 2 \pmod 3.$$

Answer 4

If all you need is whether $s_{11}$ is divisible by $3$, this is much easier.

Note that $s_3$ is not divisible by $3$. Then it is simple to show using induction that $s_k \pmod 3 = 2$ for each $k \ge 4$. Indeed: $$s_{k+1}\pmod 3 = $$ $$(s^2_k \pmod 3)-2$$ $$ =1-2=2.$$

So $s_{11}=x^{2^{12}}+x^{-1×2^{12}}$ satisfies $s_{11}\pmod 3 =2$. So $s_{11}$ is not divisible by $3$.

Answer 5

Thank you all for those who answered. Different amazing solutions! But I'd still share my final solution, this is to be done as fast as possible so there's no proving needed and algebraic/arithmetic manipulation is probably the desired/suggested solution (not that mine is the optimal one, I just find this easier).

$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}}$

What is needed: $s_{11}$

$s_1 = -3$

$s_2 = 7$

$s_3 = 47$

$s_4 = 47^2 - 2 = 2207$

$\vdots$

Or simply, this can be done under mod 3:

$((((((((((-3)^2 - 2)^2 - 2)^2 - 2)^2 - 2)^2 -2)^2 -2)^2 -2)^2 -2)^2 - 2)^2 -2 $

The innermost is just $(-3)^2 - 2 \equiv 1~$ mod 3, and then it can even be done mentally continuing the process $(1)^2 - 2 \equiv -1~$ mod 3, squaring: $(-1)^2$ and getting the same, $(-1)^2 - 2 \equiv -1~$ mod 3 . Recognizing the pattern it's $-1 \equiv 2$ mod 3 all the way. So it isn't divisible by 3.

Answer 6

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.