NOMBRES - Curiosités, théorie et usages Accueil DicoNombre Rubriques Nouveautés Édition du: 12/02/2016 Orientation générale  DicoMot Math Atlas Références M'écrire Barre de recherche DicoCulture Index alphabétique
	DIVISION
Débutants Division	Divisibilité			Glossaire Division
INDEX Divisibilité	Introduction	Récapitulatif	Par 641	Critères généraux
	Terminale Spécialité	Sommaire de cette page >>> Propriétés >>> Calculette >>> Calcul à la main >>> Méthode classique >>> Méthode astucieuse >>> Programmation

DIVISIBILITÉ par 641

Nombre de Fermat n°5: divisible par 641.

Enjeu historique: on savait que les nombres de Fermat inférieurs à F₅ étaient tous premiers. Fermat, lui-même, conjecturait qu'ils étaient tous premiers. On sait qu'ils sont tous composés à partir de F₅ et jusqu'à F₃₁.

Aujourd'hui: Sachant que ce nombre est divisible par 641, plusieurs méthodes de calcul sont possibles: à la main, calculette ou via les congruences classiquement ou via une astuce. Ne connaissant pas 641, la méthode directe consisterait à écrire un programme pour détecter cette valeur.

Voir Règles générales de divisibilité

Propriétés
Le nombre de Fermat F5 est composé. Il est divisible par 641.
Autres puissances de 2 mod 641 N = r mod m veut dire que N divisé par m donne un reste r.	2^32 – 1 mod 641 2^64 1 mod 641 2^96 – 1 mod 641 etc.

Calculette
Calculette: la touche Mod permet un calcul immédiat. Sans cette touche, le calcul proposé ci-contre est facile à réaliser sur la calculette. Les deux touches à utiliser	2^32 = 4 294 967 296; divisé par 32 = 6 700 416,99 et 6 700 416 x 641 = 4 295 159 597 soit 1 de moins que 2^32. Donc: 2^32 – 1 mod 641. Certains affirment même que le calcul de la division à la main est un excellent exercice. Cependant, les démonstrations algébriques ci-dessous montrent où se nichent les beautés mathématiques.

Calcul à la main

Démonstration classique
Quel est le reste de la division de 2^32 par 641? Notez la tactique algébrique pour s'approcher de 641 et ainsi faire tous les calculs de tête. On se souviendra que: 640 – 1 mod 641.	En mod 641: 2^8 256 2^16 = 2^82^8 256 x 256 = 64 x 4 x 256 64 x 1024 = 64 (1020 + 4) = 64 x 1020 + 256 = 640 x 102 + 256 256 + (-1) x 102 = 154 2^32 = 2^162^16 154^2 = 14² x 11² = 196 x 121 = (64 x 3 + 4) (64 x 2 – 7) = 6 x 64² + 8 x 64 – 21 x 64 – 28 = 64 (384 + 8 – 21) – 28 = 64 x 371 – 28 = 64 (370 + 1) – 28 = 640 x 37 + 64 – 28 = 640 x 37 + 36 36 + (–1) x 37 = –1 2^32 – 1 mod 641 2^32 + 1 0 mod 641

Démonstration astucieuse (Coxeter)
La barre verticale veut dire: divise. On utilise l'identité remarquable: n^4 – 1 = (n + 1) ( …) avec n = 5 x 2^7	641= 5^4 + 2^4 = 5 x 2^7 + 1 641 (5^4 + 2^4) x 2^28 = 2^28 x 5^4 + 2^32 = (5 x 2^7)^4+ 2^32 = (5 x 2^7)^4 – 1 + 1 + 2^32 641 2^32 + 1) = F5

Programmation
	Le programme Maple est archi-simple et son exécution est instantanée. N prend la valeur du nombre de Fermat. Boucle avec m qui prend toutes les valeurs de 2 à 1000 (c'est large). R est le reste de la division, cad. le modulo de N par m. Si ce reste est nul, on imprime la valeur de m. Seul résultat: m = 641.
	Même programme pour le nombre de Fermat suivant. Dans ce cas la boucle examine un million de cas en quelques secondes.
5, ``(5) 17, ``(17) 257, ``(257) 65537, ``(65537) 4294967297, ``(641) *``(6700417) etc.	Ceci-dit, Maple dispose d'une instruction qui donne la directement factorisation (ifactor). Compte tenu de la quantité de chiffres (78 pour pour F8), la factorisation au-delà de F7 prend énormément de temps et devient vite impossible.

Voir Programmation – Index

Suite	Divisibilité par 576 Calcul modulo – Exemples
Voir	Nombres de Fermat Fermat – Petit théorème Nombres magiques – Index Théorie des nombres – Index
Diconombre	Nombre 641
Cette page	http://villemin.gerard.free.fr/Wwwgvmm/Decompos/D641.htm