Comment savoir si un nombre est premier : les astuces indispensables

Introduction

Les nombres premiers ont fasciné les mathématiciens pendant des siècles. Bien qu’ils soient essentiels à la théorie des nombres, il n’y a pas de méthode simple pour les identifier. Cependant, il existe des astuces et des techniques pour déterminer si un nombre est premier ou non. Dans cet article, nous allons explorer ces astuces indispensables et vous aider à comprendre comment savoir si un nombre est premier.

Qu’est-ce qu’un nombre premier ?

Un nombre premier est un nombre entier qui ne peut être divisé que par 1 et par lui-même. Les nombres premiers sont donc des nombres qui ne sont pas divisibles par d’autres nombres que 1 et eux-mêmes.

Par exemple, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 sont des nombres premiers. En revanche, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18 ne sont pas des nombres premiers car ils sont divisibles par d’autres nombres que 1 et eux-mêmes.

Test de divisibilité par les premiers

Une première astuce pour déterminer si un nombre est premier est de le tester avec les nombres premiers. Si le nombre n’est pas divisible par un des nombres premiers, alors il est lui-même un nombre premier.

Les nombres premiers à tester sont 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 et 97. Pour un nombre donné, il suffit de le diviser par chacun de ces nombres premiers. Si le nombre n’est divisible par aucun de ces nombres premiers, alors il est lui-même un nombre premier.

Par exemple, pour savoir si 47 est un nombre premier, on teste sa divisibilité par les nombres premiers de 2 à 9 :

47 n’est pas divisible par 2 (car il est impair).
47 n’est pas divisible par 3 (car la somme de ses chiffres, 4 + 7, n’est pas divisible par 3).
47 n’est pas divisible par 5 (car il ne se termine pas par 0 ou par 5).
47 n’est pas divisible par 7 (car on trouve 42 en soustrayant 7 de 47, et 42 n’est pas divisible par 7).

47 n’est divisible par aucun des nombres premiers de 2 à 9, donc c’est un nombre premier.

Test de Wilson

Une autre astuce pour déterminer si un nombre est premier est le test de Wilson. Ce test est basé sur la formule suivante :

(n - 1)! mod n = n - 1

où n est le nombre que l’on souhaite tester et ! signifie factorielle (le produit de tous les entiers de 1 à n).

Si cette équation est vraie, alors le nombre n est premier. Sinon, il est composé.

Par exemple, pour savoir si 17 est un nombre premier, on calcule (17-1)! mod 17 :

16! mod 17 = 1

Comme (17-1)! mod 17 est égal à 1, 17 est un nombre premier.

Cependant, ce test n’est pas très efficace pour les grands nombres, car le calcul de la factorielle devient rapidement très complexe.

Test de Fermat

Le test de Fermat est une autre astuce pour déterminer si un nombre est premier. Il s’agit d’une méthode probabiliste, c’est-à-dire qu’elle donne une réponse qui n’est pas certaine à 100%.

Le test de Fermat repose sur le petit théorème de Fermat, qui stipule que si p est un nombre premier et a est un entier tel que 1 ≤ a < p, alors :

a^(p-1) ≡ 1 (mod p)

où ≡ signifie « est congru à » (c'est-à-dire que les deux nombres ont le même reste dans une division par p).

Le test de Fermat consiste à choisir un nombre a au hasard et à vérifier si cette équation est vraie pour le nombre que l'on souhaite tester. Si l'équation est vraie, alors le nombre est probablement premier. Si elle est fausse, alors le nombre est composé.

Cependant, il existe des nombres qui satisfont cette équation même s'ils ne sont pas premiers. Ces nombres sont appelés nombres de Carmichael. Par conséquent, le test de Fermat ne permet pas de garantir à 100% que le nombre testé est premier, mais permet de détecter la plupart des nombres composés.

Par exemple, pour savoir si 17 est un nombre premier, on choisit un nombre a au hasard, par exemple a = 3, et on calcule :

3^16 mod 17 = 1

Comme l'équation est vraie, 17 est probablement un nombre premier.

Test de Miller-Rabin

Le test de Miller-Rabin est une méthode probabiliste pour déterminer si un nombre est premier. Cette méthode est plus fiable que le test de Fermat, car elle permet de détecter les nombres de Carmichael.

Le test de Miller-Rabin consiste à choisir un nombre a au hasard et à effectuer une série de tests basés sur le petit théorème de Fermat. Si le nombre testé n'est pas un nombre premier, alors il y a une forte probabilité qu'il ne satisfasse pas au moins l'un de ces tests.

Le nombre de tests à effectuer dépend de la taille du nombre à tester. En général, pour un nombre de n chiffres, il est recommandé d'effectuer k = O(log n) tests.

Le test de Miller-Rabin est largement utilisé en cryptographie pour générer des nombres premiers aléatoires.

Conclusion

Savoir si un nombre est premier est un problème fondamental en mathématiques. Bien qu'il n'y ait pas de méthode simple pour identifier les nombres premiers, il existe des astuces et des techniques qui permettent de déterminer leur nature avec une forte probabilité. Parmi ces astuces, on peut citer le test de divisibilité par les premiers, le test de Wilson, le test de Fermat et le test de Miller-Rabin. À vous de choisir celle qui convient le mieux à vos besoins !

Note : Cet article n'est pas mis à jour régulièrement et peut contenir des informations obsolètes ainsi que des erreurs.