La suite de Fibonacci est-elle surjective modulo $p$ ?

john_john

Si $K$ est un corps fini, la suite définie par $u_0=0, u_1=1$ et $u_{n+2}=u_{n+1}+u_n$ prend-elle toutes les valeurs dans $K$ ? Je ne sais répondre que très partiellement ; voici à quel stade j'en suis, tout en espérant vos lumières : 

Il est nécessaire que le cardinal de $K$ soit premier puisque la suite prend ses valeurs dans le sous-corps premier de $K$. Supposons cela vérifié.

L'équation caractéristique $r^2=r+1$ a une racine double lorsque $p=5$ ; on regarde directement ce cas et l'on constate que la suite prend les cinq valeurs possibles.

Lorsque $5$ est un carré, càd ssi $p=5q\pm1$, l'équation a deux solutions $a\neq b$ dans $K$ et $u_n=\displaystyle\frac{a^n-b^n}{a-b}$ pour tout $n$. La suite n'est donc pas surjective puisqu'une période de celle-ci est l'ordre de $a$ (et de $b$) dans le groupe $K^\times$, d'ordre $<p$.

En revanche, lorsque les solutions se trouvent dans une extension quadratique de $K$, la période n'est a priori majorée que par $p^2-1$. Pour $p=13$, la période est $28$ mais les classes de $4,6,7,9,$ ne sont pas obtenues. À noter que $u_7=0, u_8=8$ et donc que $u_{n+7}=8u_n$ pour tout $n$.

jandri

Avec un petit programme je trouve que les seuls nombres premiers p inférieurs à 1000 pour lesquels la suite de Fibonacci est surjective modulo p sont 2, 3, 5 et 7.

john_john

Merci, Jandri ! Cela suggère donc ce qu'il va falloir établir.

JLapin

On parle de ce sujet en anglais ici ou là.
https://oeis.org/A079002
https://mathoverflow.net/questions/389663/fibonacci-with-seeds-modulo-n

john_john

Merci, JLapin ! Et pour ceux que cela intéresse, l'OEIS renvoie à https://www.fq.math.ca/Scanned/9-5/burr.pdf, article dans lequel la démonstration est détaillée.

Cet article n'est pas auto-contenu ; il renvoie à https://www.fq.math.ca/Scanned/6-2/shah.pdf