Nombres premiers
1. Définitions
Définition 1.
Un nombre entier naturel $p$ supérieur ou égal à $2$ est dit premier lorsqu’il n’admet pas d’autres diviseurs positifs que $1$ et lui-même.
Autrement dit : Un nombre entier naturel $p$ supérieur ou égal à $2$ est dit premier lorsqu’il admet exactement deux diviseurs positifs, $1$ et lui-même.
Cette définition exclut le nombre $1$ ; car $1$ admet exactement un seul diviseur : $1$ qui n’est autre que lui-même.
Définition 2.
Un nombre entier naturel $n$, distinct de $1$, qui n’est pas premier est dit composé.
Exemple 1. 2; 3; 5; 7; 11 ; sont des nombres premiers. 6 est un nombre composé.
2. Comment chercher des nombres premiers
Nous connaissons deux méthodes, appelées des cribles, pour déterminer tous les nombres premiers compris entre $1$ et un entier naturel $N$ quelconque. Une troisième méthode est d’utiliser un algorithme ou un programme sur calculatrice.
Comment déterminer tous les nombres premiers compris entre $1$ et $100$ ?
2.1. Le crible d’Eratosthène
[Eratosthène est un mathématicien grec 284-192 avant J.C.]
Cette méthode permet de déterminer la liste de tous les nombres premiers inférieurs à un nombre entier donné $N$.
Cette méthode se base sur la propriété suivante :
Propriété 1.
Pour tout entier naturel $p$, les multiples de $p$, strictement supérieurs à cet entier, ne sont pas premiers.
Méthode du crible d’Eratosthène.
Soit $N$ un entier naturel supérieur ou égal à $2$.
On construit un tableau comportant les entiers compris entre $1$ et $N$.
On barre le $1$. Ensuite, on conserve chaque premier nombre $p$ rencontré et on raye tous ses multiples stricts dans l’ordre croissant à partir de $p^2$.
Les nombres entiers non rayés sont donc premiers.
ILLUSTRATION : Déterminer tous les nombres premiers compris entre $1$ et $100$ avec le crible d’Eratosthène.
| 1 | 2 | 3 | 4$\hskip{-6pt}\diagup$ | 5 | 6$\hskip{-6pt}\diagup$ | 7 | 8$\hskip{-6pt}\diagup$ | 9$\hskip{-6pt}\diagup$ | 10${}\!\!\!\!\diagup$ |
| 11 | 12$\hskip{-10pt}\diagup$ | 13 | 14$\hskip{-10pt}\diagup$ | 15$\hskip{-10pt}\diagup$ | 16$\hskip{-10pt}\diagup$ | 17 | 18$\hskip{-10pt}\diagup$ | 19 | 20${}\!\!\!\!\diagup$ |
| 21$\hskip{-10pt}\diagup$ | 22$\hskip{-10pt}\diagup$ | 23 | 24$\hskip{-10pt}\diagup$ | 25${}\!\!\!\!\diagup$ | 26${}\!\!\!\!\diagup$ | 27${}\!\!\!\!\diagup$ | 28${}\!\!\!\!\diagup$ | 29 | 30${}\!\!\!\!\diagup$ |
| 31 | 32${}\!\!\!\!\diagup$ | 33${}\!\!\!\!\diagup$ | 34${}\!\!\!\!\diagup$ | 35${}\!\!\!\!\diagup$ | 36${}\!\!\!\!\diagup$ | 37 | 38${}\!\!\!\!\diagup$ | 39${}\!\!\!\!\diagup$ | 40${}\!\!\!\!\diagup$ |
| 41 | 42$\hskip{-10pt}\diagup$ | 43 | 44$\hskip{-10pt}\diagup$ | 45$\hskip{-10pt}\diagup$ | 46$\hskip{-10pt}\diagup$ | 47 | 48$\hskip{-10pt}\diagup$ | 49$\hskip{-10pt}\diagup$ | 50$\hskip{-10pt}\diagup$ |
| 51$\hskip{-10pt}\diagup$ | 52$\hskip{-10pt}\diagup$ | 53 | 54$\hskip{-10pt}\diagup$ | 55$\hskip{-10pt}\diagup$ | 56$\hskip{-10pt}\diagup$ | 57$\hskip{-10pt}\diagup$ | 58$\hskip{-10pt}\diagup$ | 59 | 60$\hskip{-10pt}\diagup$ |
| 61 | 62$\hskip{-10pt}\diagup$ | 63$\hskip{-10pt}\diagup$ | 64$\hskip{-10pt}\diagup$ | 65$\hskip{-10pt}\diagup$ | 66$\hskip{-10pt}\diagup$ | 67 | 68$\hskip{-10pt}\diagup$ | 69$\hskip{-10pt}\diagup$ | 70$\hskip{-10pt}\diagup$ |
| 71 | 72$\hskip{-10pt}\diagup$ | 73 | 74$\hskip{-10pt}\diagup$ | 75$\hskip{-10pt}\diagup$ | 76$\hskip{-10pt}\diagup$ | 77$\hskip{-10pt}\diagup$ | 78$\hskip{-10pt}\diagup$ | 79 | 80$\hskip{-10pt}\diagup$ |
| 81$\hskip{-10pt}\diagup$ | 82$\hskip{-10pt}\diagup$ | 83 | 84$\hskip{-10pt}\diagup$ | 85$\hskip{-10pt}\diagup$ | 86$\hskip{-10pt}\diagup$ | 87$\hskip{-10pt}\diagup$ | 88$\hskip{-10pt}\diagup$ | 89 | 90$\hskip{-10pt}\diagup$ |
| 91$\hskip{-10pt}\diagup$ | 92$\hskip{-10pt}\diagup$ | 93$\hskip{-10pt}\diagup$ | 94$\hskip{-10pt}\diagup$ | 95$\hskip{-10pt}\diagup$ | 96$\hskip{-10pt}\diagup$ | 97 | 98$\hskip{-10pt}\diagup$ | 99$\hskip{-10pt}\diagup$ | 100$\hskip{-10pt}\diagup$ |
Par conséquent ; la liste des nombres premiers inférieurs à $100$ sont : $2$ ; $3$ ; $5$ ; $7$ ; $11$ ; $13$ ; $17$ ; $19$ ; $23$ ; $29$ ; $31$ ; $37$ ; $41$ ; $43$ ; $47$ ; $53$ ; $59$ ; $61$ ; $67$ ; $71$ ; $73$ ; $79$ ; $83$ ; $89$ et $97$.
2.2. Le crible de Matiassevitch
Matiassevitch est un mathématicien russe, né en 1947.
Cette méthode utilise la parabole d’équation $y = x^2$.
On place deux points d’abscisses entières $M(– m ;m^2)$ et $P(n ;n^2)$, $m,n\leqslant$ puis leurs symétriques $M'(m ; m^2)$ et $P'(– n ; n)$ par rapport à $(Oy)$, puis on trace les $4$ segments joignant ces $4$ points. On recommence pour tous les nombres entiers naturels $m$ et $n$ supérieurs ou égaux à $2$ ; [compris entre $1$ et la partie entière $E(\sqrt{N})$ de $\sqrt{N}$, voir plus loin].
On démontre que les ordonnées entières sur l’axe $(Oy)$ (axe de symétrie de la parabole), qui n’appartiennent à aucun de ces segments sont tous les nombres premiers supérieurs ou égaux à $2$.
Source. Activité à réaliser [Maths TS, Éd. Bordas, collection Indice, Paris 2012, p.14].
3°) Méthode TICE
Avec un algorithme.
Un programme sur calculatrice
Texas Instrument
Casio 35+ ou supérieure
Reprendre et améliorer ces programmes pour afficher tous les diviseurs de $N$.
2) Propriétés des nombres premiers
Propriété n°2.
Pour tout entier $n$ supérieur ou égal à $2$ ; le plus petit diviseur de $n$, compris entre $2$ et $n$, est premier.
Soit n un entier supérieur ou égal à $2$.
Soit $p$ le plus petit diviseur de $n$ compris entre $2$ et $n$. Donc : $2\leqslant p\leqslant n$.
On fait un raisonnement par l’absurde.
Supposons que $p$ n’est pas premier.
Par définition, il existe deux entiers $a$ et $b$ différents de $1$ tels que $p = ab$.
Comme $a\not=1$, on a : $b < p$. D’autre part, comme $b\no=1$, on a $b\geqslant 2$.
Mais alors, $b|p$ et $p|n$, donc d’après la propriété de transitivité de la relation « divise », on peut affirmer que $b|n$, avec $2\leqslant b<p\leqslant n$.
Ce qui signifie que $p$ n’est pas le plus petit diviseur de $n$ compris entre $2$ et $n$.
Ce qui est absurde.
Conclusion : le plus petit diviseur de $n$ compris entre $2$ et $n$ est bien un nombre premier.
Propriété n°3.
Tout entier naturel composé $n$, admet un diviseur premier au plus égal à $\sqrt{n}$.
Démonstration.
Soit $n$ un entier naturel composé. Donc : $n\geqslant 2$.
D’après la propriété précédente, $n$ admet un plus petit diviseur premier compris entre $2$ et $n$. Appelons $d$ ce diviseur. Donc : $2\leqslant d\leqslant n$ et par définition, il existe un entier $q$ différent de $1$ tel que : $n = dq$.
Montrons que$d\leqslant \sqrt{n}$.
On fait un raisonnement par l’absurde.
Supposons que $d>\sqrt{n}$.
Or, par définition, $d$ est le plus petit diviseur premier de $n$, compris entre $2$ et $n$ et on sait que $n = dq$. Donc : $q\geqslant d$. Par suite : $q>\sqrt{n}$.
Mais alors, on a : $d>\sqrt{n}$ et $q>\sqrt{n}$.
En multipliant membre à membre les termes des deux inégalités entre nombres strictement positifs, on obtient une nouvelle inégalité de même sens.
Donc :$dq>\sqrt{n}\times\sqrt{n}$. Donc : $n>n$.
Ce qui est absurde.
Conclusion : $n$ admet un diviseur premier au plus égal à $\sqrt{n}$.
Propriété n°4.
Il existe une infinité de nombres premiers.
Démonstration.
On fait un raisonnement par l’absurde.
Supposons qu’il existe (seulement) un nombre fini d’entiers premiers.
Soit $p$ le plus grand de ces nombres premiers. Ce qui signifie que tous les entiers supérieurs à $p$ sont composés.
On définit un nombre entier $N$ comme le « produit de tous les entiers premiers ».
$$N=1\times 2\times 3\times 5\cdots\times p$$
puis on pose $N’ = N+1$. On a alors : $N’ > N$ donc $N’$ est composé.
D’après la propriété précédente, $N’$ admet un diviseur premier au plus égal à $\sqrt{N’}$.
Appelons $d$ ce diviseur. Donc $d|N’$.
Comme $N’ = N+1$, on a : $N’ – N = 1$.
Or, d’une part, $d|N$ car $d$ est premier et $N$ est le produit de tous les entiers premiers.
Et d’autre part, $d|N$ et $d|N’$ donc $d$ divise toute combinaison linéaire de $N$ et $N’$.
En particulier, $d|(N’ – N)$ et par suite $d|1$. Or, $d$ est un entier naturel, donc $d=1$.
Ce qui est absurde, puisque $d$ est premier.
Conclusion : Il n’existe pas de plus grand nombre premier. Donc l’ensemble des nombres premiers est infini.
Propriété n°5. Test de primalité.
Pour tout entier $n$ supérieur ou égal à $2$ ; si aucun des nombres entiers compris entre $2$ et $n$ ne divise $n$, alors $n$ est premier.
Démonstration.
On fait un raisonnement par contraposée.
Soit $n$ un entier supérieur ou égal à $2$.
Supposons que $n$ ne soit pas premier. Comme $n\not=1$, $n$ est un entier composé.
D’après la propriété n°3, admet un diviseur premier, $d $au plus égal à $\sqrt{n}$.
Par contraposition, on obtient le résultat demandé.
Propriété n°5bis. Test de primalité simplifié.
Pour tout entier $n$ supérieur ou égal à $2$ ; si aucun des nombres premiers compris entre $2$ et $\sqrt{n}$ ne divise $n$, alors $n$ est premier.
EXERCICE RÉSOLU n° : Tester si 317 est un nombre premier.
$\sqrt{317}=17,8044\ldots$. Il suffit de vérifier si 317 est divisible par $2$ ; $3$ ; $4$ ; $5$ ; $6$ ;$\ldots$ ; $17$.
Or $317$ n’est divisible par aucun de ces nombres entiers, donc $317$ est bien un nombre premier.
Remarque.
Avec la propriété 5bis, il suffit de tester la divisibilité de $317$ par les nombres premiers inférieurs ou égaux à $17$. (Un nombre qui est divisible par $6$, est divisible par $2$, le premier nombre premier de la série).
EXERCICE TICE : Reprendre et améliorer l’algorithme et les programmes ci-dessus pour afficher si un entier $N$ donné en entrée, est premier ou non.
3) Décomposition d’un nombre entier en facteurs premiers
Théorème d’existence de la décomposition d’un entier en facteurs premiers.
Théorème d’Euclide n°1.
Tout entier naturel $n$, supérieur ou égal à $2$, est un nombre premier ou un produit de nombres premiers.
Démonstration.
La propriété est vraie pour les premiers entiers naturels : $2$ ; $3$; $4 = 2^2$ ; $5$ ; $6=2\times 3$ ; $7$ ; $8=2^3$.
On fait un raisonnement par l’absurde.
Supposons qu’elle ne soit pas vraie pour tous les entiers.
Soit $n$ le plus petit entier supérieur ou égal à $2$ pour lequel la propriété est fausse.
Alors, $n$ n’est pas premier et $n$ ne peut pas s’écrire comme produit de nombres premiers.
Comme $n$ n’est pas premier, $n$ admet une plus petit diviseur $p$ premier, compris entre $2$ et $n$. Par définition, il existe un entier $q$ compris entre $1$ et $n$ tel que : $n = pq$.
Mais alors, $q < n$ et $n$ est le plus petit entier supérieur ou égal à $2$ pour lequel la propriété est fausse. Donc, $q$ satisfait la propriété. Donc $q$ est premier ou le produit de nombres premiers.
1er cas : $q$ est premier, alors $n = pq$ s’écrit comme produit de nombres premiers.
2ème cas : $q$ est un produit de nombres premiers, alors $n = pq$ s’écrit encore comme produit de nombres premiers.
Dans les deux cas, ont obtient que $n$ est un produit de nombres premiers.
Ce qui est absurde. CQFD.
Théorème d’unicité de la décomposition en facteurs premiers.
Théorème d’Euclide n°2. (Théorème admis)
Pour tout entier naturel $n$, supérieur ou égal à $2$, la décomposition de $n$ en produit facteurs premiers est unique à l’ordre près.
En écriture symbolique, si $n$ est un entier naturel supérieur ou égal à $2$, alors, il existe k nombres premiers $p_1 < p_2 <\cdots< p_k$, deux à deux distincts et $k$ entiers naturels non nuls : $\alpha_1$, $\alpha_2$,$\ldots$, $\alpha_k$, tels que : $$n=p_1^{\alpha_1}\times p_2^{\alpha_2}\times \cdots p_k^{\alpha_k}$$
Chaque $\alpha_i$ est le nombre de répétition du facteur $p_i$ dans la décomposition de $n$.
EXEMPLE RÉSOLU ET MÉTHODE : Donner la décomposition de $792$ en facteurs premiers.
Méthode.
On effectue des divisions successives de $792$ par chacun des nombres premiers $2;3;5;7;ldots$ en recommençant à chaque fois que le quotient est un entier composé jusqu’à épuisement de la division par chacun d’entre eux. On s’arrête lorsque le (dernier) quotient est égal à $1$.
$792=2\times 396$ ;
$396=2\times 198$ ; donc $792 =2\times2\times198$
$198=2\times 99$ ; donc $792 =2^3\times198$
$99$3\times 33$ ; donc $792=2^3\times 3\times 33$
$33=3\times 11$ ; donc $792=2^3\times 3^2\times 11$
$11=1\times 11$. Le dernier quotient est $1$. On s’arrête.
Conclusion. La décomposition de $792$ en facteurs premiers est la suivante :
$$792=2^3\times3^2\times11^1$$
EXERCICE TICE. A l’aide de cet exemple, reprendre et améliorer l’algorithme et les programmes précédents pour afficher la liste des diviseurs d’un entier $N$, donné en entrée.
Caractérisation des diviseurs d’un entier.
Propriété 6.
Pour tous entiers naturels $n$ et $d$, supérieur ou égal à $2$, on a l’équivalence suivante :
$d$ divise $n$ si, et seulement si, les exposants des facteurs premiers dans la décomposition de $d$ sont au plus égaux aux exposants des facteurs premiers dans la décomposition de $n$ respectivement.
Démonstration.
$(Rightarrow)$ Soient $d$ et $n$ deux entiers naturels. Supposons que $d|n$.
Si $p$ est un facteur premier qui apparaît dans la décomposition de $d$ avec un exposant $\alpha$, alors $p^{\alpha}|d$. Et comme $d|n$, on en déduit que : $p^{\alpha}|n$. Donc si $p^k|n$, et par suite : $\alpha\leqslant k$.
$(Leftarrow)$ Supposons que $n=p_1^{\alpha_1}\times p_2^{\alpha_2}\times \cdots p_k^{\alpha_k}$ et $d=p_1^{\beta_1}\times p_2^{\beta_2}\times \cdots p_k^{\beta_k}$, avec $0\leqslant\beta_i\leqslant\alpha_i$ pour tout $i =1,2,\ldots,k$, donc : $\alpha_i-\beta_i\geqslant 0$.
On a alors : $n=p_1^{\alpha_1-\beta_1}\times p_2^{\alpha_2-\beta_2}\times \cdots p_k^{\alpha_k-\beta_k}\times p_1^{\beta_1}\times p_2^{\beta_2}\times \cdots p_k^{\beta_k}$, ou encore : $n=\left(p_1^{\alpha_1-\beta_1}\times p_2^{\alpha_2-\beta_2}\times \cdots p_k^{\alpha_k-\beta_k}\right)\times d=q\times d$.
Donc, il existe un entier $q$ tel que $n=q\times d$, avec $q=\left(p_1^{\alpha_1-\beta_1}\times p_2^{\alpha_2-\beta_2}\times \cdots p_k^{\alpha_k-\beta_k}\right)$.
Donc $d|n$. CQFD.
4) Déterminer le nombre de diviseurs positifs d’un entier
4.1) Étude d’un exemple
EXERCICE RÉSOLU. Déterminer l’ensemble des diviseurs positifs de $792$.
Nous avons vu plus haut que $792=2^3\times 3^2 \times 11^1$. D’après la propriété ci dessus un diviseur de $792$ s’écrit : $d=2^\alpha\times 3^\beta\times11^\gamma$, avec $0\alpha\leqslant\3$ ; $\leqslant\beta\leqslant\2$ et $0\leqslant\gamma\leqslant\1$. On peut construire un arbre de dénombrement pour visualiser toutes les possibilités.
Ce nombre de diviseurs peut donc s’écrire en fonctions des exposants de la décomposition de 792 en facteurs premiers de la manière suivante :
$$24=(3+1)\times(2+1)\times(1+1)=4\times 3\times 2$$
Conclusion. La liste de tous les diviseurs de $792$ est : $1$ ; $2$ ; $3$ ; $4$ ; $6$ ; $8$ ; 9$ ; $11 : 12$ ; $18$ ; $22$ ; $24$ ; $33$ ; $36$ ;$44$ ; $66$ ; $72$ ; $88$ ; $99$ ; $132$ ; $198$ ; $264$ ; $396$ et $792$.
4.2) Nombre de diviseurs d’un entier naturel.
Nombre de diviseurs d’un entier.
Propriété 7.
Soit $n$ un entier naturel d dont la décomposition en facteurs premiers est $n=p_1^{\alpha_1}\times p_2^{\alpha_2}\times \cdots p_k^{\alpha_k}$. Alors le nombre $N$ de diviseurs de $n$ est égal à : $$N=$n=(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_k+k)$$ qu’on peut aussi noter : $$N=\prod_{i=0}^{i=k}(\alpha_i+1)$$
Démonstration.
Soit $n$ un entier naturel dont la décomposition en facteurs premiers est $n=p_1^{\alpha_1}\times p_2^{\alpha_2}\times \cdots p_k^{\alpha_k}$.
Choisir un diviseur $d$ de $n$, revient à choisir les différents exposants $\beta_i$ des diviseurs premiers $p_i$ avec $0leqslant\beta_i\leqslant\alpha_i\$.
On construit un arbre de dénombrement pour déterminer la totalité des possibilités de choix des exposants.
Il y a $(\alpha_1+1)$ possibilités de choisir $\beta_1$ : $0 ; 1 ; 2 ; … ; \alpha_1$ ;
Une fois $\beta_1$ choisi, il y a $(\alpha_2+1)$ possibilités de choisir $\beta_2$ ;
et ainsi de suite …
jusqu’au dernier facteur : Il y a $(\alpha_k+1)$ possibilités de choisir $\beta_k$ ;
A l’aide du principe multiplicatif d’un arbre de dénombrement, on obtient : $$N=$n=(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_k+k)$$ CQFD.
5. Exercices résolus
EXERCICE RÉSOLU n°1.
Liens connexes
Vues : 11