Devoir de spécialité 11 ( TS1-4 pour le lundi 7 mai 2018)

Exercice 1 Les nombres de la forme 2n 1 où n est un entier naturel non nul sont appelés nombres de Mersenne.

1. On désigne par a, b et c trois entiers naturels non nuls tels que PGCD(b ; c) = 1.

Prouver, à l'aide du théorème de Gauss, que : si b divise a et c divise a alors le produit bc divise a.

2. On considère le nombre de Mersenne 233 1.

Un élève utilise sa calculatrice et obtient les résultats ci-contre.

Il affirme que 3 divise (233 1) et 4 divise (233 1) et 12 ne divise pas (233 1).

a. En quoi cette affirmation contredit-elle le résultat démontré à la question 1. ?

b. Justifier que, en réalité, 4 ne divise pas 233 1.

c. En remarquant que 2 1 (3), montrer que, en réalité, 3 ne divise pas 233 1.

d. Calculer la somme S = 1 23 + 232 + 233 + + 2310.

e. En déduire que 7 divise 233 1.

3. On considère le nombre de Mersenne 27 1. Est-il premier ? Justifier.

4. On donne l'algorithme suivant où MOD(N, k) représente le reste de la division euclidienne de N par k.

a. Qu'affiche cet algorithme si on saisit n 33 ? Et si on saisit n 7 ?

b. Que représente le CAS 2 pour le nombre de Mersenne étudié ?

Que représente alors le nombre k affiché pour le nombre de Mersenne étudié ?

c. Que représente le CAS 1 pour le nombre de Mersenne étudié ?

Exercice 2 p est premier et p 5.

1. Démontrer que p2 1 est divisible par 3.

2. Démontrer que p2 1 est divisible par 8.

3. En déduire que p2 1 est divisible par 24.

Exercice 3 Pour n 1, le nième nombre de Mersenne est le nombre Mn 2n 1.

1. Quels sont les nombres premiers parmi les nombres de Mersenne Mn pour n 6.

2. Montrer la factorisation standard (n 1) : xn 1 (x 1)(xn1 xn2 x 1)

3. Montrer que si n n’est pas premier alors le nombre de Mersenne Mn ne l’est pas non plus.

En déduire que si Mn est premier alors n est premier.

4. La réciproque est-elle vraie ?

5. Soit a et n deux entiers tels que a 2 et n 2.

Montrer que, si an 1 est premier, alors nécessairement a 2 et n est premier.

233 1÷3

2 863 311 530

233 1÷4

2 147 483 648

233 1÷12

715 827 882,6

Variables : n entier naturel supérieur ou égal à 3

k entier naturel supérieur ou égal à 2

Initialisation : Demander à l’utilisateur la valeur de n.

Affecter à k la valeur 2.

Traitement : Tant que MOD(2n 1, k) 0 et k 2n 1

Affecter à k la valeur k 1

Fin de Tant que.

Sortie : Afficher k.

Si k 2n 1

Afficher « CAS 1 »

Sinon

Afficher « CAS 2 »

Fin de Si

Exercice 4 : Partie A Le but de celle partie est de démontrer que l'ensemble des nombres premiers est infini en raisonnant par l'absurde.

1. On suppose qu'il existe un nombre fini de nombres premiers notés p1, p2, , pn.

On considère le nombre E produit de tous les nombres premiers augmenté de 1 : E p1 p2 pn 1.

Démontrer que E est un entier supérieur ou égal à 2, et que E est premier avec chacun des nombres p1, p2, , pn.

2. En utilisant le fait que E admet un diviseur premier conclure.

Partie B

Pour tout entier naturel k 2, on pose Mk 2k 1. On dit que Mk est le k-ième nombre de Mersenne.

1. a. Reproduire et compléter le tableau suivant, qui donne quelques valeurs de Mk :

k 2 3 4 5 6 7 8 9 10

Mk

b. D’après le tableau précédent, si k est un nombre premier, peut-on conjecturer que le nombre Mk est premier ?

2. Soient p et q deux entiers naturels non nuls.

a. Justifier l’égalité : 1 2p 2p2 + 2p3 2pq1 2pq 1

2p 1.

b. En déduire que 2pq 1 est divisible par 2p 1.

c. En déduire que si un entier k supérieur ou égal à 2 n'est pas premier, alors Mk ne l'est pas non plus.

3. a. Prouver que le nombre de Mersenne M11 n'est pas premier.

b. Que peut-on en déduire concernant la conjecture de la question 1. b. ?

Partie C Le test de Lucas-Lehmer permet de déterminer si un nombre de Mersenne donné est premier. Ce test utilise la suite numérique un définie par u0 4 et pour tout entier naturel n : un+1 un 2 2.

Si n est un entier naturel supérieur ou égal à 2, le test permet d'affirmer que le nombre Mn est premier si et seulement si un 2 0

modulo Mn. Cette propriété est admise dans la suite.

1. Utiliser le test de Lucas-Lehmer pour vérifier que le nombre de Mersenne M5 est premier.

2. Soit n un entier naturel supérieur ou égal à 3.

L'algorithme suivant, qui est incomplet, doit permettre de vérifier si le nombre de Mersenne Mn est premier, en utilisant le test

de Lucas-Lehmer.

Recopier et compléter cet algorithme de façon à ce qu'il remplisse la condition voulue.

Exercice 5 : en classe p 3 est un nombre premier

1. Quels sont les restes possibles dans la division de p par 12 ?

2. Prouver que p2 11 est divisible par 12.

WxMaxima

Variables : u, M, n et i sont des entiers naturels

Initialisation : u 4

Traitement : Demander un entier n 3

M

Pour i allant de 1 à faire

u p Fin Pour

Si M divise u alors afficher « M »

sinon afficher « M »

Exercice 6 : en classe Les nombres de Carmichaël ou pseudo-premiers 1. Introduction Soit p un nombre premier et a un entier naturel

si a est premier avec p :

d’après le petit théorème de Fermat, ap1 1 p (admis en spécialité)

c’est-à-dire ap1 1 est un multiple de p ;

donc aap1 1 est un multiple de p ;

donc ap a est un multiple de p ;

donc ap a p. a est un multiple de p :

alors a 0 p) donc ap 0 p donc ap a p. Donc une conséquence du petit théorème de Fermat est :

si p est un nombre premier alors pour tout a, ap a (p) 2. On se pose alors la question : la réciproque de ce théorème est-elle vraie ?

Si, pour tout a, an a n alors peut-on affirmer que n est premier ? (ce serait génial mais c’est faux).

Les contre-exemples de ce théorème s’appellent les nombres de Carmichaël.

Une caractérisation des nombres de Carmichael est donnée par le théorème de Korselt. (Totalement hors programme)

Théorème (Korselt, 1899) Un entier positif composé n est un nombre de Carmichael si et seulement si aucun carré de nombre premier ne divise n (on dit

que n est quadratfrei (sans carré)) et pour chaque diviseur premier p de n, le nombre p 1 divise n 1.

Il découle de ce théorème que tous les nombres de Carmichaël sont des produits d'au moins trois nombres premiers impairs

différents.

Korselt fut le premier à observer ces propriétés, mais il n'a pas pu trouver d'exemples de nombre de Carmichael.

En 1909, Robert Daniel Carmichaël trouva le plus petit de ces nombres, 561, et ceux-ci furent nommés en son honneur.

Ce nombre de Carmichaël 561 peut être vérifié avec le théorème de Korselt.

Effectivement, 561 31117 n'est pas divisible par un carré de nombre premier,

et 3 1 2, 11 1 10 et 17 1 16 sont tous trois des diviseurs de 560.

Les premiers nombres de Carmichael sont :

561 31117

1 105 51317

1 729 71319

2 465 5729

2 821 71331

6 601 72341

8 911 71967

3. Que faut-il savoir faire en spécialité ?

Démontrer que, pour tout a, a561 a (561).

Ou démontrer que, pour tout a et a premier avec 561 alors a560 1 (561). (voir ce qui précède)

Des pistes pour la démonstration.

a. Justifier que a2 1 (3), a10 1 (11) et a16 1 (17) (Le petit théorème de Fermat est admis)

b. Justifier que a560 1 est un multiple de 3, 11 et 17 puis conclure.

Pour une autre idée, voir exercice 7.

Exercice 7 : en classe Résultat admis : pour tout nombre premier p, pour tout entier a premier avec p, ap1 1 (modulo p) (Petit théorème de Fermat)

1. Décomposer 561 en produit de facteurs premiers.

2. On considère un entier naturel a.

a. Justifier que a561 a = a(a2280 1) a(a2 1)k avec k. (Méthode vue avec les nombres de Mersenne)

b. En déduire que a561 a est multiple de 3.

3. De la même manière, montrer que a561 a est multiple de 11 et de 17.

4. En déduire que, pour tout entier naturel a, a561 a (mod 561).

Que peut-on dire du nombre 561 ?

Exercice 8 : en classe et sont deux naturels et n 2 3..

Le nombre de diviseurs de n2 est le triple du nombre de diviseurs de n.

1. Prouver que ( 1)( 1) 3.

2. En déduire n.

Exercice 9 : en classe Théorème d’Euclide : On appelle nombre parfait un nombre dont la somme des diviseurs stricts est égal à lui-même. 1. Exemples : Euclide donne la règle suivante pour trouver des nombre parfait :

« Si un nombre a s’écrit 2n (2n1 1) est si 2n1 1 est premier, alors a est parfait ».

Trouver alors les quatre premiers nombres parfaits.

2. Démonstration. On pose a 2n (2n1 1) et supposons que 2n1 1 est premier.

a. Quelle est la décomposition de a en facteurs premiers ?

b. En déduire la liste des diviseurs de a.

c. Démontrer alors que la somme des diviseurs stricts est égale à ce nombre a.

Le problème de savoir s’il existe des nombres parfaits impairs n’est toujours pas résolu.

Exercice 10 : facultatif Dans cet exercice, on s’intéresse aux triplets d’entiers naturels (x, y, ) tels que x2 y2 2.

Ces triplets sont nommés « triplets pythagoriciens » en référence aux triangles rectangles dont ils mesurent les côtés, et notés en

abrégé « TP ». Ainsi (3, 4, 5) est un TP car 32 42 52.

Parte A : généralités

1. Démontrer que si, (x, y, ) est un TP, et p*, alors (px, py, p) est aussi un TP.

2. Démontrer que si, (x, y, ) est un TP, alors les entiers naturels x, y et ne peuvent pas être tous les trois impairs.

3. Pour cette question, on admet que tout entier naturel n non nul peut s’écrire de façon unique sous la forme d’une puissance de 2

par un entier impair. L’écriture n 2k est nommée décomposition de n.

Voici les décompositions de des entiers 9 et 120 : 9 299 , 120 2315.

a. Donner la décomposition de l’entier 192.

b. Soit x et deux entiers naturels non nuls, dont les décompositions sont x 2k et 2m.

Écrire la décomposition des entiers naturels 2x2 et 2.

c. En examinant l’exposant dans la décomposition de 2x2 et dans celle de 2, démontrer qu’il n’existe pas de couples d’entiers

naturels non nuls (x, ) tels que 2x2 2.

On admet que la question A-3 permet d’établir que les trois entiers naturels x, y, sont deux à deux distincts. Comme de plus les

entiers naturels x, y jouent un rôle symétrique, dans la suite, pour tout TP (x, y, ), les trois entiers naturels x, y et sont rangés dans

l’ordre suivant : x y

Parte B : recherche des triplets pythagoriciens contenant l’entier 2015 1. Décomposer en produit de facteurs premiers l’entier 2015 puis en utilisant le TP donné dans le préambule, déterminer un TP de

la forme (x, y, 2015).

2. On admet que, pour tout entier naturel n, (2n 1)2 (2n2 2n)2 (2n2 2n 1)2.

Déterminer un TP de la forme (2015, y, ).

3. a. En remarquant que 4032 169961, déterminer un couple d’entiers naturels non nuls (x, ) tels que 2 x2 4032

avec x 403.

b. En déduire un TP de la forme (x, 2015, ).