Find a such that $ax^{17}+bx^{16}+1$ is divisible by $x^2-x-1$.

Question

Find $a$ such that $ax^{17}+bx^{16}+1$ is divisible by $x^2-x-1$.

I tried taking the roots of the polynomial which are $\frac{1±\sqrt{5}}{2}$

And I got the equation $a(\frac{1±\sqrt{5}}{2})^{17}+b(\frac{1±\sqrt{5}}{2})^{16}+1=0$

Now I don't know what to do next.

Any help would be appreciated.

Answer 1

The given divisor has roots $\varphi=\frac{1+\sqrt5}2$ and $-\frac1\varphi$, so the $17$th-degree polynomial must also have these roots. This gives a system of equations for $a$ and $b$, which can then be solved.

The high exponents can be simplified by using the property $\varphi^2=\varphi+1$: $$\varphi^4=3\varphi+2$$ $$\varphi^8=21\varphi+13$$ $$\varphi^{16}=987\varphi+610$$ $$\varphi^{17}=1597\varphi+987$$ Thus $$a\varphi^{17}+b\varphi^{16}+1=0\implies a(1597\varphi+987)+b(987\varphi+610)=-1$$ $$-a\varphi^{-17}+b\varphi^{-16}+1=0\implies -a+b\varphi=-1597\varphi-987$$ We can see that $a=987,b=-1597$ is a solution to this system, and hence the original problem.

Answer 2

Hint. If $x=\frac{1±\sqrt{5}}{2}$ then $x^2=x+1$ and \begin{align} ax^{17}+bx^{16}+1 &=(ax+b)(x+1)^8+1 \\ &=(ax+b)(x^2+2x+1)^4+1\\ &=(ax+b)(3x+2)^4+1\\ &=(ax+b)(21x+13)^2+1. \end{align} Can you take it from here? Note that 3,2, 21,13 are all Fibonacci numbers.

Answer 3

As you observed correctly, the 17th degree polynomial must also have the same roots ($\frac{1\pm\sqrt5}2$). Substituting these roots into $ax^{17}+bx^{16}+1=0$, you get two equations which can be solved simultaneously for $a$ and $b$, yielding $$a=987 \qquad \text{and} \qquad b=-1597.$$

Answer 4

Let $\alpha$ and $\beta$ be the two roots of the polynomial $x^2-x-1$. Observe that $\alpha\beta=-1$. Then, $$a\alpha^{17}+b\alpha^{16}+1=0$$ and $$a\beta^{17}+b\beta^{16}+1=0\,.$$ This means $$a\alpha+b=-\frac{1}{\alpha^{16}}=-\left(-\frac{1}{\alpha}\right)^{16}=-\beta^{16}\,.$$ Similarly, $$a\beta+b=-\alpha^{16}\,.$$ Consequently, $$(\alpha-\beta)\,a=\left(\alpha^{16}-\beta^{16}\right)\text{ or }a=\left(\frac{\alpha^{16}-\beta^{16}}{\alpha-\beta}\right)=F_{16}\,,$$ where $F_k$ is the $k$-th Fibonacci number (i.e., $F_0=0$, $F_1=1$, and $F_k=F_{k-1}+F_{k-2}$ for all integers $k$).

In the same manner, $$a-b\beta=a+\frac{b}{\alpha}=-\frac{1}{\alpha^{17}}=\beta^{17}$$ and $$a-b\alpha=a+\frac{b}{\beta}=-\frac{1}{\beta^{17}}=\alpha^{17}\,,$$ whence $$(\alpha-\beta)\,b=-\left(\alpha^{17}-\beta^{17}\right)\,.$$ Thus, $$b=-\left(\frac{\alpha^{17}-\beta^{17}}{\alpha-\beta}\right)=-F_{17}\,.$$

In general, if $n$ is a positive integer and $ax^{n+1}+bx^n+1\in\mathbb{R}[x]$ is divisible by $x^2-x-1$, then $$a=(-1)^n\,F_n\text{ and }b=(-1)^{n+1}\,F_{n+1}\,.$$ Even more generally, let $K$ be an arbitrary field, and $p$ and $q$ any elements of $K$ such that $q\neq 0$. Suppose that $ax^{n+1}+bx^n+1\in K[x]$ is divisible by $x^2+px+q$. Then, $$a=\frac{1}{q^n}\,f_n(p,q)\text{ and }b=-\frac{1}{q^n}\,f_{n+1}(p,q)\,,$$ where $f_0(p,q):=0$, $f_1(p,q):=1$, and $$f_k(p,q)+p\,f_{k-1}(p,q)+q\,f_{k-2}(p,q)=0$$ for all $k\in\mathbb{Z}$. The proof is very much the same (except for the case $p^2=4q$, which has to be dealt with separately).