Fibonacci et les premiers
Olympiades mathématiques, énigmes et défis
-
nodgim
- Habitué(e)
- Messages: 2002
- Enregistré le: 27 Jan 2008, 12:21
-
par nodgim » 11 Oct 2009, 16:13
Bonjour à tous.
Soit N un entier naturel et Fk, le Kième nombre de Fibonacci.
Montrer que si Fk= 0 modulo N, avec F(k-1)=p modulo N, alors p est premier avec N.
Bonne recherche.
-
yos
- Membre Transcendant
- Messages: 4858
- Enregistré le: 10 Nov 2005, 22:20
-
par yos » 13 Oct 2009, 21:20
donc un diviseur commun d de p et de N divise
. Par ailleurs
.
Enfin, il est bien connu que
et
sont premiers entre eux.
-
nodgim
- Habitué(e)
- Messages: 2002
- Enregistré le: 27 Jan 2008, 12:21
-
par nodgim » 14 Oct 2009, 18:21
yos a écrit:Enfin, il est bien connu que
et
sont premiers entre eux.
Allez, réécrire la preuve que 2 Fibo successifs sont premiers entre eux...
-
yos
- Membre Transcendant
- Messages: 4858
- Enregistré le: 10 Nov 2005, 22:20
-
par yos » 14 Oct 2009, 19:00
c'est l'algorithme d'Euclide :
.
C'est l'occasion de rappeler que c'est avec deux termes consécutifs de la suite de Fibonacci que l'algorithme d'Euclide demande le plus d'étapes (à taille de nombres donnée bien sûr) : c'est assez compréhensible car les quotients des divisions successives valent tous 1.
-
nodgim
- Habitué(e)
- Messages: 2002
- Enregistré le: 27 Jan 2008, 12:21
-
par nodgim » 16 Oct 2009, 17:08
Bon d'accord.
Un peu plus difficile maintenant:
Montrer que pour p premier >5, Fp est congru à +1 ou -1 modulo p.
-
yos
- Membre Transcendant
- Messages: 4858
- Enregistré le: 10 Nov 2005, 22:20
-
par yos » 17 Oct 2009, 09:38
Il y a sûrement des simplifications à apporter à ce qui suit, mais ça a l'air de marcher :
Dans l'égalité
, on développe les parenthèses avec la formule du binôme pour obtenir :
si n est impair,
.
Si p est premier, il ne reste que le dernier terme du second membre (car
pour 05, le théorème de Fermat permet de conclure :
.
-
nodgim
- Habitué(e)
- Messages: 2002
- Enregistré le: 27 Jan 2008, 12:21
-
par nodgim » 17 Oct 2009, 10:20
C'est bon pour moi.
Est ce un bon test de primalité ?
-
yos
- Membre Transcendant
- Messages: 4858
- Enregistré le: 10 Nov 2005, 22:20
-
par yos » 18 Oct 2009, 14:06
Je ne sais pas, je n'y connais rien.
Si n est grand, f_n est terriblement grand, donc ça nécessite le calcul de f_n modulo n sans passer par le calcul de f_n.
D'autre part, un entier qui passe le test est-il premier?
-
nodgim
- Habitué(e)
- Messages: 2002
- Enregistré le: 27 Jan 2008, 12:21
-
par nodgim » 18 Oct 2009, 16:15
C'est là la grande question.
-
yos
- Membre Transcendant
- Messages: 4858
- Enregistré le: 10 Nov 2005, 22:20
-
par yos » 18 Oct 2009, 16:42
A priori c'est non car
.
D'où la question : quels sont les entiers n tels que
?
-
nodgim
- Habitué(e)
- Messages: 2002
- Enregistré le: 27 Jan 2008, 12:21
-
par nodgim » 18 Oct 2009, 18:41
yos a écrit:A priori c'est non car
.
D'où la question : quels sont les entiers n tels que
?
Je n'ai pas été assez précis. Le triplet (F(p-1);Fp;F(p+1)) prend, modulo p, quand p premier, l'une des 4 valeurs suivantes: (0;1;1)(0;-1;-1)(1;1;0)(-1;-1;0).
Et là, ça marche très bien.
Il est vrai que je n'ai pas demandé si F(p-1) ou F(p+1) est divisible par p.
Démonstration ?
-
yos
- Membre Transcendant
- Messages: 4858
- Enregistré le: 10 Nov 2005, 22:20
-
par yos » 18 Oct 2009, 20:56
.
Vu l'autre résultat on a
.
Ainsi, p divise
ou
.
Dans le premier cas, on a les triplets (0,1,1) ou (0,-1,-1).
Dans le second cas, les triplets (-1,1,0) ou (1,-1,0).
-
nodgim
- Habitué(e)
- Messages: 2002
- Enregistré le: 27 Jan 2008, 12:21
-
par nodgim » 19 Oct 2009, 06:42
yos a écrit:.
Vu l'autre résultat on a
.
Ainsi, p divise
ou
.
Dans le premier cas, on a les triplets (0,1,1) ou (0,-1,-1).
Dans le second cas, les triplets (-1,1,0) ou (1,-1,0).
Merci pour la correction des signes.
Voilà, maintenant, si Fn avec n non premier, peut on obtenir l'un des 4 triplets ?
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 22 invités