Period Patterns of Certain Second-Order Linear Recurrences Modulo a Prime

Throughout this paper, p will denote a fixed prime. Let a and b be integers and let the Lucas sequence u(a, b) denote the second-order linear recurrence satisfying 1 $$ {u_{n + 2}} = a{u_{n + 1}} + b{u_n} $$ with initial terms u 0 = 0, u 1 = 1. Let μ(a, b) denote the period of u(a, b) modulo p. It is known (see [2, pages 344-345]) that if b ≢ 0 (mod p), then u(a, b) is purely periodic modulo p. If b ≢ 0 (mod p), define ord(b) to be the exponent of b modulo p. It was shown by Somer in [5, Theorem 11] and [6, Theorem 4.5.1] that if ord(— b) = ord(— b'), then the set of periods modulo p appearing among the Lucas sequences u(a, b) is the same as the set of periods modulo p appearing among the Lucas sequences u(a', b'), where both a and a' vary over all the residues modulo p. However, it was not shown in [5] and [6] that the number of recurrences u(a, b) modulo p having a given period equals the number of recurrences u(a', b') modulo p having that same period. This will be shown in Theorem 1 by means of a period-preserving map between the recurrences modulo p.