Fibonacci et les premiers

Olympiades mathématiques, énigmes et défis
nodgim
Habitué(e)
Messages: 2002
Enregistré le: 27 Jan 2008, 12:21

Fibonacci et les premiers

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 ?

 

Retourner vers ⚔ Défis et énigmes

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 22 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite