Pouvez-vous me dire comment savoir si un nombre est premier?

Bonjour Katia,

Il y a plusieurs niveaux de reponse:

1. Un nombre est N premier si et seulement si sa division par tous les nombres de 2 jusqu'a la racine carree de N laisse un reste.

   Cette caracterisation fonctionne assez bien pour verifier a la main si un petit nombre de trois chiffres est premier, ou a l'ordinateur si un nombre de dix chiffres est premier, mais elle est trop lente pour les nombres plus grands.

   Pour la suite, on note A % B le reste de la division de A par B, et A^B la B-ieme puissance de A. Les algorithmes d'"exponentiation modulaire par mises au carre successives" permettent d'evaluer rapidement les nombres de la forme (A^B) % C, meme lorsque l'exposant B est tres grand. On peut ainsi appliquer rapidement le test de Fermat:

2. Pour tout nombre premier N et pour tout nombre a entre 2 et N-1, (A^N-1) % N = 1.

   Par exemple, mon ordinateur calcule en moins d'une seconde
   (2²⁰⁰⁸) % 2009 = 1773,
   ce qui permet de conclure que 2009 n'est pas premier. Par contre,
   (2²⁰⁰²) % 2003 = 1,
   (3²⁰⁰²) % 2003 = 1,
   (5²⁰⁰²) % 2003 = 1,
   mais ces resultats ne permettent pas de conclure que 2003 est premier: un nombre qui passe le test de Fermat a de fortes chances d'etre premier, mais ce n'est pas une certitude (en fait, 2003 est premier).

3. Un nouvel algorithme vient d'etre concu en 2002 par Agarwal, Kayal et Saxena, qui dit avec certitude si un nombre est premier ou compose. Il s'apparente au test de Fermat, mais utilise plutot les polynomes en arithmetique modulaire.

   Notons que ni le test de Fermat, ni le nouvel algorithme ne permettent de trouver un facteur d'un nombre lorsqu'ils demontrent que ce nombre n'est pas premier. C'est la magie de la chose.

Claude

La Centrale des maths