French flag English flag
Index des cours

Les propriétés des nombres premiers

L'ensemble \(\mathbb{P}\) est l'ensemble des nombres premiers :

$$ \mathbb{P} = \Bigl \{2, 3, 5, 7, 11, 13, ...etc. \Bigr\}$$

On appelle nombre premier, un nombre \(p \in \mathbb{P}\) qui a uniquement comme diviseur lui-même et \(1\).

$$ \mathcal{D}(p) = \bigl\{p, 1 \bigr\} $$

De même, on dira que deux nombres \((a, b) \in \hspace{0.05em} \mathbb{Z}^2\) sont premiers entre eux si leur unique diviseur commun est \(1\).

$$ \mathcal{D}(a, b) = \bigl\{1 \bigr\} \hspace{0.2em} \Longleftrightarrow \hspace{0.2em} a \wedge b = 1 $$


Deux nombres premiers sont premiers entre eux

deux nombres premiers sont premiers entre eux.

$$ \forall (p_1, p_2) \in \hspace{0.05em} \mathbb{P}, $$

$$ (p_1, p_2) \in \hspace{0.05em} \mathbb{P} \Longrightarrow p_1 \wedge p_2 = 1$$


Décomposition d'un nombre en facteurs premiers

Tout entier naturel \(n \geqslant 2\) se décompose de manière unique en produit facteurs premiers.

$$ \forall n \in \mathbb{N}, \enspace n \geqslant 2, \enspace \forall i \in \mathbb{N}, \enspace (\forall p_i \in \mathbb{P}, \enspace \exists \alpha_i \in \mathbb{N}), $$

$$ n= p_1^{\alpha_1}p_2^{\alpha_2}...p_i^{\alpha_i}$$


Tout nombre supérieur à 2 possède au moins un diviseur premier

Tout entier naturel \(n \geqslant 2\) possède au moins un diviseur premier.


Tout nombre non premier supérieur à 4 possède au moins un diviseur strict

Tout entier naturel \(n \geqslant 4 \) non premier possède au moins un diviseur strict \(d_0 \) tel que \( d_0 \leqslant \sqrt{n} \).


Lien de primalité entre deux nombres

$$ \forall p \in \mathbb{P}, \enspace \forall a \in \mathbb{Z}, $$

$$ p \nmid a \hspace{0.2em} \Longleftrightarrow \hspace{0.2em} a \wedge p = 1 $$


Transmission du lien de primalité de deux nombres avec un autre même nombre par le produit

$$ \forall (a, b, n) \in \hspace{0.05em} \mathbb{Z}^3, $$

$$ \Biggl \{ \begin{align*} a \wedge n = 1 \\ b \wedge n = 1 \end{align*} \hspace{0.2em} \Longrightarrow \hspace{0.2em} ab \wedge n = 1 $$


Lemme d'Euclide

$$ \forall p \in \mathbb{P}, \enspace \forall (a, b) \in \hspace{0.05em} \mathbb{Z}^2, $$

$$ p/ab \hspace{0.2em} \Longrightarrow \hspace{0.2em} p/a \enspace ou \enspace p/b $$


Corollaire du lemme d'Euclide

$$ \forall (p, a, b) \in \hspace{0.05em} \mathbb{P}^3, $$

$$ p/ab \hspace{0.2em} \Longrightarrow \hspace{0.2em} p=a \enspace ou \enspace p=b $$


Démonstrations


Deux nombres premiers sont premiers entre eux

Soient \((p_1, p_2) \in \hspace{0.05em} \mathbb{P} \) deux nombres premiers.

Alors :

$$ \Biggl \{ \begin{align*} \mathcal{D}(p_1) = \bigl\{1, p_1 \bigr\} \\ \mathcal{D}(p_2) = \bigl\{1, p_2 \bigr\} \end{align*} $$

Leur seul diviseur commun est \( 1 \).

Alors,

$$ \forall (p_1, p_2) \in \hspace{0.05em} \mathbb{P}, $$

$$ (p_1, p_2) \in \hspace{0.05em} \mathbb{P} \Longrightarrow p_1 \wedge p_2 = 1$$

La réciproque n'est pas vraie.

Par exemple : \(16 \wedge 35 = 1\)

Et pourtant ces deux nombres ne sont pas premiers.


Décomposition d'un nombre en facteurs premiers

Soit \(n \in \mathbb{N}\) un entier naturel avec \(n \geqslant 2\).

Ce nombre admet un nombre fini de diviseurs.

  1. si \( n \) est premier
  2. Il n'y a qu'un seul facteur.

    $$ n= p_1^{\alpha_1} \enspace \enspace (avec \enspace \alpha_1 = 1) $$

  3. si \( n \) n'est pas premier
  4. On sait que \( n \) a au moins un diviseur premier.

    $$ n = n_1 p_1 $$

    1. - Si \( n_1 \) n'est pas premier
    2. On recommence :

      $$ n_1 = n_2 p_2 $$

      $$ n = p_1. n_2 p_2 $$

    3. - Si \( n_2 \) n'est pas premier
    4. On effectue cette procédure jusqu'au dernier diviseur qui sera nécessairement premier.


      On pourra éventuellement retomber sur les mêmes nombres premiers plusieurs fois de suite.

      $$ n= p_1^{\alpha_1}p_2^{\alpha_2}...p_i^{\alpha_i}$$


Soit finalement,

Tout entier naturel \(n \geqslant 2\) se décompose de manière unique en produit facteurs premiers.

$$ \forall n \in \mathbb{N}, \enspace n \geqslant 2, \enspace \forall i \in \mathbb{N}, \enspace (\forall p_i \in \mathbb{P}, \enspace \exists \alpha_i \in \mathbb{N}), $$

$$ n= p_1^{\alpha_1}p_2^{\alpha_2}...p_i^{\alpha_i}$$


Tout nombre supérieur à 2 possède au moins un diviseur premier

Soit \(n \in \mathbb{N}\) un entier naturel avec \(n \geqslant 2\).

Deux cas se présentent :

  1. \( n \) est premier
  2. Alors, \( n / n \).

    Il a bien au moins un diviseur premier.

  3. \( n \) n'est pas premier
  4. \( n \) possède au moins un diviseur strict.

    $$ \mathcal{D}(a) = \bigl\{1, d_1, d_2, \hspace{0.2em} ... \hspace{0.2em}, n \} $$

    Soit \( d_1 \) le plus petit diviseur strict de \(n \), \(d_1 \) est forcément premier, car s'il ne l'était pas, il aurait un diviseur inférieur à lui-même qui diviserait \( n \), et \( d_1 \) ne serait pas le plus petit diviseur de \(a \).


Soit finalement,

Tout entier naturel \(n \geqslant 2\) possède au moins un diviseur premier.


Tout nombre non premier supérieur à 4 possède au moins un diviseur strict

Soient \(n \in \{ \mathbb{N} \hspace{0.2em} \backslash\ \mathbb{P} \} \) un entier naturel non premier avec \(n \geqslant 4\), et \(d_0 \in \mathbb{N}\) un diviseur strict de \(n\).

Alors,

$$ \exists d' \geqslant d_0, \enspace n =d_0 d' $$

En multipliant par \(d_0 \) les deux membres,

$$ d_0^2 \leqslant d_0d' \Longleftrightarrow d_0^2 \leqslant n $$

$$ d_0 \leqslant \sqrt{n} $$


Et finalement,

Tout entier naturel \(n \geqslant 4 \) non premier possède au moins un diviseur strict \(d_0 \) tel que \( d_0 \leqslant \sqrt{n} \).


Lien de primalité entre deux nombres

Soient \( p \in \mathbb{P} \) un nombre premier et \(a \in \mathbb{Z} \) un entier relatif.

$$ \mathcal{D}(p) = \bigl\{p, 1 \bigr\} $$

$$ \mathcal{D}(a) = \bigl\{1, \hspace{0.2em} ... \hspace{0.2em}, a \} $$

Si \( p \nmid a \) alors \( p \not\in \mathcal{D}(a) \). D'où le fait que :

$$ p \nmid a \hspace{0.2em} \Longrightarrow \hspace{0.2em} \mathcal{D}(a) \wedge \mathcal{D}(p) = \bigl\{1 \bigr\} $$

$$ p \nmid a \hspace{0.2em} \Longrightarrow \hspace{0.2em} a \wedge p = 1 $$

Réciproque

Si \(a \wedge p = 1\), comme \(p\) divise uniquement \(1\) et lui-même, alors \(p \nmid a\).

$$ a \wedge p = 1 \hspace{0.2em} \Longrightarrow \hspace{0.2em} p \nmid a $$


Conclusion

$$ \forall p \in \mathbb{P}, \enspace \forall a \in \mathbb{Z}, $$

$$ p \nmid a \hspace{0.2em} \Longleftrightarrow \hspace{0.2em} a \wedge p = 1 $$


Transmission du lien de primalité de deux nombres avec un autre même nombre par le produit

Soient \( (a, b, n) \in \hspace{0.05em} \mathbb{Z}^3 \), trois entiers relatifs.

Le nombre \( n \) est premier avec \( a \) mais aussi avec \( b \).

$$ \Biggl \{ \begin{align*} a \wedge n = 1 \\ b \wedge n= 1 \end{align*} $$

Par le théorème de Bézout, on sait que :

$$ \forall (a, b) \in \hspace{0.05em}\mathbb{Z}^2, $$

$$ a \wedge b = 1 \Longrightarrow \exists (u, v) \in \hspace{0.05em}\mathbb{Z}^2, \enspace au + bv = 1 $$

On a alors le couple d'équations :

$$ \Biggl \{ \begin{align*} \exists (u, v) \in \hspace{0.05em}\mathbb{Z}^2, \enspace au + nv = 1 \qquad (1) \\ \exists (u', v') \in \hspace{0.05em}\mathbb{Z}^2, \enspace bu' + nv' = 1 \qquad (2) \end{align*} $$

En effectuant la multiplication \( (1) \times (2) \), on a :

$$ (au + nv)(bu' + nv') = 1$$

$$ aubu' + aunv' + nvbu' + nvnv' = 1$$

$$ ab \underbrace{(uu')} _\text{ \(U \in \hspace{0.05em} \mathbb{Z}\)} \hspace{0.1em} + n \underbrace{(auv' + vbu' + vnv')} _\text{ \(V \in \hspace{0.05em} \mathbb{Z}\)} \hspace{0.1em} + \hspace{0.1em} = 1$$

$$ ab U + nV = 1$$

D'après la réciproque du théorème de Bézout :

$$ ab \wedge n = 1 $$


Et finalement,

$$ \forall (a, b, n) \in \hspace{0.05em} \mathbb{Z}^3, $$

$$ \Biggl \{ \begin{align*} a \wedge n = 1 \\ b \wedge n = 1 \end{align*} \hspace{0.2em} \Longrightarrow \hspace{0.2em} ab \wedge n = 1 $$


Lemme d'Euclide

Soient \( p \in \mathbb{P} \) un nombre premier, \( (a, b) \in \hspace{0.1em} \mathbb{Z}^2 \) deux entiers relatifs.

Si \( p/ab \), alors deux cas se présentent :

  1. \( p \) divise \( a \)
  2. Alors, le théorème est vrai

  3. \( p \) ne divise pas \( a \)
  4. Alors, le lien de primalité entre deux nombres nous dit que comme \( p \nmid a\), alors \( a \wedge p = 1\).

    Or, avec le théorème de Gauss :

    $$ \forall (a, b, c) \in (\mathbb{Z})^3,\enspace a / bc \enspace et \enspace a \wedge b = 1 \hspace{0.2em} \Longrightarrow \hspace{0.2em} a/c $$

    Ce qui nous permet de dire que \( p \) divise \( b \).


Soit finalement,

$$ \forall p \in \mathbb{P}, \enspace \forall (a, b) \in \hspace{0.05em} \mathbb{Z}^2, $$

$$ p/ab \hspace{0.2em} \Longrightarrow \hspace{0.2em} p/a \enspace ou \enspace p/b $$


Corollaire du lemme d'Euclide

Soient \( (p, a, b) \in \hspace{0.1em} \mathbb{P}^3 \), trois nombres premiers.

Si \( p/ab \), on a vu plus haut qu'avec le lemme d'Euclide, on a :

$$ p/ab \hspace{0.2em} \Longrightarrow \hspace{0.2em} p/a \enspace ou \enspace p/b $$

Voyons ce qu'il se passe dans les deux cas.

  1. \( p \) divise \( a \)
  2. \( a \) est premier donc ses deux seuls diviseurs sont \( 1 \) et \( a \).

    Or, \( p \neq 1 \) par hypothèse car c'est un nombre premier, alors :

    $$ p/a \hspace{0.2em} \Longrightarrow \hspace{0.2em} p = a $$

  3. \( p \) divise \( b \)
  4. Ce sont les mêmes hypothèses pour \( b \), par conséquent :

    $$ p/b \hspace{0.2em} \Longrightarrow \hspace{0.2em} p = b $$


Soit finalement,

$$ \forall (p, a, b) \in \hspace{0.05em} \mathbb{P}^3, $$

$$ p/ab \hspace{0.2em} \Longrightarrow \hspace{0.2em} p=a \enspace ou \enspace p=b $$

Index des cours
Retour en haut de page