Vol. 3, No. 2, 2010

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

Volume 10
Issue 5, 721–900
Issue 4, 541–720
Issue 3, 361–539
Issue 2, 181–360
Issue 1, 1–180

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
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 ω = 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