Congruence properties of linear recurring sequences

This thesis deals with the behaviour modulo n of linear recurring sequences of integers with characteristic polynomial ƒ ( x ) where n is a positive integer and ƒ ( x ) is a monic polynomial of degree k. Let α [subscript 1], α [subscript 2],...,α [subscript k] be the zeros of ƒ ( x ) and D ( ƒ ) ≠ 0 its discriminant. We focus on the v-sequence ( v [subscript j] ), defined by v [subscript j] = α[superscript j] over [subscript 1] + α [superscript j] over [subscript 2] + ... + α [superscript j] over [subscript k] for j ≥ 0. Our main interest is in algebraic congruences modulo n which hold when n is a prime and which involve only terms of the sequence and rational integers. For k = 1,2 such results have been used extensively in primality testing and have led to the study of various types of pseudoprimes. For k = 3, such results have been studied by Adams and Shanks ( 1 ) under the further assumption ƒ ( 0 ) = - 1. For general k, quite different approaches have been taken by Gurak ( 2 ) and Szekeres ( 3 ). The infinite test matrix modulo n is the infinite matrix M with rows and columns numbered 0,1,2 ... whose ( i, j ) entry is m [subscript ij], the least residue modulo n of v [subscript in + j] - v [subscript i + j] for i ≥ 0 and j ≥ 0. We study the congruence properties of M and especially of the k x k submatrix M ( [superscript k] ) determined by rows and columns 0 to k - 1. Chapters 1 and 2 introduce the thesis and summarise auxiliary results. Chapter 3 presents background on linear recurring sequences with an emphasis on the matrix approach, including the v - sequence and the k " u - sequences " ( whose initial vectors are the rows of Ik ). Chapter 4 comprises theoretical study of the properties of M for a general k, both when n is a prime and for general n, together with investigation of the condition of Gurak ( 2 ). For ( n, k!D ( ƒ ) ) = 1, we show that the condition of Szekeres is equivalent to the condition that m [subscript i0] = 0 for 1 ≤ i ≤ k and also to certain permutation conditions. Gurak ' s condition is then described using these conditions. Chapter 5 assumes k = 3. For this case we study congruences modulo n satisfied by the m [subscript ij] when n is a prime, and hence develop a combination of tests on M ( [superscript 3] ) which are passed by all primes. We report on extensive computer investigation of composites passing these tests. Such composites are found to be rare. Investigation of the relevant work of Adams and Shanks and colleagues, together with use of the permutation condition of Chapter 4, leads to a modification of the earlier tests on M ( [superscript 3] ). Under suitable assumptions we show that the new modified condition is equivalent to the basic condition of Adams and Shanks and also to that of Gurak but has significant advantages over both. References ( 1 ) Adams, W. and Shanks, D. Strong primality tests that are not sufficient, Math. Comp., 39, 1982, 255-300. ( 2 ) Gurak, S. Pseudoprimes for higher - order linear recurrence sequences, Math. Comp., 55, 1990, 783-813. ( 3 ) Szekeres, G., Higher order pseudoprimes in primality testing, pp 451-458, in Combinatorics, Paul Erdos is eighty, Vol. 2 ( Jesztgektm 1993 ), Bolyai Soc. Math. Stud., 2, Jnos Bolyai Math. Soc. Budapest, 1996.Thesis (M.Sc.)--School of Mathematical Sciences, 2006