CARTE POSTALE 2213 du 15 juin 2008

PUISSANCE DE DEUX
	22

Observation

Trouver les facteurs de 2^16 – 1 = ?	On peut calculer 2^16 – 1 = 65 535 = 5 x 13 107 = 5 x 3 X 4 369 = ?
Pas facile de factoriser avec un si grand nombre!

Exploration

L'idée consiste à remarquer que nous avons à faire à la différence de deux puissances identiques, paires qui plus est.		2^16 – 1 = 2^16 – 1^16
Nous nous souvenons d'une identité remarquable qui va nous aider		a² – b² = (a + b) (a – b)
Appliquons cette identité à notre expression numérique Remarquons que nous faisons apparaître une nouvelle différence de puissances paires		2^16 – 1^16 = (2^8 + 1^8) (2^8 – 1^8)
Appliquons encore, et jusqu'au bout	2^16 – 1 = (2^8 + 1^8) (2^8 – 1^8) = (2^8 + 1^8) (2^4 + 1^4) (2^4 – 1^4) = (2^8 + 1^8) (2^4 + 1^4) (2^2 + 1^2) (2^2 – 1^2) = (2^8 + 1) (2^4 + 1) (2^2 + 1) (2^2 – 1)
Factorisation finale	2^16 – 1 = 257 x 17 x 5 x 3 et tous ces facteurs sont premiers

Voir plus loin

PLUS GRAND …

2³² – 1 = (2¹⁶ + 1) (2⁸ + 1) (2⁴ + 1) (2² + 1) (2² – 1)

= 65 537 x 257 x 17 x 5 x 3

et ce nouveau facteur est premier

2⁶⁴ – 1 = (2³² + 1) (2¹⁶ + 1) (2⁸ + 1) (2⁴ + 1) (2² + 1) (2² – 1)

= 4 294 967 297 x 65 537 x 257 x 7 x 5 x 3

Et ce nouveau facteur est composé. Calculs faits (pas simples), on trouve

2⁶⁴ – 1 = (2³² + 1) (2¹⁶ + 1) (2⁸ + 1) (2⁴ + 1) (2² + 1) (2² – 1)

= 6 700 417 x 65 537 x 641 x 257 x 7 x 5 x 3

Avec un peu d'astuce, on peut trouver les facteurs premiers sans faire de grands calculs, mais … seulement lorsque la configuration proposée s'y prête!

Autres cartes postales

En savoir plus

Orientation

Gérard Villemin

Tableau des puissances de deux plus ou moins un et leur factorisation

Cellule jaune => nombre premier

n	2^n – 1	2^n + 1
2	3	5
4 = 2^2	15 = 3 x 5	17
8 = 2^3	255 = 3 X 5 X 17	257
16 = 2^4	65 535 = 3 x 5 x 17 x 257	65 537
32 = 2^5	42 94 967 295 = 3 x 5 x 17 x 257 x 65 537	4 294 967 297
64 = 2^6	1, 84 … 10^19 = 3 x 5 x 17 x 257 x 641 x 65 537 x 7 700 417	1, 84 … 10^19 = 18 446 744 073 709 551 617 = 274 177 x 67 280 421 310 721
Propriété	Tous composés, divisibles par 3, 5, 17 etc.	Les cinq en tête de liste sont les seuls nombres premiers connus de cette forme
Rappel	Mersenne pour n = premier	Nombre de Fermat pour n = 2^k Ils se terminent tous par 7 (sauf le premier)