Prouver qu'un million est premier demande mille divisions, non un million
Publié le 16/11/2026 · 3 min de lecture · Calculateurs du quotidien
Lena Hoffmann — Rédactrice Sciences & Éducation chez OneKitly
Mathématiques · Physique
Vérifié à partir de 2 sources
Pour tester si un nombre a un facteur, il n'est jamais nécessaire de regarder au-delà de sa racine carrée. Si un nombre se scinde en deux facteurs, l'un est au plus égal à la racine et l'autre au moins égal : ne rien trouver de petit signifie donc qu'il n'y a rien du tout. Tester 1 000 003 ne demande donc des divisions d'essai que jusqu'à 1000, et il leur survit toutes : il est premier. Son voisin 1 000 001 tombe vite, car 101 le divise exactement, laissant 9901. La racine carrée est ce qui transforme une recherche impossible en travail d'un après-midi, et c'est la première chose que découvre quiconque écrit un test de primalité.
1 000 003 est premier et la preuve s'arrête à 1000, sa racine carrée. 1 000 001 ne l'est pas, et la recherche s'achève au troisième essai : 101 le divise.
Seuls les premiers valent d'être essayés
Diviser par 4 est peine perdue si 2 a déjà échoué : la liste des candidats n'est pas les mille nombres sous la racine mais les 168 premiers qui s'y trouvent. Cela seul divise le travail par six, et sauter les pairs et les multiples de trois attrape presque gratuitement l'essentiel du reste. L'implémentation classique teste 2, puis 3, puis tout nombre de la forme « à un de part et d'autre d'un multiple de six », ce qui couvre tous les premiers possibles en n'essayant qu'un tiers des entiers.
Pourquoi l'astuce cesse d'aider
Diviser par deux le nombre de chiffres semble énorme jusqu'à ce que le nombre soit long. La racine carrée d'un nombre de 600 chiffres en a encore 300 : les divisions d'essai sur les clés de la cryptographie moderne exigeraient plus d'opérations qu'il n'y a d'atomes dans l'univers observable. Les vrais tests de primalité abandonnent donc la division et emploient des tests probabilistes dont la probabilité d'erreur peut être poussée sous n'importe quel seuil. Ces tests prouvent bien plus facilement qu'un nombre est composé qu'ils n'en exhibent un facteur, et c'est exactement l'asymétrie sur laquelle repose la sécurité.
| Nombre | Divisions à essayer | Résultat |
|---|---|---|
| 1 000 001 | 3 avant l'échec | 101 × 9901 |
| 1 000 003 | 168 premiers jusqu'à 1000 | Premier |
| Un nombre de 600 chiffres | Plus que d'atomes dans l'univers | Inutilisable |
Questions fréquentes
- Pourquoi 1 n'est-il pas premier ?
- Par décision, pour garder l'unicité de la factorisation. Si 1 comptait, 12 pourrait s'écrire 2×2×3, ou 1×2×2×3, ou 1×1×2×2×3, et l'énoncé selon lequel tout nombre a exactement une factorisation première demanderait une clause d'exception. Les tables du XIXe siècle listaient bien 1 comme premier, et la convention a changé parce que chaque théorème devenait plus propre sans lui. Les définitions en mathématiques se choisissent pour leurs conséquences plutôt qu'elles ne se découvrent, et voici le plus clair des petits exemples.
- Comment tester un nombre à la main ?
- Prenez la racine carrée, arrondissez au-dessus, et divisez par tous les premiers jusque-là. Sous dix mille, cela fait au plus 25 divisions, dont l'essentiel se règle instantanément : les pairs échouent sur 2, les sommes de chiffres divisibles par trois échouent sur 3, tout ce qui finit par 0 ou 5 échoue sur 5. Ce qui survit pour être testé sérieusement forme une courte liste. Au-delà du million, la méthode devient fastidieuse plutôt que difficile, et c'est exactement le moment de la confier à une machine.
Articles qui pourraient t'intéresser
Tous les guides →Outils similaires
Sources
Tu as repéré une erreur dans cet article ?