1988 AIME Problem 13

Question

Find

a

if

a

and

b

are integers such that

x^2-x-1

is a factor of

ax^{17}+bx^{16}+1.

Answer

Modulo

x^2-x-1,

powers satisfy

x^n=F_nx+F_{n-1}

Set both coefficients of the linear remainder equal to zero and use Cassini’s identity

Modulo

x^2-x-1,

the relation

x^2=x+1

gives

x^n=F_nx+F_{n-1}.

Hence the remainder is

\begin{aligned}r(x)={}&(1597a+987b)x\\&+(987a+610b+1).\end{aligned}

Both coefficients must vanish. The determinant of the coefficient matrix is

1597(610)-987^2=1

by Cassini’s identity. Cramer’s rule then gives

a=987.

Problem 13 in other years