Second Order Polynomial Recursions
S. W. Golomb, Abraham Lempel · SIAM Journal on Applied Mathematics · 1977
Divisibility properties of sequences of polynomials $\{ f_n (x)\} $ which satisfy a second order recursion of the form \[ f_{n + 1} (x) = a(x)f_n (x) + b(x)f_{n - 1} (x) \] are considered, with special emphasis on the sequence $\{ q_n (x)\} $ obtained when $a(x) = 1,b(x) = x$, and starting with $q_0 = 0,q_1 = 1$. It is shown that for $n > 2,q_n (x)$ is irreducible over the rationals if and only if n is prime. The further factorization of $q_n (x)$ over $GF(2)$ is characterized. In particular, $q_n (x)$ is irreducible over $GF(2)$ iff p is an odd prime such that $\alpha (p) = {{(p - 1)} / 2 }$, where $\alpha (k)$ is the least positive integer s such that $k| (4^s - 1) $.