Vol. 3, No. 2, 2010

 Recent Issues
 The Journal Cover Page Editorial Board Editors’ Addresses Editors’ Interests About the Journal Scientific Advantages Submission Guidelines Submission Form Ethics Statement Subscriptions Editorial Login Author Index Coming Soon Contacts ISSN: 1944-4184 (e-only) ISSN: 1944-4176 (print)
Recursive sequences and polynomial congruences

J. Larry Lehman and Christopher Triola

Vol. 3 (2010), No. 2, 129–148
Abstract

We consider the periodicity of recursive sequences defined by linear homogeneous recurrence relations of arbitrary order, when they are reduced modulo a positive integer $m$. We show that the period of such a sequence with characteristic polynomial $f$ can be expressed in terms of the order of $\omega =x+〈f〉$ as a unit in the quotient ring ${ℤ}_{m}\left[\omega \right]={ℤ}_{m}\left[x\right]∕〈f〉$. When $m=p$ is prime, this order can be described in terms of the factorization of $f$ in the polynomial ring ${ℤ}_{p}\left[x\right]$. We use this connection to develop efficient algorithms for determining the factorization types of monic polynomials of degree $k\le 5$ in ${ℤ}_{p}\left[x\right]$.

Keywords
linear homogeneous recurrence relations, polynomial congruences, finite rings, finite fields
Mathematical Subject Classification 2000
Primary: 11B50, 11C08, 11T06
Milestones
Received: 29 October 2007
Accepted: 26 January 2010
Published: 11 August 2010

Communicated by Kenneth S. Berenhaut
Authors
 J. Larry Lehman University of Mary Washington Department of Mathematics 1301 College Avenue Fredericksburg, VA 22401 United States Christopher Triola 9 Seneca Terrace Fredericksburg, VA 22401 United States