Find $a$, $b$ such that $x^2 - x -1$ is a factor of $ax^9 + bx^8 + 1$

Say $c$ and $d$ are zeroes of $x^2-x-1$ then they are zeros of $ax^9+bx^8+1$ too.

Since $c^2 = c+1$ we have $$c^4=c^2+2c+1=3c+2$$ and $$c^8 = 9c^2+12c+4 = 21c+13$$

and finnaly $c^9 = 34c+21$.

So we have $$a(34c+21)+b(21c+13)+1=0$$ or $$boxed{(34a+21b)c+ (21a+13b+1)=0}$$ Simmilay we have for $d$: $$boxed{(34a+21b)d+ (21a+13b+1)=0}$$

so if we substract equation and since $cne d$ we have $$(34a+21b)(c-d) = 0implies 34a+21b=0$$

and thus $$21a+13b+1=0$$

Now solve this system and you are done.

Consider $P(x)= ax^9+bx^8+1$ and $alpha$ one of the numbers$frac{1 pm sqrt 5}{2}.$

We have equalities:

$alpha^2$ = $alpha$ + 1, $alpha^4$ = 3$alpha$ + 2, $alpha^8$ = 21$alpha$ + 13, $alpha^9$ = 34$alpha$ + 21.

(The coefficients to the right of the equations are terms of the Fibonacci sequence)

From $P(alpha) = 0$ results $a(34alpha + 21) +b(21alpha + 13) + 1 =0$ and then $(34a + 21b)alpha + 21a + 13b + 1 = 0$

If $a$ and $b$ are rational numbers then $$ a = 21, b = -34.$$

Consider $$frac{a x^9+bx^8+1}{x^2-x-1}$$ perform long division to get $$-1+x-2 x^2+3 x^3-5 x^4+8 x^5-13 x^6+21 x^7-(b+34) x^8+x^9 (-a+b+55)+Oleft(x^{10}right)$$ So $b=-34$ and $a=21$ and the result is $$frac{a x^9+bx^8+1}{x^2-x-1}=-1+x-2 x^2+3 x^3-5 x^4+8 x^5-13 x^6+21 x^7$$

Write $ax^9+bx^8+1=(x^2-x-1)sumlimits_{k=0}^7c_kx^{7-k}$ which gives the initial conditions $c_7=-1$ and $-c_7-c_6=0implies c_6=1$. Notice that $c_0=a$ and $c_1-c_0=b$ on equating coefficients.

Further, we have $c_i=c_{i-1}+c_{i-2}$ for $i>1$ which is the negative Fibonacci sequence shifted by one. In particular, $c_{7-i}=(-1)^{i+1}F_{i+1}$ so $c_0=F_8$ and $c_1=-F_7$. Hence $a=21$ and $b=-34$.

Put $A = x^2 - x - 1$, $B = ax^9 + bx^8 + 1$ now we want $B/A$ to divide without remainder. We can subtract multiples of $A$ from $B$ to kill off high order terms and see what the remainder would be:

B
- a*x^7*A
= (a + b)*x^8 + a*x^7 + 1

- (a + b)*x^6*A
(2*a + b)*x^7 + (a + b)*x^6 + 1

- (2*a + b)*x^5*A
(3*a + 2*b)*x^6 + (2*a + b)*x^5 + 1

We find

Q = a*x^7 + (a + b)*x^6 + (2*a + b)*x^5
  + (3*a+2*b)*x^4 + (5*a + 3*b)*x^3 + (8*a + 5*b)*x^2
  + (13*a + 8*b)*x + (21*a + 13*b)

R = (34*a + 21*b)*x + 21*a + 13*b + 1

via B - Q A = R

So we need to solve the system

• $34a + 21b = 0$
• $21a + 13b + 1 = 0$

To get no remainder.