University of Illinois Urbana-Champaign

The Divisibility and Modular Properties of Kth-Order Linear Recurrences Over The Ring of Integers of an Algebraic Number Field With Respect to Prime Ideals

Somer, Lawrence Eric

This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.

Permalink

https://hdl.handle.net/2142/71235

Description

Title
The Divisibility and Modular Properties of Kth-Order Linear Recurrences Over The Ring of Integers of an Algebraic Number Field With Respect to Prime Ideals
Author(s)
Somer, Lawrence Eric
Issue Date
1985
Department of Study
Mathematics
Discipline
Mathematics
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Mathematics
Abstract
  • Let K be an algebraic number field and R its ring of integers. Let k (GREATERTHEQ) 2 and let (w) be a kth-order linear recurrence over R satisfying the recursion relation (1) w(,n+k) = a(,1)w(,n+k-1) + a(,2)w(,n+k-2) +...+ a(,k)w(,n). Those recurrences (u) satisfying (1) for which u(,0) = u(,1) =...= u(,k-2) = 0 and u(,k) = 1 are called unit sequences. Let f be the characteristic polynomial of the recurrence defined by (1). Let D be the discriminant of f. An ideal M is a maximal divisor of the kth-order recurrence (w) if the maximal number of successive terms of (w) it divides is k - 1.
  • It is shown that, in general, the linear recurrence w(,n) (,n=0)('(INFIN)) has almost all prime ideals as maximal divisors if and only if the recur- rence has k - 1 consecutive terms equal to 0 when considered as the doubly infinite sequence w(,n) (,n=-(INFIN))('(INFIN)). Modular properties of kth- order unit sequences are considered with respect to prime ideals P. Constraints on (mu)(P), the period modulo P, and (beta)(P), the exponent of the multiplier modulo P, are determined for a unit sequence given (alpha)(P), the restricted period modulo P, and the exponent of a(,k) modulo P. Additional constraints are given for the possible values of (mu)(P), (alpha)(P), and (beta)(P) for a unit sequence in cases in which f either splits completely or remains irreducible modulo P. These additional constraints are also shown to be necessary and sufficient.
  • Improved primality tests are developed for an odd integer N for the case in which the factorization of N - 1 or N + 1 is completely known. These tests are based on the proof of the existence of only a finite number of composite Fermat and Lucas d-pseudoprimes, where d is a positive integer such that 4 (VBAR) d. A Fermat d-pseudoprime is an odd integer N for which there exists an integer a whose exponent modulo N is (N - 1)/d. A Lucas d-pseudoprime is an odd integer N for which there exists a second-order unit sequence for which the rank of apparition of N is (n - (D/N))/d. All composite d-pseudoprimes are determined when d = 2, 3, 5, or 6. All composite Fermat 7-pseudoprimes are also found.
Graduation Semester
1985
Type of Resource
text
Permalink
http://hdl.handle.net/2142/71235

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois
Dissertations and Theses - Mathematics