Fibonacci et périodicité

moiccasey
moiccasey
dans Algèbre
Bonjour à tous
j'ai quelques questions sur la suite de Fibonacci
J'ai fait une recherche avant et n'ai pas trouvé les réponses, je m'excuse d'avance si jamais ces questions ont déjà été posées
Je vous mets seulement les questions auxquelles je n'ai pas su répondre

1))m entier naturel Montrer que (Fn) est périodique modulo m, de période P(m) <m2-1

2))montrer que pour tout m entier naturel, les assertions suivantes sont équivalentes:
1. P(m) divise n
2. m divise pgcd (Fn, Fn+1-1)

3)) Montrer que: pgcd (Fn, Fn+1-1) = Fn/2si n congru à 0 (4)
Ln/2 si n congru à 2 (4)
2 si n congru à 3 (6)
1 sinon

4)) montrer P(m) pair

5)) montrer que P(L2n+1)=4n+2 et P(F2n)=4n

6)) montrer que P(m)> 2/ (log (1+5)-log (2)). log m et montrer que P(m) converge

7))q premier montrer que si q congru à + ou - 1 (10) , P(q) divise q-1

8))Montrer que si q congru à + ou - 3 (10) alors Fn+q+1 congru à -Fn (q)
Montrer que P(q) divise 2q+2 et que( 2q+2 )/ P(q) est impair

9)) Montrer que Fn congru à -n 3n+1 (5) En déduire P(5)


Je sais que ça fait beaucoup de questions et je serai ravie de toute l'aide que vous pourriez m'apporter
Vraiment ravie parce que je me noie


Je vous remercie
Cordialement
Casey S.

pS: désolée mais je ne sais pas écrire en latex

Réponses

  • skilveg
    skilveg
    Bonjour,
    Pour la première question, je pense qu'on peut utiliser le fait que (la classe de)~$\binom{0\ 1}{1\ 1}$ habite~$\mathrm{GL}_{2}(\Z/m\Z)$, dont on peut majorer le cardinal.

    Par ailleurs, c'est bien gentil de recopier toutes les questions auxquelles tu n'as pas su répondre, mais je crois que tu n'as pas défini~$L$.
  • Richard André-Jeannin
    Richard André-Jeannin
    Voici une preuve de 1) plus élémentaire que celle de Skilveg.

    On considère les couples (F(n), F(n+1)) (mod m). Il y a m valeurs possibles pour chaque terme, soit m2 couples possibles. Le couple (0, 0) est toutefois impossible, car:
    F(n)=F(n+1)=0 (mod m) entraîne F(n-1)=F(n+1)-F(n)=0 (mod m). En descendant, on arrive à F(1)=0 (mod m), ce qui contredit F(1)=1.
    Il y a donc m2-1 couples possibles.

    Pour 0<=n<=m2-1, on a m2 couples, donc deux d'entre eux sont égaux (Dirichlet):
    (F(r), F(r+1))= (F(s), F(s+1)), avec 0<=r<s<=m2-1
    On a: F(r-1)=F(r+1)-F(r)=F(s+1)-F(s)=F(s-1). En descendant, on arrive à:
    F(0)=F(s-r) et F(1)=F(s-r+1). La période est donc s-r<=m2-1.

    Remarquons qu'on peut avoir période = m2-1 (par exemple pour m=2 ou m=3).
    La même démonstration est valable pour la suite de Lucas L(n), car L(1)=1
  • skilveg
    skilveg
    Bien vue RAJ, l'application du principe des tiroirs... :)
  • bs
    bs
    Bonjour,

    Quels sont les deux premiers termes de tes suites de Fibonacci et de Lucas ?

    Sinon, quelques éléments de réponse here.

    Pour info: les nombres de Pisano (= période P(m) des (Fn) modulo m) sont ici: http://oeis.org/A001175

    Amicalement.
  • JLT
    JLT
    Pour que ce soit cohérent avec la 2e question, on a besoin de $F_0=0$ et $F_1=1$. En effet, $P(m)$ divise $n$ ssi $F_0\equiv F_n\,[m]$ et $F_1\equiv F_{n+1}\,[m]$, ce qui équivaut à ce que $m$ divise à la fois $F_n-F_0=F_n$ et $F_{n+1}-F_1=F_{n+1}-1$.
  • JLT
    JLT
    Sinon, on a $L_0=2$ et $L_1=1$.

    Pour la 3), on utilise $a\wedge b=b\wedge (a-b)$. En appliquant ceci $k$ fois, on trouve que $(F_{n+1}-1)\wedge F_n = (F_{n-k}+(-1)^kF_k)\wedge (F_{n-k-1}+(-1)^{k+1}F_{k+1})$.

    a) Si $n$ est divisible par 4, on prend $k=n/2$ et on obtient $(2F_{n/2})\wedge F_{n/2}=F_{n/2}$.

    b) Si $n$ est congru à 2 modulo 4, on obtient $0\wedge (F_{n/2-1}+F_{n/2+1})=L_{n/2}$.

    c) Si $n$ est impair, $n=2p+1$, on prend $k=p$ et on obtient $(F_{p+1}+(-1)^pF_p)\wedge (F_p+(-1)^{p+1}F_{p+1})$. Or, $a\wedge b=a\wedge (b+(-1)^pa)$, donc on obtient $(F_{p+1}+(-1)^pF_p)\wedge 2F_p$. Si un facteur commun aux deux termes divise $F_p$, alors il divise aussi $F_{p+1}$, ce qui est impossible car $F_p$ et $F_{p+1}$ sont premiers entre eux (ceci se démontre par récurrence). Donc le pgcd est $F_{p+1}+(-1)^pF_p\wedge 2$, qui vaut $2$ si $F_p$ et $F_{p+1}$ ont la même parité et 1 sinon. Or, on observe que $F_p$ est 3-périodique modulo 2 donc le pgcd vaut 2 ssi $p\equiv 1\,[3]$, ce qui équivaut à $n\equiv 3\,[6]$.
  • JLT
    JLT
    Le 4) n'est pas vrai pour m=2 puisque P(2)=3. Par contre, si $m\ge 3$ alors $P(m)$ est pair. En effet, s'il était impair, soit $n=P(m)$. D'après les questions 2 et 3, $m$ divise 2. Impossible.
  • Richard André-Jeannin
    Richard André-Jeannin
    J'essaie la 4). Si m=2, on a P(2)=3 et le résultat est faux.
    En posant p = P(m), il est facile de voir que:
    F(p-1)=F(p+1)=1, mod m, et plus généralement que F(p-n)=(-1)n-1F(n) mod m
    Prenons n=p-1 pour obtenir:
    1=F(1)=(-1)pF(p-1)=(-1)p Si m différent de 2, la relation 1=(-1)p entraîne que p pair.
  • JLT
    JLT
    5) On veut montrer que $P(L_{2k+1})=4k+2$. Posons $m=L_{2k+1}$. On sait que $P(m)$ est pair.
    On a $L_{2k+1} | L_{(4k+2)/2}$ donc d'après les questions 2 et 3, $P(L_{2k+1})|4k+2$.

    Réciproquement, posons $n=P(m)$. Comme $n$ est pair, la question 3 montre que $m$ divise $L_{n/2}$ ou $F_{n/2}$ donc $L_{2k+1}\le L_{n/2}$, ce qui entraîne que $2k+1\le n/2$, d'où $4k+2\le P(m)$. On en conclut que $P(m)=4k+2$.

    Montrons que $P(F_{2k})=4k$ pour $k\ge 2$. Posons $m=F_{2k}$ et $n=P(m)$. Une méthode analogue donne que $P(m)|4k$ et que $m$ divise $F_{n/2}$ ou $L_{n/2}$. Dans le premier cas, on a $2k\le n/2$ donc $P(m)=n\ge 4k$, d'où $P(m)=4k$.
    Dans le deuxième cas, on a $F_{2k}=m\le L_{n/2}<F_{n/2+2}$ donc $2k<(n/2)+2$, ce qui n'est possible que si $n\ge 4k-2$. Si on avait $n\ne 4k$, comme $n$ est pair on doit avoir $n=4k-2|4k$. Impossible.
  • JLT
    JLT
    La question 6 n'est pas claire mais si $n=P(m)$ alors on doit avoir $F_n\ge m$. Or, $F_n<\frac{\phi^n+1}{\sqrt{5}}$ ce qui permet aisément de minorer $P(m)$ et de montrer que $P(m)$ tend vers l'infini.
  • JLT
    JLT
    7) Revient à montrer que $F_{q-1}\equiv 0\,[q]$ et $F_q\equiv 1\,[q]$.

    Pour la deuxième, on a $F_q=2^{-(q-1)}\sum_{k\;\mathrm{impair}}\binom{q}{k}5^{\frac{k-1}{2}}\equiv 5^{(q-1)/2}$ (utiliser le petit théorème de Fermat et le fait que les coefficients binomiaux sont divisibles par $q$ sauf le dernier). Il faut donc montrer que $5$ est un résidu quadratique modulo $q$, ce qui provient aisément de la loi de réciprocité quadratique.

    Pour le premier, comme $F_{q-1}=F_{q+1}-F_q$ cela revient à regarder $F_{q+1}$ modulo $q$.
    $F_{q+1}=2^{-q}\sum_{k\;\mathrm{impair}}\binom{q+1}{k}5^{\frac{k-1}{2}}\equiv 1$ (utiliser $\binom{q+1}{k}=\binom{q}{k}+\binom{q}{k-1}$ et la méthode précédente).
  • JLT
    JLT
    9) La relation se montre par récurrence sur $n$.

    $P(5)$ est le plus petit entier non nul tel que $F_n$ soit divisible par $5$ et $F_{n+1}\equiv 1\,[5]$. Cela donne $5|n$ et $-(n+1)3^{n+2}\equiv 1\,[5]$. La dernière relation se simplifie en $3^n\equiv 1\,[5]$ donc $4|n$.

    Conclusion : $P(5)=20$.
  • JLT
    JLT
    8) On montre comme au 7) que $F_q\equiv -1$ et $F_{q+1}\equiv 0$, donc $F_{q+2}\equiv -1$. La première assertion se démontre alors par récurrence sur $n$. En l'appliquant 2 fois, on a $F_{n+2(q+1)}\equiv -F_{n+q+1}\equiv F_n$ donc $P(q)$ divise $2q+2$. Si le quotient était un nombre pair $2r$, alors on aurait $F_n\equiv F_{n+rP(q)}=F_{n+q+1}\equiv -F_n$. Contradiction.
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 9

TOTO25 +8 Invités