<s>[INST] find integers a and b such $x^2-x-1$ divides $ax^{17}+bx^{16}+1 = 0$ 
find integers a and b  such $x^2-x-1$ divides  $ax^{17}+bx^{16}+1  = 0$


By really long division i got :-
$$Q=ax^{15} + (a+b)x^{14} + \dots +(610a + 377b) $$
$$R = x(987a+610b)+1+610a+377b$$
since remainder is $0 $,
$$987a+610b = 0$$
$$1+610a+377b = 0$$
from which i got $a = -610, b = 987$
but from wolfram alpha the remainder of $-610x^{17}+987x^{16}+1  \over x^2-x-1$ is $x-1$
Somebody please show me where i went wrong ?
Thanks. 
 [/INST] Alternatively, observe that $x^2-x-1$, $x^3-2x^2+1$, and $2x^4-3x^3-1$ are the only polynomials degree less than $5$ divisible by $x^2-x-1$ which are of the form $A\,x^{n+1}+B\,x^{n}+C$ with $A,B,C\in\mathbb{Z}$, $A>0$, and $\gcd(A,B,C)=1$.  We suppose that $a_n\,x^{n+1}-b_n\,x^n+(-1)^n$ is divisible by $x^2-x-1$ for each $n\in\mathbb{N}$.  Then, for all integera $n>1$, 
$$
\begin{align}
\left(a_n\,x^{n+1}-b_n\,x^n+(-1)^n\right)+\left(a_{n-1}\,x^n-b_{n-1}\,x^{n-1}+(-1)^{n-1}\right)\phantom{aaaaaaaaaaaa}
\\\phantom{aaaaaaaaaaaa}=\left(a_n\,x^2-\left(b_{n}-a_{n-1}\right)\,x-b_{n-1}\right)x^{n-1}
\end{align}$$
must be divisible by $x^2-x-1$.  This means $a_n=b_{n}-a_{n-1}=b_{n-1}$ for each integer $n>1$.  Therefore, $b_{n}=a_n+a_{n-1}$ and $b_{n}=a_{n+1}$, whence
$$a_{n+1}=a_n+a_{n-1}\text{ and }b_n=a_{n+1}\,.$$
Since $a_1=F_1$ and $a_2=F_2$, we conclude that $a_n=F_n$ and $b_n=F_{n+1}$ for all $n\in\mathbb{N}$.  Here, $\left(F_n\right)_{n=1}^\infty$ is the standard Fibonacci sequence: $F_0=F_1=1$ and $F_{n+1}=F_n+F_{n-1}$ for $n-1,2,3,\ldots$.  In particular, $F_{16}\,x^{17}-F_{17}\,x^{16}+1$ is the only polynomial of the form $A\,x^{n+1}+B\,x^{n}+C$ with $A,B,C\in\mathbb{Z}$, $A>0$, and $\gcd(A,B,C)=1$ divisible by $x^2-x-1$.

In general, if complex numbers $\alpha$ and $\beta$ are such that $\alpha\neq 0$ and $\beta^2\neq 4\alpha$, then there exist unique $a_n,b_n\in\mathbb{C}$ such that $a_n\,x^{n+1}+b_n\,x^n+1$ is divisible by $\alpha\,x^2+\beta\,x+1$.  If the complex numbers $u$ and $v$ are the two roots of $\alpha\,x^2+\beta\,x+1$, say, $u=\frac{-\beta+\sqrt{\beta^2-4\alpha}}{2\alpha}$ and $v=\frac{-\beta-\sqrt{\beta^2-4\alpha}}{2\alpha}$, then
$$a_n=\alpha^n\,\left(\frac{u^n-v^n}{u-v}\right)$$
and 
$$b_n=-\frac{a_{n+1}}{\alpha}=-\alpha^n\,\left(\frac{u^{n+1}-v^{n+1}}{u-v}\right)$$
for all $n=0,1,2,\ldots$.  If $\beta^2=4\alpha$, then there is a unique root $z:=-\frac{\beta}{2\alpha}$ of $\alpha\,x^2+\beta\,x+1$.  In this case,
$$a_n=n\,\alpha^{n}\,z^{n-1}\text{ and }b_n=-(n+1)\,\alpha^{n}\,z^n$$
for all $n=0,1,2,\ldots$.  (In fact, $\mathbb{C}$ can be replaced by any field, and we just have to work in the splitting field of $\alpha\,x^2+\beta\,x+1$.)
</s>