Vol. 3, No. 2, 2010

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

Volume 11
Issue 5, 721–900
Issue 4, 541–720
Issue 3, 361–540
Issue 2, 181–359
Issue 1, 1–179

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’ Addresses
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)
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