Vol. 3, No. 2, 2010

Download this article
Download this article For screen
For printing
Recent Issues

Volume 12
Issue 6, 901–1080
Issue 5, 721–899
Issue 4, 541–720
Issue 3, 361–539
Issue 2, 181–360
Issue 1, 1–180

Volume 11, 5 issues

Volume 10, 5 issues

Volume 9, 5 issues

Volume 8, 5 issues

Volume 7, 6 issues

Volume 6, 4 issues

Volume 5, 4 issues

Volume 4, 4 issues

Volume 3, 4 issues

Volume 2, 5 issues

Volume 1, 2 issues

The Journal
About the Journal
Editorial Board
Editors’ Interests
Scientific Advantages
Submission Guidelines
Submission Form
Ethics Statement
Editorial Login
Author Index
Coming Soon
ISSN: 1944-4184 (e-only)
ISSN: 1944-4176 (print)
Other MSP Journals
Recursive sequences and polynomial congruences

J. Larry Lehman and Christopher Triola

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

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 ω = x + f as a unit in the quotient ring m[ω] = m[x]f. When m = p is prime, this order can be described in terms of the factorization of f in the polynomial ring p[x]. We use this connection to develop efficient algorithms for determining the factorization types of monic polynomials of degree k 5 in p[x].

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

Communicated by Kenneth S. Berenhaut
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