Fibo dans $\Bbb{F}_{p}$

Amédé
Amédé
Modifié (April 2022) dans Arithmétique
Bonsoir,
j'ai lancé dans mon python le calcul des 1000 premiers termes de la suite de Fibonacci. Et je les ai réduit modulo 7. J'ai constaté qu'il y avait une période de longueur 16. Du coup j'ai essayé avec d'autre valeurs: 3,5,7,11,13,17 et 19. J'ai constaté le même phénomène. Est-ce qu'il existe un résultat général ?
Dans le sens pour tout nombre premier $p$ si on note $\overline{x}$ la classe de $x$ modulo $p$. Est-ce que $(\overline{\phi_{n}})_{n\in\N}$ est périodique ?

Réponses

  • Paco_del_Rey
    Paco_del_Rey
    Oui bien sûr. Si $\overline{\phi_{n+p}} = \overline{\phi_{n}}$ et $\overline{\phi_{n+p+1}} = \overline{\phi_{n+1}}$ pour un certain $n\in \N$ et $p\in\N^*$, alors la suite $(\overline{\phi_{n}})_{n\in\N}$ est $p$ périodique.
    Il suffit de penser au principe des tiroirs.

    Paco.
  • Benoit RIVET
    Benoit RIVET
    Une suite récurrente du type $u_{n+1} = f(u_{n})$ à valeurs dans un ensemble fini est périodique, what else ?
  • marco
    marco
    Modifié (April 2022)
    Oui, en effet $\mathbb{F}_p^2$ est un ensemble fini. Soit $f: \mathbb{F}_p ^2 \rightarrow \mathbb{F}_p^2$ qui à $(x,y) $ associe $(y,x+y)$. Alors $f( \overline{\phi_n}, \overline{\phi_{n+1}})=(\overline{\phi_{n+1}},\overline{ \phi_{n+2}})$, et $f$ est bijective.
    Si on note $e=(\overline{0},\overline{1})$, alors la fonction $k\in \N \mapsto f^k(e)$ n'est pas injective, donc, il existe $k\in \N$, $r \in \N^*$ tels que $f^k(e)=f^{k+r}(e)$, donc $f^k(e)=f^{k+nr}(e)$, donc $\overline{\phi_k}=\overline{\phi_{k+nr}}$.
    De même en composant par $f^{-1}$, $f^k(e)=f^{k-nr}(e)$, donc $\overline{\phi_k}=\overline{\phi_{k-nr}}$.
    Donc $\overline{\phi_n}$ est périodique de période un diviseur de $r$.

  • JLapin
    JLapin
    Modifié (April 2022)
    C'est une histoire d'ordre de la matrice $A=\begin{pmatrix} 0&1\\1&1\end{pmatrix}$ dans $\mathrm{GL}_2(F_p)$.
    Par exemple, $A^{16}=I_2$ modulo $7$.

    Comme c'est une matrice du groupe fini $\mathrm{GL}_2(F_p)$, de cardinal $(p^2-1)(p^2-p)$, elle est d'ordre fini qui divise $(p^2-1)(p^2-p)$.
    Par exemple, $16$ divise $48*42$.
  • JLapin
    JLapin
    Benoit RIVET a dit :
    Une suite récurrente du type $u_{n+1} = f(u_{n})$ à valeurs dans un ensemble fini est périodique, what else ?

    Périodique à partir d'un certain rang seulement  :)
  • Amédé
    Amédé
    Modifié (April 2022)
    Ok merci à tous.
    Effectivement j'étais en train de lire ce papier: https://www.di.ens.fr/users/phan/PIR2016_Rapports/CROS_DUPEUX_MILON.pdf
    C'est intéressant.
    @JLapin : tu voulais dire $A=\begin{pmatrix}1&1\\1&0\end{pmatrix}$ ? Peut importe mais tu préconises qu'on peut le voir dans l'ordre de la matrice qui sert à itérer la suite ?
  • Amédé
    Amédé
    Benoit RIVET a dit :
    Une suite récurrente du type $u_{n+1} = f(u_{n})$ à valeurs dans un ensemble fini est périodique, what else ?

    Autre phénomène à étudier si on donne les termes de la suite de manière aléatoire.
  • JLapin
    JLapin
    Modifié (April 2022)
    Amédé a dit :
    @JLapin: tu voulais dire $A=\begin{pmatrix}1&1\\1&0\end{pmatrix}$? Peut importe mais tu préconises qu'on peut le voir dans l'ordre de la matrice qui sert à itérer la suite ?
    J'ai posé $A$ pour que le vecteur $\begin{pmatrix} u_n\\u_{n+1}\end{pmatrix}$ s'écrive $A^n \begin{pmatrix} u_0\\ u_1\end{pmatrix}$.
    Ensuite, dès que $A^k =I_2$, on a $u_k=u_0$ et $u_{k+1}=u_1$, ce qui montre la $k$-périodicité.
  • Amédé
    Amédé
    Modifié (April 2022)
    Ok merci.
  • Paco_del_Rey
    Paco_del_Rey
    Modifié (April 2022)
    Une idée (qui marche) est de chercher les suites récurrentes \( u_n \) dans \( F_p \), qui vérifient \( u_{n+2} = u_{n+1} + u_n \) pour tout entier \( n \).
    Mots-clés : suites géométriques, espace vectoriel de solutions, résidus quadratiques.
    Paco.
  • jmf
    jmf
    @Amédé

    ci-joint un sujet d'oral de Centrale Mp1 (en 2016)


  • Math Coss
    Math Coss
    Modifié (April 2022)
    Une autre façon de voir : comme dans la situation habituelle sur $\R$ ou $\C$, une suite solution est combinaison linéaire de suites géométriques $(\lambda^n)_{n\in\N}$ ou, parfois, de suites $(n^k\lambda^n)_{n\in\N}$ (il faut éventuellement passer dans une extension de $\mathbf{F}_p$ pour trouver les $\lambda$). Ces suites sont périodiques (pourquoi au fait ?).
  • Paul Broussous
    Paul Broussous
    C'est une belle application de la théorie des corps finis et de la loi de réciprocité quadratique !
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 10

JLapinLee sinLirone93biguine_equation +6 Invités