find integers a and b such $x^2-x-1$ divides $ax^{17}+bx^{16}+1 = 0$

Question

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.

Answer 1

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$.

Answer 2

$$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}$$

Answer 3

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$.)

Answer 4

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}$

Answer 5

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$.

Answer 6

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.