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

  • Thread starter Thread starter anemone
  • Start date Start date
AI Thread Summary
The problem involves determining the values of integers a and b such that the polynomial ax^17 + bx^16 + 1 is divisible by x^2 - x - 1. The divisibility condition leads to specific relationships between a and b, which can be explored through polynomial long division or by substituting roots of the divisor. Several members successfully provided solutions, showcasing different approaches to the problem. The discussion highlights the importance of understanding polynomial divisibility in algebra. The final goal is to find the possible value of a - b.
anemone
Gold Member
MHB
POTW Director
Messages
3,851
Reaction score
115
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!
 
Physics news on Phys.org
Congratulations to the following members for their correct solution!(Cool)

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

Solution from Opalg:
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:
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
 
Back
Top