Contenu
Some arithmetical properties of Linear
recurring sequences in a finite field
Oumar FALL 1), Sémou DIOUF2), Chérif Bachir DEME3), and Oumar DIANKHA 4)
1), 2), 4) Département de Mathématiques et Informatique,
Faculté des Sciences et Technologies de l’Education et de la Formation,
Université Cheikh Anta Diop de Dakar, Sénégal
3) Université Alioune Diop de Bambey, Sénégal
Mathematics Subject Classification: (2010) 11B37, 11B50
Key words: Linear recurring sequences, period, lowest common multiple,
Legendre’s symbol, companion polynomial, law of quadratic reciprocity
Abstract:
M. Mignotte cited, in [CMP 87], the following result: let (un) be a binary linear recurring sequence whose values are integers and Q = X2 - a1X - a0 its companion polynomial. If p is a prime integer not dividing a0, then (un) is purely periodic modulo p. Let Tp denote this period. We note D(Q) the discriminant of Q:
∙ if p divides D(Q), then Tp divides p(p - 1),
∙ if = +1, where (⋅∕p) designates the symbol of Legendre, then Tp
divides p - 1,
∙ if = -1, then Tp divides p2 - 1.
This study was developed in [FDMS 11] and [FDMS 12] for cubic recurrences.
In this paper, we pursue this study for fourth-order and fifth-order recurrences, next we proceed to h-order recurrences for (h ≥ 2).
We propose a determination of the period Tp of a linear recurring sequence modulo p, with p a prime integer, using the arithmetical method. This method is based on law of reciprocity quadratic, Legendre’s symbol and polynomials.