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. 
 A: Still another approach (and a quite compact one). Since
$$ \frac{1}{1-x-x^2}=\sum_{n\geq 0}F_{n+1} x^n \tag{1}$$
it is not difficult to write down the Taylor series of $\frac{1+bx^{16}+a x^{17}}{1+x-x^2} $:
$$\frac{1+bx^{16}+a x^{17}}{1+x-x^2}=\sum_{n\geq 0}(-1)^n\left(F_{n+1} x^n + bF_{n+1} x^{n+16} + a F_{n+1} x^{n+17}\right) \tag{2}$$
If $1+x-x^2$ is a divisor of $1+bx^{16}+ax^{17}$, the RHS of $(2)$ is a polynomial with degree $\leq 15$, hence the coefficients of $x^{16}$ and $x^{17}$ have to be zero. That translates into:
$$ F_{17}+b = 0,\qquad F_{18}+b-a = 0\tag{3}$$
from which $(a,b)=(F_{16},-F_{17})=\color{red}{(987,-1597)}$ readily follows. Now we just have to check that, with this choice, for any $m\geq 18$ the coefficient of $x^m$ in the RHS of $(2)$ is actually zero. That is easy by induction.
A: $$x^2-x-1=
\left( x-\frac{1+\sqrt{5}}{2} \right)\left( x-\frac{1-\sqrt{5}}{2} \right)$$
By factor theorem,
\begin{align*}
  a\left( \frac{1+\sqrt{5}}{2} \right)^{17}+
  b\left( \frac{1+\sqrt{5}}{2} \right)^{16}+1 &=0 \quad \cdots \cdots \: (1) \\
  a\left( \frac{1-\sqrt{5}}{2} \right)^{17}+
  b\left( \frac{1-\sqrt{5}}{2} \right)^{16}+1 &=0 \quad \cdots \cdots \: (2)
\end{align*}
$\left( \frac{1-\sqrt{5}}{2} \right)^{16} \times (1)
-\left( \frac{1+\sqrt{5}}{2} \right)^{16} \times (2)$,
$$a\sqrt{5}
=\left( \frac{1+\sqrt{5}}{2} \right)^{16}
-\left( \frac{1-\sqrt{5}}{2} \right)^{16}$$

$$a=F_{16}=987$$

$\left( \frac{1-\sqrt{5}}{2} \right)^{17} \times (1)
-\left( \frac{1+\sqrt{5}}{2} \right)^{17} \times (2)$,
$$-b\sqrt{5}
=\left( \frac{1+\sqrt{5}}{2} \right)^{17}
-\left( \frac{1-\sqrt{5}}{2} \right)^{17}$$

$$b=-F_{17}=-1597$$

In general,
$$
\frac{F_{n} x^{n+1}-F_{n+1} x^n+(-1)^n}{x^2-x-1}=
F_{n} x^{n-1}-F_{n-1} x^{n-2}+\ldots+(-1)^{n-1}F_{1}$$
A: A slightly different (but longer) method:
Let roots of $x^2-x-1$ be $c$ and $d$
Using Vieta's formulas, we get 
$$c+d=1\tag{1}$$
$$cd=-1\tag{2}$$
Using Factor theorem, we get 
$$ac^{17}+bc^{16}=-1\tag{3}$$
$$ad^{17}+bd^{16}=-1\tag{4}$$
Multiplying $(3)$ with $d^{16}$ and using $(2)$, we get 
$$ac+b=-d^{16}\tag{5}$$
Multiplying $(3)$ with $c^{16}$ and using $(2)$, we get
$$ad+b=-c^{16}\tag{6}$$
Subtracting $(6)$ from $(5)$, we get 
$$a(c-d)=c^{16}-d^{16} \Rightarrow a=\frac{c^{16}-d^{16}}{c-d}=(c+d)(c^2+d^2)(c^4+d^4)(c^8+d^8)$$
Likewise, eliminating $a$, we get $$-b=\frac{p^{17}-q^{17}}{p-q}=p^{16}+p^{15}q+ \cdots + q^{16}$$
Using simple algebraic manipulations we get $a=987$ and correspondingly $b=-1597$, which are left as an exercise to reader.

Hint:

 Using $(1)$ and $(2)$, we give the finishing touch to this problem.


Answer to the exercise left to readers:

 $c+d=1$ 
 $c^2+d^2=(c+d)^2-2cd=3$ 
 $c^4+d^4=(c^2+d^2)^2-2c^2d^2=7$ 
 $c^8+d^8=(c^4+d^4)^2-2c^4d^4=47$ 



 So, $\color{red}{a=1 \cdot 3 \cdot 7 \cdot 47=987}$



 $-b=(c^{16}+d^{16})-(c^{14}+d^{14})+ \cdots -(c^2+d^2)+1$ 
 Let $k_{2n}=c^{2n}+d^{2n}$ 
 Also, $ k_{2n+4}=3k_{2n+2}-k_{2n}$ 


We have 

$$\begin{array}{c c c} \\
   k_0 & 2 \\
   k_2 & 3\\
   k_4 & 7\\
   k_6 & 18\\
   k_8 & 47\\
   k_{10} & 123\\
   k_{12} & 372\\
   k_{14} & 843\\
   k_{16} & 2207\\
   \end{array}$$



 Thus, $\color{blue}{b=-(2207-843+322-123+47-18+7-3+2)=-1597}$

A: 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$.)
A: Strictly addressing what went wrong in the OP's long division approach, the constant term in $Q$ should be $(987a+610b)$, not $(610a+377b)$.  The sequence of coefficients, starting from $x^{15}$ and going down to $x^0$, is $a,a+b,2a+b,3a+2b,5a+3b,\ldots,987a+610b$.
A: The polynomial $x^2-x-1$ divides  $ax^{17}+bx^{16}+1$ if and only if
$$a\phi_+^{17}+b\phi_+^{16}=-1\quad\mbox{and}\quad a\phi_-^{17}+b\phi_-^{16}=-1,$$
where $\phi_{\pm}$ are the solutions of $x^2-x-1=0$.
Then, after adding, and subtracting the two equations we find
$$aL_{17}+bL_{16}=-2\quad\mbox{and}\quad aF_{17}+bF_{16}=0$$
where $F_n$ and $L_n$ are the Fibonacci and Lucas numbers,
that is
$$3571a+2207b = -2\quad\mbox{and}\quad 1597a+987b = 0.$$
Finally by solving the linear system we get $a=987$ and $b=-1597$.
