Annales Mathématiques Africaines


Aller au contenu

abstract_art7

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 (    )
 D(Qp) = +1, where (∕p) designates the symbol of Legendre, then Tp divides p - 1,

 if (D(Q))
   p = -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.

Accueil | Comité de Rédaction | A propos du journal | Abonnement | Contenu | Plan du site


Revenir au contenu | Revenir au menu