Exercice corrigé Ancien programme

factorisation des nombres de mersenne

Cet exercice prolonge l'étude des nombres de Mersenne qui a été faite dans

l'exercice 31. On rappelle que les nombres de Mersenne sont de la forme avec p un nombre premier impair.

Soit q un facteur premier de MP 1. Quelle est la parité de q ?

2. Démontrer que p est l'ordre de 2 modulo q (c'est-à-dire que p est le plus petit entier supérieur à 1 tel que (modulo q)).

3. Démontrer que p divise

4. On écrit alors avec démontrer que m est pair et en déduire que (modulo 2 p).

5. Application : les nombres M17, M19 et M23 sont-ils premiers ?

1. étant impair, q est forcément impair.

2. Appelons h l'ordre de 2 modulo q.

q divise , donc(modulo q), c'est-à-dire (modulo q).

On en déduit que h divise p, mais p étant premier, .

3. Puisque q est premier impair et que 2 n'est pas divisible par q alors, d'après

le petit théorème de Fermat (modulo q).

De plus p est l'ordre de 2 modulo q, donc p divise.

4. q est impair donc est pair, puisque p est impair et que , alors m est nécessairement pair et il existe tel quedonc.

5. Montrons que est premier. à 1 unité près et si n'est pas premier, il admet un diviseur premier inférieur à . Or d'après la question 4., les facteurs premiers éventuels q de sont congrus à 1 modulo 34. On dresse le tableau suivant :

K

1

2

3

4

5

6

7

8

9

10

1 + 34 k

35

69

103

137

171

205

239

273

307

341

On vérifie que seuls les entiers 103, 137, 239, 307 sont premiers mais qu'ils

ne divisent pas . est donc premier.

De même, on démontre que est premier.

et à 1 unité près.

On vérifie que divise , qui n'est donc pas premier.

Accéder à tous les contenus
dès 6,79€/mois

  • Les dernières annales corrigées et expliquées
  • Des fiches de cours et cours vidéo/audio
  • Des conseils et méthodes pour réussir ses examens
  • Pas de publicités
S'abonner