Activité : de Mersenne à Lucas-Lehmer

[vanyle]

Les nombres de la forme 2^n-1 pour n entier naturel s'appellent les nombres de Mersenne.
Leurs diviseurs possèdent des propriétés particulières et il existe un test de primalité spécifique à ces nombres, ce qui explique l'intérêt qu'on leur porte dans la recherche des nombres premiers.
On posera dans la suite Mn = 2^-1 (n entier naturel).

A. Exploration.
1. Pour 0 <= n < 20, déterminer si Mn est premier ou composé. Qu'observe-t-on quand n est composé? Quand n est premier?
2. Vérifier que, pour tout entier naturel n non nul, a^n-1 = (a-1)(a^(n-1)+a^(n-2)+...+1)
En déduire que : (n composé) implique (Mn composé)
3. On suppose que Mn admet un diviseur premier d. Justifier que 2^n est congru à 1 modulo d.

B. Etude du cas où p est premier
On considère un entier p premier tel que Mp = 2^p-1 admette un diviseur premier d. Soit I l'ensemble des entiers naturels n non nuls tels que 2^n est congru à 1 modulo d.

1. Justifier que I n'est pas vide puis qu'il admet un plus petit élément p0 et que p0 > 1
2. En écrivant la division euclidienne de n par p0, montrer que tout élément de I est multiple de p0.
En déduire que p=p0.
3. On admet que 2d-1 est congru à 1 modulo d.
Déduire comme en 2. que p0 divise d-1 puis qu'il existe k (entier naturel) tel que d = 2kp+1.


J'ai réussi quelques questions :
A.
1.Quand n est composé, Mn est composé
Quand n est premier, Mn n'est pas forcément premier
2.J'ai démontré l'égalité en développant le membre de droite pour arriver au membre de gauche.
Je n'arrive pas à en déduire que (n composé) implique (Mn composé)
3. Mn est congru à 0 modulo d donc 2^n-1 est congru à 0 modulo d
Donc 2^n est congru à 1 modulo d d'après les opérations possibles sur les congruences.

B. Je n'arrive pas à répondre à toutes les questions

Merci d'avance de votre aide !

[Manny06]

[quote="vanyle"]Les nombres de la forme 2^n-1 pour n entier naturel s'appellent les nombres de Mersenne.
Leurs diviseurs possèdent des propriétés particulières et il existe un test de primalité spécifique à ces nombres, ce qui explique l'intérêt qu'on leur porte dans la recherche des nombres premiers.
On posera dans la suite Mn = 2^-1 (n entier naturel).

A. Exploration.
1. Pour 0 <= n < 20, déterminer si Mn est premier ou composé. Qu'observe-t-on quand n est composé? Quand n est premier?
2. Vérifier que, pour tout entier naturel n non nul, a^n-1 = (a-1)(a^(n-1)+a^(n-2)+...+1)
En déduire que : (n composé) implique (Mn composé)
3. On suppose que Mn admet un diviseur premier d. Justifier que 2^n est congru à 1 modulo d.

B. Etude du cas où p est premier
On considère un entier p premier tel que Mp = 2^p-1 admette un diviseur premier d. Soit I l'ensemble des entiers naturels n non nuls tels que 2^n est congru à 1 modulo d.

1. Justifier que I n'est pas vide puis qu'il admet un plus petit élément p0 et que p0 > 1
2. En écrivant la division euclidienne de n par p0, montrer que tout élément de I est multiple de p0.
En déduire que p=p0.
3. On admet que 2d-1 est congru à 1 modulo d.
Déduire comme en 2. que p0 divise d-1 puis qu'il existe k (entier naturel) tel que d = 2kp+1.


J'ai réussi quelques questions :
A.
1.Quand n est composé, Mn est composé
Quand n est premier, Mn n'est pas forcément premier
2.J'ai démontré l'égalité en développant le membre de droite pour arriver au membre de gauche.
Je n'arrive pas à en déduire que (n composé) implique (Mn composé)
3. Mn est congru à 0 modulo d donc 2^n-1 est congru à 0 modulo d
Donc 2^n est congru à 1 modulo d d'après les opérations possibles sur les congruences.

B. Je n'arrive pas à répondre à toutes les questions

Merci
si n=pq
2^n=2^pq=(2^p)^q donc 2^n -1 est divisible par 2^p - 1