Les nombres premiers
- Fiche de cours
- Quiz
- Profs en ligne
- Videos
- Application mobile
- Maîtriser les notions d'infinitude et de répartition des nombres premiers, ainsi que les nombres premiers particuliers.
- Savoir décomposer un nombre en produit de facteurs premiers.
- Connaitre les nombres premiers particuliers (nombres de Mersenne, nombres de Fermat)
- Connaître le principe de clé publique et de clé privée du système cryptographique RSA.
- Un nombre premier admet exactement deux diviseurs : 1 et lui-même.
- L'ensemble des nombres premiers est infini.
- Les nombres premiers sont répartis irrégulièrement, et se raréfient.
- Tout nombre entier naturel supérieur ou égal à 2 est soit un nombre premier, soit un produit de nombres premiers (on appellera cela une décomposition en produit de facteurs premiers).
- La décomposition en produit de facteurs premiers, pour un entier naturel strictement supérieur à 1, est unique.
-
Les entiers de la forme
sont appelés nombres de
Mersenne. Si n n'est pas un nombre
premier, alors Mn n'est pas
premier.
-
Les entiers de la
forme
sont appelés nombres de
Fermat. Si n ≠ m,
alors Fn et Fm sont
premiers entre eux.
: 1 et lui-même.
0 admettant une infinité de diviseurs n'est pas un nombre premier.
1 n'admet qu'un seul diviseur 1, il n'est donc pas premier.
2 admet comme seuls diviseurs 1 et lui-même, il est donc premier.
Soit n un entier naturel supérieur ou égal à 2. Si n n'est divisible par aucun nombre premier p tel que
, alors n est
premier.
117 est un nombre premier, en effet :
, les seuls nombres premiers
compris entre 2 et 10 sont : 2, 3, 5 et 7. 117
n'est divisible par aucun de ces nombres, il est donc
premier.
Tout nombre entier naturel supérieur ou égal à 2 est soit un nombre premier, soit un produit de nombres premiers (on appellera cela une décomposition en produit de facteurs premiers).
Preuve
Supposons que n soit un nombre non premier. Il
existe alors un plus petit diviseur premier
d1 supérieur ou égal
à 2, et un entier naturel n1
tel que n = d1n1 avec
n1 < n. Puis on continue le
raisonnement : soit n1 est premier
soit il ne l'est pas ...
On construit donc une suite (ni)
d'entiers qui est strictement décroissante.
Cette suite est finie, si on note par r le
dernier rang on a donc : nr = 1. On
construit aussi une suite finie de nombres premiers
(pi), on a donc : n =
p1p2...pr
La décomposition en produit de facteurs premiers, pour un entier naturel strictement supérieur à 1, est unique.
- L'ensemble des nombres premiers est infini.
- La répartition des nombres premiers n'est pas régulière.
-
Loi de raréfaction des nombres
premiers : pour n assez grand, le nombre de
nombres premiers inférieurs ou égaux
à n est environ égal à
.
Marin Mersenne (1588-1648) était un scientifique qui tenta de dresser la liste de certains nombres premiers.
Les entiers de la forme
sont appelés nombres de
Mersenne.
Si n n'est pas un nombre premier, alors Mn n'est pas premier.
Preuve
Si n n'est pas un nombre premier, il existe donc
un diviseur p compris strictement entre 1 et
n, il existe donc un entier q tel que
n = pq. On a donc 
, donc Mn n'est pas un nombre
premier.
Si Mn est premier, alors n est premier.
Pierre de Fermat (1601-1665) était un
mathématicien qui émit la conjecture
suivante : les entiers de la forme 
+1 avec n un nombre
entier, sont premiers.
Les entiers de la forme
sont appelés nombres de Fermat.
On admet le théorème suivant :
Il s'agit d'un système de codage
développé au Massachussets Institute of
Technologie en 1977 par Ronald Rivest, Adi Shamir et
Léonard Adleman. Ce système est à
clé publique.
Je veux transmettre le message X.
La clé publique est la donnée de deux
nombres : e et n.
Par une procédure de calcul je transforme X
en Y, et je transmets Y.
Le message Y ne pourra être lu que par la
personne possédant la clé privée.
Méthode
- Création de la clé privée
d
On se donne 4 entiers naturels : p, q, e et d avec :
p et q premiers, e premier avec (p-1)(q-1) et ed
1 [(p-1)(q-1)]
- Création de la clé publique n et
e
On pose n = pq. - Transmission codée Y
On calcule Y = Xe [n] - Décodage de l'information Y
On calcule Yd
Xed
X [n] (utilisation du petit
théorème de Fermat)
Comment as-tu trouvé ce cours ?
Évalue ce cours !
Vous avez obtenu75%de bonnes réponses !
Recevez l'intégralité des bonnes réponses ainsi que les rappels de cours associés :
Fiches de cours les plus recherchées
Mathématiques expertes
Théorème de Bézout et théorème de Gauss
Mathématiques expertes
Module, argument, forme trigonométrique
Mathématiques expertes
Forme exponentielle - Formules de Moivre et d'Euler
Mathématiques expertes
Trinôme du second degré dans l'ensemble des nombres complexes
Mathématiques expertes
Divisibilité dans Z
Mathématiques expertes
Congruences dans Z
Mathématiques expertes
PGCD, nombres premiers entre eux
Mathématiques expertes
Division euclidienne
Mathématiques expertes
Les nombres premiers - Terminale
Mathématiques expertes
Théorème de Bézout et théorème de Gauss
Mathématiques expertes
Module, argument, forme trigonométrique
Mathématiques expertes
Forme exponentielle - Formules de Moivre et d'Euler
Mathématiques expertes
Trinôme du second degré dans l'ensemble des nombres complexes
Fermer
Accédez gratuitement à
