Recursive sequences and polynomial congruences

Lehman, J.; Triola, Christopher

doi:10.2140/involve.2010.3.129

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the journal

Ethics and policies

Peer-review process

Submission guidelines

ISSN 1944-4184 (online)

ISSN 1944-4176 (print)

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

DOI: 10.2140/involve.2010.3.129

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 \leq 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

Vol. 3, No. 2, 2010