Annales Mathématiques Africaines

Some arithmetical properties of Linear
recurring sequences in a finite field

Oumar FALL ¹⁾, Sémou DIOUF²⁾, Chérif Bachir DEME³⁾, and Oumar DIANKHA ⁴⁾
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 (u_n) be a binary linear recurring sequence whose values are integers and Q = X² - a₁X - a₀ its companion polynomial. If p is a prime integer not dividing a₀, then (u_n) is purely periodic modulo p. Let T_p denote this period. We note D(Q) the discriminant of Q:

∙ if p divides D(Q), then T_p divides p(p - 1),

∙ if = +1, where (⋅∕p) designates the symbol of Legendre, then T_p divides p - 1,

∙ if = -1, then T_p divides p² - 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 T_p 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.