Vol. 3, No. 2, 2010

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

Volume 17
Issue 2, 183–362
Issue 1, 1–182

Volume 16, 5 issues

Volume 15, 5 issues

Volume 14, 5 issues

Volume 13, 5 issues

Volume 12, 8 issues

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
Ethics and policies
Peer-review process
Submission guidelines
Submission form
Editorial board
Editors' interests
ISSN (electronic): 1944-4184
ISSN (print): 1944-4176
Author index
To appear
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