Les nombres premiers
Un article de Haypo.
Retour aux articles de mathématiques
Sommaire |
[modifier] Définition
C'est un nombre ayant exactement deux diviseurs (entiers naturels). Exemples: 2, 3, 5, 7, 11, 13, 17, 19, ... Par contre 1 (l'unité) n'est pas premier car il n'est divisible que par lui même. Le nombre 5 (par exemple) est divisible par 5, mais aussi par l'unité, d'où sa primauté (caractère d'être premier pour un nombre). Les nombres entiers relatifs ne sont pas premiers car ils sont divisibles par -1 et leur opposé, ça fait au minimum 4 diviseurs!
[modifier] Nombre composé
Un nombre composé est un nombre qui n'est pas premier ! "Composé" car on peut l'écrire sous forme de produit de facteurs premiers. Exemple: 14 est composé, on peut l'écrire 2*7 (les nombres 2 et 7 sont premiers).
[modifier] Nombre de Mersennes
Les nombres de Mersennes sont les nombres de la forme :
Mn = 2n - 1
Si Mn est premier, alors n est premier, la réciproque étant fausse.
Mn est pour premier pour n valant : 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, ...
[modifier] Petite théorème de Fermat (1640)
Soit p: un nombre premier
Le petit théorème de Fermat peut s'énoncer sous trois formes différentes :
- Pour tout entier a, ap ≡ a (modulo p)
- Pour tout entier a qui n'est pas multiple de p : ap-1 ≡ 1 (modulo p)
- Pour tout entier a qui n'est pas multiple de p, il existe un entier k > 0 tel que que ak ≡ 1 (modulo p).
En outre, le plus petit k > 0 vérifiant cette équation divise (p-1)
Par contre, la contraposée est fausse. Par exemple : le nombre p n'est pas obligatoirement premier si 2p ≡ 2 (modulo p) (faux pour p=341).
[modifier] Théorème de Wilson
Énoncé du théorème de Wilson :
Un nombre entier n (supérieur à 1) est premier si (p-1)! ≡ -1 (modulo p)
Ce théorème est très simple, mais en pratique il est très long de calculer un factoriel, même si on calcule "modulo p" (on calcule modulo p à chaque itération du calcul du fatoriel, ce qui limite la taille du résultat).
Note: (-1) modulo p ≡ (p-1) (modulo p)
[modifier] Voir aussi
[modifier] Articles connexes
[modifier] Liens externes
- The ECMNET Project: Projet de LORIA consistant à prouver que la prédiction de Richard est vraie, c'est à dire que la méthode des courbres elliptiques (Elliptic Curve Method, ECM) permet de trouver des facteurs de plus de 50 chiffres dans la factorisation de grands nombres entiers. Site très intéressant, contenant de nombreux liens.
- RSA.com: Tout ce qui concerne le cryptage RSA qui a besoin de deux nombres premiers, ou plutôt un produit de deux nombres premiers, c'est à dire un nombre composé de deux facteurs (ex: 77 = 7*11).
[modifier] Bibliographie
- « Merveilleux nombres premiers » de Jean-Pierre DELAHAYE aux éditions Pour la science (ISBN : 2-84245-017-5). C'est un très bon livre de vulgarisation.
