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

• Try $ax^3+bx^2+1$ first, remembering that $x^2=x+1$ so $x^3=x^2+x$. Then $ax^4+bx^3+1$ and try to spot a pattern. – Empy2 Oct 13 '19 at 6:30
• Sorry, I can't spot any pattern. – Crocogator Oct 13 '19 at 6:41
• As in Robert's answer, they turn out to be Fibonacci numbers – Empy2 Oct 13 '19 at 6:43
• @Empy2 Yes it looks like it has something to do with Fibonacci numbers but this question is there in the exercises in the end of the chapter and unfortunately there nothing given about Fibonacci numbers and I don't know anything about them. I believe there may be another way of solving this. – Crocogator Oct 13 '19 at 6:50
• It is just a sequence of numbers, but it crops up in many places. You will see it again. – Empy2 Oct 13 '19 at 7:09

## 4 Answers

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.

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.

• +1 Nice connection to the Fibonacci numbers. – Toby Mak Oct 13 '19 at 6:38
• @UnnayanUpadhyay Note that one of the roots of $x^2-x-1$ is the golden ratio, which also the ratio between consecuitive fibonacci numbers 'converges' to. – Certainly not a dog Oct 13 '19 at 6:52
• @UnnayanUpadhyay It is just a remark. You can go on and replace $x^2$ with $x+1$ and find what you need. – Robert Z Oct 13 '19 at 6:53
• @RobertZ oh thanks. – Crocogator Oct 13 '19 at 6:55
• @UnnayanUpadhyay See en.wikipedia.org/wiki/Golden_ratio and the link that I gave you in my answer. – Robert Z Oct 13 '19 at 6:57

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

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