POTW #354: Find Possible Value of a-b When $x^2-x-1$ Divides $ax^{17}+bx^{16}+1$

[anemone]

Here is this week's POTW:

-----

If $x^2-x-1$ divides $ax^{17}+bx^{16}+1$ for integer $a$ and $b$, find the possible value of $a-b$.

-----

Remember to read the https://mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to https://mathhelpboards.com/forms.php?do=form&fid=2!

 

[anemone]

Congratulations to the following members for their correct solution!(Cool)

1. castor28
2. Opalg
3. Olinguito
4. lfdahl
5. kaliprasad

Solution from Opalg:

Spoiler

The golden ratio $\phi = \frac{1+\sqrt5}2$ is a root of $x^2-x-1=0$. So if that quadratic divides $ax^{17} + bx^{16} + 1$ then $a\phi^{17} + b\phi^{16} + 1 = 0$. But the powers of $\phi$ are given by $\phi^n = F_n\phi + F_{n-1}$, where $F_n$ is the $n$th Fibonacci number. Therefore $$a(F_{17}\phi + F_{16}) + b(F_{16}\phi + F_{15}) + 1 = 0.$$ Now substitute $\phi = \frac{1+\sqrt5}2$ into that equation. If $a$ and $b$ are integers then the rational part of the left side of the equation, and the part involving multiples of $\sqrt5$, must both be zero. So $$\tfrac12 aF_{17} + aF_{16} + \tfrac12 bF_{16} + bF_{15} + 1 = 0,$$ $$aF_{17} + bF_{16} = 0,$$ and therefore $ aF_{16} + bF_{15} + 1 = 0.$

Write the equations $ aF_{16} + bF_{15} + 1 = 0$ and $ aF_{17} + bF_{16} = 0$ as $$(a-b)F_{16} + b(F_{15} + F_{16}) + 1 = 0,$$ $$(a-b)F_{17} + b(F_{16} + F_{17}) = 0.$$ From the Fibonacci property $F_n + F_{n-1} = F_{n+1}$ it follows that $$(a-b)F_{16} + bF_{17} + 1 = 0,$$ $$(a-b)F_{17} + bF_{18} = 0.$$ Solve those as simultaneous equations, multiplying the first one by $F_{18}$ and the second one by $F_{17}$, and subtracting: $$(a-b)(F_{16}F_{18} - F_{17}^2) + F_{18} = 0.$$ Then the Fibonacci property $F_n^2 - F_{n-1}F_{n+1} = (-1)^{n-1}$ gives $a-b = F_{18}$. The 18th Fibonacci number is $2584$, so the conclusion is that $a-b = 2584.$

Alternate solution from kaliprasad:

Spoiler

If $x^2-x-1$ divides $ax^{17}+bx^{16} + 1$ then $x^2=x+1$ => $ax^{17}+bx^{16} + 1 = 0$
The above is so because x =t which is root of $x^2= x+1$ is also a root of $ax^{17}+bx^{16} + 1= 0$
We have $x^2=x+1$
Putting $y=\frac{1}{x}$ we get $\frac{1}{y^2} = \frac{1}{y} +1$
or $y^2 = 1 - y$
or $y^4 = (1-y)^2 = 1-2y +y^2 = (1-2y) + (1-y) = 2-3y$
or $y^8 = (2-3y)^2 = 4-12y +9y^2 = (4-12y) + 9(1-y) =13-21y$
or $y^{16} = (13-21y)^2 = 169-546y +441y^2 = (169-546y) + 441(1-y) = 610-987y$
or $y^{17} = 610y-987y^2 = 610y - 987(1-y) = 1597y - 987$
Putting back $x=\frac{1}{y}$ we get
$\frac{1}{x^{17}} = \frac{1597}{x} - 987$
Or $987x^{17} - 1597x^{16} +1 $ = 0

Comparing with above we get a = 987, b = - 1597 so a - b = 2584