Problem:
Find a if a and b are integers such that x2−x−1 is a factor of ax17+bx16+1.
Solution:
Since the roots of x2−x−1=0 are p=21(1+5) and q=21(1−5), these must also be roots of ax17+bx16+1=0. Thus
ap17+bp16=−1 and aq17+bq16=−1
Multiplying the first of these equations by q16, the second one by p16, and using the fact that pq=−1, we find that
ap+b=−q16 and aq+b=−p16
Thus
a=p−qp16−q16=(p8+q8)(p4+q4)(p2+q2)(p+q)(1)
Since
p+qp2+q2p4+q4p8+q8=1=(p+q)2−2pq=1+2=3,=(p2+q2)2−2(pq)2=9−2=7,=(p4+q4)2−2(pq)4=49−2=47,
substitution into (1) yields
a=(47)(7)(3)(1)=987.
Note. Substituting for p and q into (1) gives
a=51⎣⎢⎡(21+5)16−(21−5)16⎦⎥⎤
whose right side may be recognized as (the Binet form of) the 16-th
Fibonacci number F16. It is easiest to compute F16 by iteration, using the recursive definition: F1=F2=1,Fn=Fn−1+Fn−2 for n>2.
OR
The other factor is of degree 15 and we write (with slight malice aforethought)
(−1−x+x2)(−c0+c1x−…+c15x15)=1+bx16+ax17
Comparing coefficients:
x0:c0=1,x1:c0−c1=0⇒c1=1x2:−c0−c1+c2=0⇒c2=2
and for 3≤k≤15,
xk:−ck−2−ck−1+ck=0
It follows that for k≤15,ck=Fk+1, the (k+1)-st Fibonacci number.
Thus a=c15=F16=987.
The problems on this page are the property of the MAA's American Mathematics Competitions