Find a such that $ax^{17}+bx^{16}+1$ is divisible by $x^2-x-1$. 
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.
 A: 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.
A: 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.$$
A: 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).  
A: 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.
