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.
![](https://e.educlever.com/img/4/7/0/0/470015.gif)
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
![](https://e.educlever.com/img/4/7/0/0/470019.gif)
117 est un nombre premier, en effet :
![](https://e.educlever.com/img/4/7/0/0/470021.gif)
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
![](https://e.educlever.com/img/4/7/0/0/470023.gif)
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
![](https://e.educlever.com/img/4/7/0/0/470027.gif)
![](https://e.educlever.com/img/4/8/0/0/480095.gif)
![](https://e.educlever.com/img/4/8/0/0/480097.gif)
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 ed1 [(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 YdXed
X [n] (utilisation du petit théorème de Fermat)
Vous avez obtenu75%de bonnes réponses !