4 – Nombres Premiers

cours pdf

I – L’ensemble des nombres premiers.

1°) Définition et existence.

Définition :
On dit qu’un entier naturel est un nombre premier s’il admet exactement deux diviseurs distincts 1 et lui-même.

Remarques :

  1. On trouve généralement la définition suivante. Un entier naturel \( \ge \)2 est premier si ses seuls diviseurs sont 1 et lui-même.(On exclut 1 pour avoir unicité dans la décomposition en produit de facteurs premiers car sinon 6=2*3 mais aussi 6=2*3*1 ou 6=2*3*\(1^n\) où \(n\) est un entier naturel.)
  2. Une conséquence est que 0 qui est divisible par tous les entiers et 1 qui n’a qu’un seul diviseur ne sont pas des nombres premiers.
  3. Vocabulaire : un nombre non premier est dit composé.
  4. Un entier non premier admet un diviseur autre que 1 et lui-même ; on dit que c’est un diviseur strict. (2 et 4 sont les diviseur stricts de 8).

Exemple :
7 est un nombre premier car admet exactement deux diviseurs distincts 1 et 7.
12 n’est pas un nombre premier car il admet plus de deux diviseurs distincts qui sont 1, 2, 3, 4, 6.

Proposition : existence des nombres premiers.
Tout entier naturel \(n\), avec \(n\)\( \ge \)2, admet au moins un nombre premier comme diviseur.

Démonstration :

  • Si \(n\) est premier, le diviseur premier de \(n\) est \(n\) donc \(n\) admet un diviseur premier : lui-même.
  • Si \(n\) n’est pas premier, \(n\) admet au moins un diviseur strict. Soit \(Di{v_{\mathbb{N}}} = \left\{ {1;{n_1};{n_2}; \cdots ;n} \right\}\) les diviseurs de \(n\) rangés dans l’ordre croissant. Montrons que \(n_1\) est premier en raisonnant par l’absurde.
    Si \(n_1\) n’est pas premier, alors \(n_1\) admet un diviseur strict d tel que \(1 < d < {n_1}\). Comme \(d|n_1\) et \(n_1|n\) alors \(d|n\) et donc \(d\) est un diviseur strict de \(n\) plus petit que \(n_1\) ce qui contredit le fait que \(n_1\) est le plus petit.
    Donc \(n_1\) est premier et donc \(n\) admet un diviseur premier.

Autre démonstration :
Soit \(n\) un entier naturel avec \(n\)\( \ge \)2.
Soit \(\mathbb{E}\) l’ensemble des diviseurs de \(n\) qui sont supérieurs ou égaux à 2. Comme \(n \in \mathbb{E}\), alors \(\mathbb{E}\) est non vide. Comme toute partie non vide de \(\mathbb{N}\) admet un plus petit élément, l’ensemble \(\mathbb{E}\) admet un plus petit élément que l’on note \(p\).

Comme \(p \in \mathbb{E}\) alors \(p\) divise \(n\) et comme \(p \in \mathbb{E}\) alors \(p\)\( \ge \)2.

Si \(n\) est premier, le diviseur premier \(p\) de \(n\) n’est autre que \(n\) lui-même.
Si \(n\) n’est pas premier, raisonnons par l’absurde en supposant que \(p\) n’est pas premier. Dans ce cas, \(p\) admet un autre diviseur que 1 et \(p\) que l’on note \(d\) ; ainsi \(d\)\( \ge \)2 (car \(d\)\( \ne \)1) et \(d\)<\(p\) (car \(d\)\( \ne \)\(p\)).
Or, \(d\left| p \right.\) et \(p\left| n \right.\) donc \(d\left| n \right.\) et comme \(d\) est un diviseur de \(n\) plus grand que 2, il est dans \(\mathbb{E}\), ce qui est absurde car cela contredit la minimalité.

Conclusion : \(p\) est premier et donc il existe une nombre premier qui divise \(n\).

2°) Le crible d’Ératosthène ; test de primalité.

Théorème n°1:   Soit \(n\) un entier naturel avec \(n\)\( \ge \)2.
Si \(n\) n’admet aucun diviseur premier \(p\) tel que \(p\)2\( \le \)\(n\), alors \(n\) est un nombre premier.

Démonstration :
Raisonnons par contraposée, en supposant que \(n\) (\( \ge \)2) \(n\)’est pas premier. Ainsi, \(n\) admet un diviseur premier \(p\) tel que \(n = p \times q\) avec \(1 < p \le q\) car \(p\) est le plus petit diviseur premier de \(n\). Comme \(1 < p < q\) alors \({p^2} \le pq\) c’est-à-dire \({p^2} \le n\) donc \(p \le \sqrt n \)

Exemple : 167 est-il un nombre premier ?
On cherche un carré parfait juste au dessus de 167, on a 132=169.
On regarde si 167 est divisible par les nombres premiers strictement inférieurs à 13 : 2, 3, 5, 7, 11. Aucun ne divise 167, donc 167 est un nombre premier.

Remarque : 
Ce théorème justifie le crible d’Ératosthène. On élimine tous les nombres premiers déjà connus et on s’arrête dès que l’on dépasse \(\sqrt n \). Ici \(n = 100\) donc \(\sqrt n  = 10\).

Exercice :
Soit \(n\) un entier naturel supérieur ou égal à 3. On pose \(a = {n^2} – 2n – 3\). Existe-t-il des valeurs de \(n\) telles que \(a\) soit un entier naturel premier ?
Les racines du polynôme \({X^2} – 2X – 3\) sont \(X\)=-1 et \(X\)=3. Une factorisation dans \(\mathbb{N}\) est alors \(a = \left( {n + 1} \right)\left( {n – 3} \right)\).
Or \(n + 1 \ge 2\) pour \(n\)\( \ge \)1 et \(n – 3 \ge 2\) pour \(n\)\( \ge \)5 donc \(a\) est le produit de deux entiers supérieurs ou égaux à 2 et ne peut donc être premier.
Regardons les cas où \(n\)=3 et \(n\)=4.
Si \(n\)=3, on a \(a\)=0 et donc \(a\) n’est pas premier.
Si \(n\)=4, alors \(a\)=5 et \(a\) est premier.

3°) L’infinitude des nombres premiers.

Corollaire :
L’ensemble \(\wp \) des nombres premiers est infini.

Démonstration :
Par l’absurde comme préconisée dans le programme.
Supposons que l’ensemble \(\wp \) des nombres premiers est fini et soit alors \(\wp \)={\(p_1p_2…p_n \)} la liste des nombres premiers. Posons \(N \)=\(p_1p_2…p_n +1 \) un entier naturel, on a : \(N \)\( \ge \)2 donc, \(N \) admet un diviseur premier \(p_i\) qui est dans la liste.
Ainsi, \({p_i}\left| N \right.\) et \({p_i}\left| {\left( {{p_1} \times {p_2} \times  \cdots  \times {p_n}} \right)} \right.\) donc \({p_i}\left| {\left[ {N – \left( {{p_1} \times {p_2} \times  \cdots  \times {p_n}} \right)} \right]} \right.\) c’est à dire que donc \(p\)\( \le \)1 ce qui est absurde pour un nombre premier.
Conclusion : \(N\) est un entier qui n’est pas divisible par l’un des nombres premiers \(p_i\) de la liste, donc d’après la proposition sur l’existence des nombres premiers, il est premier ou possède un diviseur premier qui n’est pas dans la liste ; dans les deux cas, cette liste n’est pas finie.

II – Décomposition d’un entier naturel en produit de facteurs premiers.

1°) Le théorème fondamental de l’arithmétique.

Théorème : (théorème fondamental de l’arithmétique)(ROC)
Tout entier naturel \(n\)\( \ge \)2 est premier ou se décompose en un produit de facteurs premiers.
Cette décomposition est unique à l’ordre près des facteurs.

Démonstration : (ROC)

  • Si \(n\) est premier, la propriété est établie.
  • Si \(n\) n’est pas premier, alors son plus petit diviseur \(n_1\)\( \ge \)2 est premier et donc il existe un entier naturel \(q\) tel que \(n = {n_1} \times q\) avec \(1 < q < n\)  (avec \(q \ne 1\) car sinon \(n_1\)=\(n\) ce qui entraîne \(n\) premier puisque \(n_1\) l’est, ce qui est absurde).
    • Si \(q\) est premier alors \(n = {n_1} \times q\) et la propriété est établie.
    • Si \(q\) n’est pas premier, alors son plus petit diviseur \(q_1\)\( \ge \)2 est premier et il existe un entier naturel \(q_2\) tel que \(q=q_1q_2\) avec 1 < \(q_2\) <\(q\) et donc \(n\)=\(n_1\)\(q_1\)\(q_2\)
      On réitère le processus avec \(q_2\). Ainsi, on construit une suite d’entiers \(q_i\) strictement décroissante (les quotients successifs sont de plus en plus petits) \(1 \le  \cdots  < {q_i} <  \cdots  < {q_2} < {q_1}\) Cette suite est finie et le dernier d’entre eux est nécessairement premier (sinon on continuerait), donc \(n = {n_1}{q_1}{q_2}{q_3} \cdots {q_k}\) avec les \(q_i\) premiers.
      Comme ces \(q_i\) ne sont pas forcément distincts, on peut les regrouper.

D’où tout entier \(n\) s’écrit sous la forme \(n = p^{\alpha _1}_1p^{\alpha _2}_2…p^{\alpha _k}_k \) où les \(p_i\) sont premiers avec \(p_1 < p_2 < … < p_k \) et \(\alpha_i\) entiers naturels.

2°) Application de la décomposition en produit de facteurs premiers pour déterminer tous les diviseurs d’un entier naturel.

a – Détermination des diviseurs à l’aide de la décomposition en produit de facteurs premiers.

Théorème :
Soit \(n\) et \(d\) deux entiers naturels avec \(d\) non nul.
\(d\) est un diviseur de \(n\) si et seulement si la décomposition en produit de facteurs premiers de \(d\) ne comporte que des diviseurs premiers de \(n\), chacun d’eux étant élevé à une puissance inférieure ou égale à la puissance correspondante de ce facteur dans la décomposition de \(n\).

Exemple :
Effectuons la décomposition en produit de facteurs premiers de 735.

IMAGE
Ainsi, les diviseurs de 735 sont tous les nombres de la forme \(d\)=3a.5b.7c

où \(a\), \(b\) et \(c\) sont des entiers naturels tels que 0\( \le \)\( a\)\( \le \)1, 0\( \le \)\( b\)\( \le \)1  et 0\( \le \)\( c \)\( \le \)2.

b – Nombre de diviseurs d’un entier naturel.

Exemple :
Faisons le avec 735.
On construit alors un arbre :

IMAGE

Le nombre de diviseurs de 735 est 2.2.3=12.

Théorème.
Soit \(n\) un entier naturel avec \(n\)\( \ge \)2.
Si la décomposition en facteurs premiers de \(n\) s’écrit \(n = p^{\alpha _1}_1p^{\alpha _2}_2…p^{\alpha _k}_k \) alors le nombre de diviseurs de \(n\) est \(({\alpha _1} + 1)({\alpha _2} + 1)…({\alpha _k} + 1)\).

Exemple :
On a 4536= donc le nombre de diviseurs de 4536 est (3+1)(4+1)(1+1)=40

c – Utilisation de la décomposition en produit de facteurs premiers pour déterminer le \(PGCD\).

Théorème :
Soit \( a\) et \( b\) deux entiers naturels dont l’un des deux au moins est non nul.
Le \( PGCD\) de \( a\) et \( b\) est le produit de tous les facteurs premiers communs aux décompositions de \( a\) et \( b\), chacun de ces facteurs étant élevé à la plus petite des puissances de ce facteur dans chacune des décompositions de \( a\) et de \( b\).

Exemple :
\( PGCD\)(24,140) :
On a 24 = 23.3 et 140 = 22.5.7 d’où \( PGCD\)(24,140)=2.
\( PGCD\)(4536 ;4851) :
On a 4536 = 23.34.7 et 4851 = 3².72.11 d’où \( PGCD\)(4536 ;4851) = 3².7 = 63 .
Le nombre de diviseurs de 4536 est (3+1)(4+1)(1+1)=40, le nombre de diviseurs de 4851 est (2+1)(2+1)(1+1)=18.
On observera que ce n’est pas le nombre le plus grand qui a nécessairement le plus grand nombre de diviseurs.

III – Nombres premiers et divisibilité dans \(\mathbb{N}\).

1°) Divisibilité par un nombre premier.

Proposition :
Soit \(p\) un nombre premier et \(n\) un entier naturel non divisible par \(p\) ; alors \(p\) et \(n\) sont premiers entre eux.

Démonstration :
\(p\) est premier d’où \(Div\)\(\mathbb{N}\)(\(p\))={1,\(p\)} et \(Div\)\(\mathbb{N}\)(\(n\))={1,…,\(n\)}. Puisque \(p\) ne divise pas \(n\) alors \(p\) \( \notin \) \(Div\)\(\mathbb{N}\)(\(n\)) d’où \(Div\)\(\mathbb{N}\)(\(p) \cap Div\)\(\mathbb{N}\)(\(n\)) donc \(p\) et \(n\) sont premiers entre eux.

Théorème :
Soit \(p\)\( \in \)\(\wp \).

  1. Si [(\(a\),\(b\))\( \in \)\(\mathbb{N}\)² et \(p|ab\)] alors [\(p|a\) ou \(p|b\)].
  2. Si [(\(a\),\(b\))\( \in \)\(\wp \)² et \(p|ab\)] alors [\(p\)=\(a\) ou \(p\)=\(b\)].

Démonstration :

  1. Si \(p\)|\(a\) le résultat est évident \(p\)|\(a\) donc [\(p\)|\(a\) ou \(p\)|\(b\)].
    si \(p\) ne divise pas \(a\) alors \(PGCD\)(\(a\);\(p\))=1 puisque les diviseurs de \(p\) sont 1 et \(p\) donc \(p\) est premier avec \( a\) et d’après le théorème de Gauss : \(p\)|\( b\).
  2. Si \(p\)|\( ab\) alors d’après 1. [\(p\)|\( a\) ou \(p\)|\( b\)] ; mais (\(a\),\(b\))\( \in \)\(\wp \)² donc \(a \wedge b\) = 1 . Or \( a\) et \( b\) étant premiers entre eux et \(p\) premier (donc différent de 1) alors \(p\) =\( a\) ou \(p\) =\( b\).

2°) Le petit théorème de Fermat.

Le résultat suivant dû à Pierre de Fermat donne une condition nécessaire pour qu’un nombre \(p\) soit premier.
Il permet aussi d’analyser la décomposition en produit de facteurs premiers.

Petit théorème de Fermat :
Soit \(p\) un nombre premier et \(a\) un entier naturel non nul alors \(a^p\)\( \equiv \) \(a\) [\(p\)]
Et le corollaire, si de plus \(p\) ne divise pas \(a\) alors \(a^{p-1}\)\( \equiv \) \(1\) [\(p\)].

Exemples :
Prenons \(p\)=3 (qui est premier) et \(a\)=5. On a \(5^3 – 5\) qui est divisible par 3.

Démonstration :
Si \(p\) n’est pas premier avec \(p\), comme \(p\) est un nombre premier, alors \(a\) est un multiple de \(p\), donc \(p\) et \(v\) ont le même reste nul dans la division par \(p\) donc \(a^p\)\( \equiv \)\(a\)[\(p\)].
Si \(a\) est premier avec \(p\) alors \(a\)  n’est pas un multiple de \(p\). Démontrons le résultat suivant : \((a+1)^p\)\( \equiv \)\(a^p + 1\)[\(p\)]

La formule du binôme de Newton donne

=

newton

ce qui équivaut à :                                      .

Nombres Premiers - Tauziede

Montrons que .

D’après la formule de combinatoire sur les combinaisons, pour , on a :

donc .

La dernière équation implique que \(p\)|.

Or \(p\) est premier avec k ! donc d’après le théorème de Gauss \(p\)| .

Ainsi, \(p\) divise  par conséquent,

d’où .

Il reste à démontrer par récurrence sur l’entier naturel a que  en utilisant la relation précédente.

(La relation de récurrence ne peut être faite sur \(p\), en effet si \(p\) est premier l’entier suivant  n’est pas forcément premier (sauf si \(p\)=2, mais après ce n’est plus possible).

Au rang a=1, on a pour tout \(p\) premier :  et  donc pour tout entier \(p\) premier  ce qui prouve la relation au rang (a=) 1.

Supposons que pour un entier non nul a fixé dans \(\mathbb{N}\), et démontrons que la relation est vraie au rang suivant c’est à dire que  [\(p\)].

On a  [\(p\)] puisque \(p\) est premier. Or par hypothèse de récurrence, donc  donc  [\(p\)] ce qui prouve la relation au rang a+1. D’après le principe de récurrence :

Pour tout entier naturel a non nul et tout entier premier \(p\) ne divisant pas a : .

Par suite si \(p\) ne divise pas a alors et donc .

Exemple :
Soit \(n\) un entier naturel supérieur ou égal à 2. On considère l’entier naturel .

  • Démontrer que a est divisible par .
  • Démontrer que a est divisible par 30.
  • puisque n2+1 est un entier naturel cela entraîne que a est divisible par .
  • 5 est un nombre premier, donc d’après un conséquence du petit théorème de Fermat, 5 divise d’où .

De même 3 est un nombre premier donc 3 divise  d’où .

Par conséquent, d’après a), 3 divise .

De même 2 est premier donc 2 divise  donc divise  donc divise .

Conclusion : 2 divise a, 6 et 5 sont premiers entre eux donc 30 divise a.