Les nombres premiers sont les briques des entiers : tout entier au moins égal à est, de façon unique, un produit de nombres premiers. Avec le petit théorème de Fermat, ils fondent le chiffrement RSA, qui protège tes échanges sur internet. À la fin du chapitre, tu sauras reconnaître un nombre premier, décomposer un entier, calculer le reste d'une énorme puissance et chiffrer un message.
Reconnaître un nombre premier
Un entier naturel est premier s'il a exactement deux diviseurs positifs : et . Donc et ne sont pas premiers, et est le seul premier pair.
Propriété. Tout entier a au moins un diviseur premier : son plus petit diviseur supérieur ou égal à .
Critère. Si n'est divisible par aucun nombre premier tel que , alors est premier. En effet, si avec , alors , et tout diviseur premier de divise avec .
Exemple résolu
est-il premier ?
- : tu testes les premiers jusqu'à .
- Ni , ni (), ni ne divisent .
- , et : aucun reste nul, donc est premier.
Le crible d'Ératosthène
Pour lister les premiers jusqu'à , écris les entiers de à . Le premier nombre non barré est premier : garde-le et barre ses autres multiples, puis recommence avec le suivant non barré. Dès que ce nombre vérifie , arrête : tous les nombres non barrés sont premiers.
Exemple résolu
Jusqu'à , tu barres les multiples de , , et ; le suivant, , vérifie . Il reste quinze premiers : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.
Raisonner avec les nombres premiers
Lemme d'Euclide. Si un nombre premier divise un produit , alors divise ou divise . En effet, si ne divise pas , et sont premiers entre eux (leur PGCD divise et n'est pas ), et le théorème de Gauss donne .
Exemple résolu
Si divise , comme est premier et ne divise pas , alors divise .
L'ensemble des nombres premiers est infini
Démonstration par l'absurde.
- Suppose qu'il n'y ait qu'un nombre fini de nombres premiers, , et pose .
- Comme , a un diviseur premier , qui est l'un des .
- Alors divise et , donc leur différence, : impossible, car .
- L'hypothèse est fausse : il existe une infinité de nombres premiers.
Montrer qu'un nombre n'est pas premier
Exemple résolu 1. Pour , est un produit de deux entiers au moins égaux à : il n'est pas premier.
Exemple résolu 2 (nombres de Mersenne). , donc : divise , qui n'est pas premier. De même, divise : si n'est pas premier, ne l'est pas non plus.
Décomposer en facteurs premiers
Théorème. Tout entier s'écrit de façon unique , avec premiers et entiers naturels non nuls.
L'existence s'obtient en divisant par son plus petit diviseur premier, puis le quotient par le sien, jusqu'à obtenir . L'unicité découle du lemme d'Euclide.
Exemple résolu
Tu divises par tant que c'est possible, puis par , puis par :
Les diviseurs d'un entier
Les diviseurs positifs de sont les entiers avec pour chaque ; il y en a .
Exemple résolu
a diviseurs positifs. en est un ; n'en est pas un, car l'exposant dépasse .
Le petit théorème de Fermat
Théorème. Si est premier et si est un entier non divisible par , alors .
Conséquence. Pour tout entier , : si divise , les deux membres sont congrus à ; sinon, multiplie le théorème par .
Exemple résolu 1. Reste de dans la division par .
- est premier et ne divise pas , donc .
- , donc .
- : le reste est .
Exemple résolu 2. Pour tout entier , , donc divise .
Un test de non-primalité
Par contraposée, s'il existe un entier tel que et , alors n'est pas premier : est un témoin. Pour et : , donc , et n'est pas premier.
La réciproque du théorème est fausse : , donc , alors que . Les nombres de Carmichaël, comme , trompent même le test pour tout premier avec eux.
Chiffrer et déchiffrer
Le chiffrement affine
Chaque lettre a un rang (, , …, ) et elle est codée par la lettre de rang , reste de modulo , où et sont des entiers fixés. Pour déchiffrer, il faut que soit premier avec : a alors un inverse modulo , et .
Exemple résolu
Avec et :
- M a le rang et : M est codée par la lettre de rang , P.
- : est un inverse de , et .
- Pour P : , tu retrouves M.
Avec , A et N sont codées par la même lettre, car : le déchiffrement est impossible.
Le principe du chiffrement RSA
- Choisis deux nombres premiers distincts et , et pose .
- Choisis premier avec et un inverse de modulo .
- Un message , entier tel que , est chiffré par , reste de modulo .
- Le reste de modulo redonne : le petit théorème de Fermat, appliqué modulo puis modulo , prouve que .
Le couple est public et secret : on ne sait pas factoriser rapidement un de plusieurs centaines de chiffres.
Exemple résolu
et , donc et .
- Avec : , donc .
- Le message est chiffré par .
- ; or donne , et donne .
- et , premiers entre eux, divisent , donc aussi : tu retrouves .
Les pièges
- S'arrêter trop tôt : pour , teste jusqu'à inclus, car .
- Le lemme d'Euclide sans premier : divise , mais ni ni .
- Croire que est premier : .
- Fermat sans ses hypothèses : il faut premier et ne divisant pas ; par exemple .
- Mauvais diviseur de l'exposant : pour modulo , divise par , pas par .
- Diviser dans une congruence : pour déchiffrer, multiplie par l'inverse ; écrire n'a pas de sens modulo .
Ce qu'il faut retenir
- Si n'a aucun diviseur premier tel que , alors est premier.
- Il existe une infinité de nombres premiers.
- Si un premier divise , alors divise ou .
- Tout a une unique décomposition en facteurs premiers, et diviseurs positifs.
- Si est premier et ne divise pas , ; pour tout , .
- Chiffrement affine : déchiffrable si et seulement si est premier avec , et .
- RSA : , , , .
À l'épreuve
Les maths expertes sont évaluées en contrôle continu. En devoir surveillé, ce chapitre donne des questions enchaînées : décomposer un entier puis dénombrer ses diviseurs, trouver un inverse modulo puis déchiffrer, démontrer que divise . La démonstration de l'infinité des nombres premiers peut être demandée telle quelle.
Ton professeur attend les hypothèses citées avant chaque théorème (« est premier et ne divise pas ») et chaque division posée. Tu perds des points si tu calcules une puissance en entier au lieu de la réduire, ou si tu déclares un nombre premier sans les divisions testées.