Décomposition en facteurs premiers et nombre premier

Décomposer un nombre et savoir s'il est premier

Cet outil répond à deux questions qu'on se pose souvent en mathématiques : est-ce un nombre premier ? et quelle est sa décomposition en facteurs premiers ? Pour un entier jusqu'à 40 chiffres, vous obtenez la réponse, la méthode, l'écriture en puissances (2³ × 3² × 5), les diviseurs et les nombres premiers voisins. Un second mode donne la liste des nombres premiers jusqu'à 10 millions.

Mode d'emploi

1. Choisissez « Tester et décomposer un nombre », saisissez-le dans « Nombre entier » puis cliquez sur « Analyser » ou appuyez sur Entrée. Vous pouvez aussi écrire une puissance comme 2^61 − 1.
2. Les « Divisions successives » détaillent le calcul. Cochez « Afficher l'arbre de facteurs » pour le voir sous forme d'arbre, et « Afficher la liste des diviseurs » pour tous les diviseurs et leur somme.
3. Pour la liste, choisissez « Liste des nombres premiers », saisissez N dans « Nombres premiers jusqu'à N » puis « Afficher la liste ». « Télécharger la liste (.txt) » enregistre la liste complète.

Nombres premiers : ce qu'il faut savoir

Un nombre premier est un entier qui a exactement deux diviseurs : 1 et lui-même. 2, 3, 5, 7, 11 et 13 sont premiers ; 2 est le seul nombre premier pair. 1 n'est pas premier, car il n'a qu'un seul diviseur. 0 ne l'est pas non plus. Les autres entiers supérieurs à 1 sont composés.

Pour tester un nombre, il suffit d'essayer de le diviser par les entiers de 2 jusqu'à sa racine carrée. Pour 97, √97 ≈ 9,8 : ni 2, ni 3, ni 5, ni 7 ne divisent 97, il est donc premier. Attention aux pièges : 91 semble premier, mais 91 = 7 × 13. Pour les très grands nombres, l'outil utilise le test de Miller-Rabin, sans erreur possible jusqu'à 2⁶⁴ et bien au-delà.

La méthode de décomposition

On divise par le plus petit nombre premier possible tant que la division tombe juste, puis on passe au suivant. Avec 1 260 : 1 260 ÷ 2 = 630, 630 ÷ 2 = 315, 315 ÷ 3 = 105, 105 ÷ 3 = 35, 35 ÷ 5 = 7, 7 ÷ 7 = 1. Donc 1 260 = 2² × 3² × 5 × 7. Cette décomposition est unique, à l'ordre près. Elle donne aussi le nombre de diviseurs : on ajoute 1 à chaque exposant et on multiplie, soit 3 × 3 × 2 × 2 = 36 diviseurs.

Elle sert aussi à simplifier une racine carrée : √1 260 = 6√35.

Le crible d'Ératosthène

Pour lister les nombres premiers jusqu'à N, on écrit les entiers de 2 à N, on garde 2 et on barre ses multiples, puis on garde le premier nombre non barré, 3, et on barre ses multiples, et ainsi de suite. Jusqu'à 100, il suffit de barrer les multiples de 2, 3, 5 et 7 : il reste 25 nombres premiers. Il y en a 664 579 jusqu'à 10 millions.

Il existe une infinité de nombres premiers : Euclide l'a démontré il y a plus de 2 000 ans. Certains systèmes de chiffrement reposent sur le fait qu'il est très long, avec les méthodes connues, de retrouver deux grands nombres premiers à partir de leur produit lorsqu'ils comptent des centaines de chiffres.

Questions fréquentes

Pourquoi 1 n'est-il pas un nombre premier ?

Un nombre premier doit avoir exactement deux diviseurs distincts, et 1 n'en a qu'un. Exclure 1 garantit aussi l'unicité de la décomposition : sinon 6 pourrait s'écrire 2 × 3, 1 × 2 × 3, 1 × 1 × 2 × 3…

Quel est le plus grand nombre que l'outil peut traiter ?

Le test et la décomposition acceptent jusqu'à 40 chiffres. La décomposition peut être longue quand le nombre est le produit de deux grands nombres premiers : le calcul s'arrête alors après 10 secondes et indique le facteur qui n'a pas pu être décomposé.

2⁶¹ − 1 est-il premier ?

Oui : 2⁶¹ − 1 = 2 305 843 009 213 693 951 est un nombre premier de Mersenne. Tapez 2^61 − 1 pour le vérifier. Le plus grand nombre premier inférieur à 2⁶⁴ est 18 446 744 073 709 551 557.