Vol. 3, No. 2, 2010

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

Volume 11, 1 issue

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
Subscriptions
Editorial Board
Editors’ Addresses
Editors’ Interests
Scientific Advantages
Submission Guidelines
Submission Form
Ethics Statement
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 ω = 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].

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