RMO Practice Problem - Algebra 2

We are looking for $a,b$ such that $ax^{17} + bx^{16} = x^{16}(ax + b) = -1,$ where

$x^{2} = x + 1 \Longrightarrow x^{4} = x^{2} + 2x + 1 = 3x + 2 \Longrightarrow x^{8} = 9x^{2} + 12x + 4 = 21x + 13$

$\Longrightarrow x^{16} = 441x^{2} + 546x + 169 = 987x + 610.$

Now $x^{2} - x - 1 = 0 \Longrightarrow x = \dfrac{1 \pm \sqrt{5}}{2},$ so $x^{16} = 987*\dfrac{(1 \pm \sqrt{5})}{2} + 610 = \dfrac{2207 \pm 987\sqrt{5}}{2}.$

Thus $ax + b = -\dfrac{1}{x^{16}} \Longrightarrow a*\dfrac{(1 \pm \sqrt{5})}{2} + b = -\dfrac{2}{2207 \pm 987\sqrt{5}}$

$\Longrightarrow (a + 2b) \pm a\sqrt{5} = -\dfrac{4}{2207 \pm 987\sqrt{5}} * \dfrac{2207 \mp 987\sqrt{5}}{2207 \mp 987\sqrt{5}} = -2207 \pm 987\sqrt{5}.$

So for both cases we have that $a = 987$ and $a + 2b = -2207 \Longrightarrow b = -1597,$ and so

$a + b = 987 + (-1597) = \boxed{-610}.$

When $f(x)=ax^{17}+bx^{16}+1$ is divisible by $g(x)=x^2-x-1$ . It means that $f(x)$ has the same roots as $g(x)$ . Now, let us look at $x$ .

\(\begin{array} {} x = x + 0 & \Rightarrow x^1 = \color{blue}{F_1}x + \color{blue}{F_0} \quad \quad \color{blue}{F_n \text{ is the } n^{th} \text{ Fibonacci number}} \\ x^2 = x + 1 & \Rightarrow x^2 = F_2x + F_1 \\ x^3 = x^2 + x = 2x+1 & \Rightarrow x^3 = F_3x+F_2 \\ x^4 = 2x^2+x = 3x + 2 & \Rightarrow x^4 = F_4x+F_3 \\ x^5 = 3x^2 + 2x = 5x + 3 & \Rightarrow x^5 = F_5x+F_4 \\ ... & \Rightarrow x^{16} = F_{16}x + F_{15} \\ ... & \Rightarrow x^{17} = F_{17}x + F_{16} \end{array} \)

$\begin{aligned} \Rightarrow ax^{17} + bx^{16} + 1 & = 0 \\ (aF_{17}+bF_{16})x + aF_{16} + bF_{15} + 1 & = 0 \end{aligned}$

Equating the coefficients on both sides, we have:

$\begin{cases} aF_{17} + bF_{16} = 0 &...(1) \\ aF_{16} + bF_{15} = - 1 & ...(2) \end{cases}$

$\begin{cases} (1)\times F_{15}: & aF_{15}F_{17} + bF_{15}F_{16} = 0 &...(3) \\ (2) \times F_{16}: & aF_{16}^2 + bF_{15}F_{16} = - F_{16} &...(4) \end{cases}$

$\begin{cases} (3)-(4): & (\color{#3D99F6}{F_{15}F_{17}-F_{16}^2})a = F_{16} & \Rightarrow \color{#3D99F6}{(1)} a = F_{16} & \color{#3D99F6}{\text{By Cassini's identity*}} \\ (1): & F_{16}F_{17} + bF_{16} = 0 & \Rightarrow b = - F_{17} \end{cases}$

$\Rightarrow a = F_{16}$ and $b = -F_{17}$ and $a+b = F_{16}-F_{17} = - F_{15} = \boxed{-610}$

$\color{#3D99F6}{* }$ Cassini's identity $\color{#3D99F6}{\text{ }F_{n-1}F_{n+1} - F_n^2 = (-1)^n}$

Let $p$ , $q$ be the roots of the equation ${ x }^{ 2 }-x-1$ . By Vieta's theorem $p + q = 1$ and $pq = -1$ . Note that $p$ and $q$ must also be the roots of $\large\ a{ x }^{ 17 }+b{ x }^{ 16 }+1=0$ . Thus

$\large\ a{ p }^{ 17 }+b{ p }^{ 16 }=-1$ and $\large\ a{ q }^{ 17 }+b{ q }^{ 16 }=-1$ .

Multiplying the first of these equations by $q^{16}$ , the second one by $p^{16}$ , and using the fact that $pq = -1$ , we find

$\large\ ap+b=-{ q }^{ 16 }$ and $\large\ aq+b=-{ p }^{ 16 }$ . $(1)$

Thus

$\large\ a=\frac { { p }^{ 16 }-{ q }^{ 16 } }{ p-q } =({ p }^{ 8 }+{ q }^{ 8 })({ p }^{ 4 }+{ q }^{ 4 })({ p }^{ 2 }+{ q }^{ 2 })(p+q)$ .

Since

$p+q = 1$ ,

$\large\ { p }^{ 2 }+{ q }^{ 2 }={ (p+q) }^{ 2 }-2{ pq }=1+2=3$

$\large\ { p }^{ 4 }+{ q }^{ 4 }={ ({ p }^{ 2 }+{ q }^{ 2 }) }^{ 2 }-2{ (pq) }^{ 2 }=9-2=7$

$\large\ { p }^{ 8 }+{ q }^{ 8 }={ ({ p }^{ 4 }+{ q }^{ 4 }) }^{ 2 }-2{ (pq) }^{ 4 }=49-2=47$

it follows that $a = 1 . 3 . 7 . 47 = 987$ .

Likewise, eliminating a in $(1)$ gives

$\large\ -b=\frac { { p }^{ 17 }-{ q }^{ 17 } }{ p-q }$

$\large\ ={ (p }^{ 16 }+{ q }^{ 16 })-({ p }^{ 14 }+{ q }^{ 14 })+\quad ...\quad -({ p }^{ 2 }+{ q }^{ 2 })+1$

For $n > 1$ , let $\large\ { k }_{ 2n }={ p }^{ 2n }+{ q }^{ 2n }$ . Then ${ { k }_{ 2 }=3 }$ and ${ k }_{ 4 }=7$ , and

$\large\ { k }_{ 2n+4 }={ p }^{ 2n+4 }{ q }^{ 2n+4 }$

$\large\ ={ (p }^{ 2n+2 }+{ q }^{ 2n+2 })({ p }^{ 2 }+{ q }^{ 2 })-{ p }^{ 2 }{ q }^{ 2 }({ p }^{ 2n }+{ q }^{ 2n }$

$\large\ =3{ k }_{ 2n+2 }-{ k }_{ 2n }$

for $n\ge 3$ . Then ${ k }_{ 6 }=18$ , ${ k }_{ 8 }=47$ , ${ k }_{ 10 }=123$ , ${ k }_{ 12 }=322$ , ${ k }_{ 14 }=843$ , ${ k }_{ 16 }=2207$ .

Hence,

$-b = 2207- 843+322 - 123+47- 18+7- 3+ 1 = 1597$

or

$(a, b) = (987, -1597)$ .

So, $a+b=987-1597=-610$ .

Thus, answer : $\boxed{-610}$ .

In what follows we are going to assume that $x^2-x-1$ divides $ax^{17}+bx^{16}+1$ . Then we can see that any solution of $x^2-x-1=0$ must be a solution of $ax^{17}+bx^{16}+1=0$ .

Let $\alpha$ represent a solution of $x^2-x-1=0,$ then $\alpha^2=\alpha+1,$ and therefore for any natural number $n$ we have that $\alpha^{n+2}=\alpha^{n+1}+\alpha^n.\:\:\:\:\:\:(1)$
Now we can prove using induction that for any pair of real numbers $c$ and $d$ and for any natural numbers $n>2$ and $k<n$ the following is true: $c\: \alpha^n+d\:\alpha^{n-1}=(F_{k+1}\:c+F_{k}\: d) \alpha^{n-k}+(F_{k}\:c+F_{k-1}\:d)\alpha^{n-k-1}\:\:\:\:\:\:\:\:(2)$ where $F_m$ represents the $m-$ term of the Fibonacci sequence defined by $F_0=0,$ $F_1=1$ and $F_{m+1}=F_{m}+F_{m-1}.$ Let us prove first that (2) is true for $k=1$ . Indeed, using (1) we get that $c\: \alpha^n+d\:\alpha^{n-1}$ $=c(\alpha^{n-1}+\alpha^{n-2})+d\:\alpha^{n-1}= (c+d)\alpha^{n-1}+c\:\alpha^{n-2}=$ $(F_2 \:c+F_1\: d)\alpha^{n-1}+(F_1 \:c+F_0\: d)\alpha^{n-2}.$ Now let us prove that if (2) is true for any number natural $k<n$ then is would be true also for $k+1$ , of course, if $k+1 <n.$ Applying $(1)$ again we get that $c\: \alpha^n+d\:\alpha^{n-1}=(F_{k+1}\:c+F_{k}\: d) \alpha^{n-k}+(F_{k}\:c+F_{k-1}\:d)\alpha^{n-k-1}=$ $=(F_{k+1}\:c+F_{k}\: d)( \alpha^{n-k-1}+\alpha^{n-k-2})+(F_{k}\:c+F_{k-1}\:d)\alpha^{n-k-1}$ $=((F_{k+1}+F_k)\:c+(F_{k}+F_{k-1})\: d)( \alpha^{n-k-1})+(F_{k+1}\:c+F_{k}\:d)\alpha^{n-k-2}$ $=(F_{k+2}\:c+F_{k+1}\: d) \alpha^{n-k-1}+(F_{k+1}\:c+F_{k}\:d)\alpha^{n-k-2}.$ This completes the proof of (2)

Now using (2) with $n=17$ and $k=15$ we obtain that if $\alpha$ is a zero of $x^2-x-1=0$ then $0=a\:\alpha^{17}+b\:\alpha^{16}+1=(F_{16}\:a+F_{15}\:b)\alpha^2+(F_{15} a+F_{14} b)\alpha+1=$ $=(987 a+610 b)\alpha^2+(610a+377b)\alpha+1.$

Therefore the polynomial $ax^{17}+bx^{16}+1$ is divisible by $x^2-x-1$ if and only if $(987 a+610 b)x^2+(610a+377b)x+1$ is divisible by $x^2-x-1.$ Then $987 a+610 b=-1$ and $610a+377b=-1.$ The only solution of this system of equations is $(a, b)=(987, -1597).$ So the answer to the question is $a+b=987-1597=-610.$

For $ax^{17}+bx^{16}+1$ to be divisible by $x^2-x-1$ , $a \lambda^{17}+b \lambda^{16} + 1 = 0$ should be true for $\lambda$ being the roots of $x^2-x-1=0$

We can easily get $\lambda = \frac{1 \pm \sqrt{1+4}}{2} = \frac{1}{2} \pm \frac{\sqrt{5}}{2}$ .

Substituting for $\lambda$ we have two linear equations in $a,b$ as

$\left(\frac{1}{2}+\frac{\sqrt{5}}{2}\right)^{17}a+\left(\frac{1}{2}+\frac{\sqrt{5}}{2}\right)^{16}b=-1$

$\left(\frac{1}{2}-\frac{\sqrt{5}}{2}\right)^{17}a+\left(\frac{1}{2}-\frac{\sqrt{5}}{2}\right)^{16}b=-1$

Using Cramer's rule,

$a = \frac{-\left(\frac{1}{2}-\frac{\sqrt{5}}{2}\right)^{16}+\left(\frac{1}{2}+\frac{\sqrt{5}}{2}\right)^{16}}{\left(\frac{1}{2}+\frac{\sqrt{5}}{2}\right)^{17}\left(\frac{1}{2}-\frac{\sqrt{5}}{2}\right)^{16}-\left(\frac{1}{2}-\frac{\sqrt{5}}{2}\right)^{17}\left(\frac{1}{2}+\frac{\sqrt{5}}{2}\right)^{16}}=987$

$b = \frac{\left(\frac{1}{2}-\frac{\sqrt{5}}{2}\right)^{17}-\left(\frac{1}{2}+\frac{\sqrt{5}}{2}\right)^{17}}{\left(\frac{1}{2}+\frac{\sqrt{5}}{2}\right)^{17}\left(\frac{1}{2}-\frac{\sqrt{5}}{2}\right)^{16}-\left(\frac{1}{2}-\frac{\sqrt{5}}{2}\right)^{17}\left(\frac{1}{2}+\frac{\sqrt{5}}{2}\right)^{16}}=-1597$

Thus, giving $a+b = \boxed{-610}$

This is not a solution.

Use long division and you will find that remainder in each step follows a pattern. Find the pattern and find remainder finally. If the final remainder is mx+n, then m=n=0. Using this, try to get the values of a and b.