Exercice (oral Centrale/Supélec)
On considère la suite de Fibonacci, définie par : {\begin{cases}F_0=0\\F_1=1\end{cases}\;\text{et}\;:\forall\, n \in \mathbb{N},\; F_{n+2}=F_{n+1}+F_n}
Question 1
Soit {m} un entier supérieur ou égal à {2}.
Que dire de l’ensemble des valeurs prises dans {(\mathbb{Z}/m\mathbb{Z})^2} par les couples {(F_n,F_{n+1})} modulo {m} ?
En déduire la « périodicité modulo {m} » : {\exists\, T\in \mathbb{N}^*,\;\forall n \in \mathbb{N}, \, F_{n+T}=F_n \, [m]} |
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez :
Pour poursuivre votre exploration, vous pouvez :
Question 2.a
Résoudre l’équation {x^2=x+1} dans {\mathbb{Z}/41\mathbb{Z}}.
|
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez :
Pour poursuivre votre exploration, vous pouvez :
Question 2.b
En déduire une expression de {F_n} modulo {41}.
|
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez :
Pour poursuivre votre exploration, vous pouvez :
Question 2.c
Quelle est la période de {(F_n)} modulo {41} ?
|
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez :
Pour poursuivre votre exploration, vous pouvez :
Soit {p} un nombre premier impair.
Question 3
Montrer qu’il existe {u\in\mathbb{Z}} tel que, pour tout {x\in\mathbb{Z}}: {(x^2=x\!+\!1 \; [p] \Leftrightarrow (x\!-\!u)^2=u^2\!+\!1 \; [p])} |
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez :
Pour poursuivre votre exploration, vous pouvez :
Question
En déduire l’équivalence des propositions :
-
il existe {x} dans {\mathbb{Z}} tel que {x^2=x+1 \; [p]};
-
l’entier {5} est un carré modulo {p} (c’est-à-dire il existe {y} dans {\mathbb{Z}} tel que {5=y^2
\; [p]}).
|
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez :
Pour poursuivre votre exploration, vous pouvez :