Nombres premiers

Aujourd'hui des programmes performants peuvent décider en quelques minutes si un nombre d'une centaine de chiffres est premier ou non. Par contre on ne sait pas en un temps raisonnable en faire la décomposition : les algorithmes de cryptage reposent là-dessus.

On va faire une démonstration par récurrence utilisant la forme forte du principe d'induction.

--- Énoncé de la propriété \(P(n) :\) Le nombre entier positif \(n\) supérieur ou égal à 2 admet une décomposition en produit de facteurs premiers.

--- Initialisation : le nombre 2 admet de façon évidente une décomposition en produit de facteurs premiers puisqu'il est un nombre premier : \(P(2)\) est vraie.

--- Hérédité de la propriété : Supposons que \(P(k)\) est vraie c'est-à-dire que \(k\) se décompose en produit de facteurs premiers pour tout entier \(k, 2 \leq k \leq a - 1.\) On veut montrer que \(P(a)\) est vraie, c'est-à-dire que \(a\) se décompose en produit de facteurs premiers. On constate qu'il y a deux cas, suivant que a est premier ou non.

\(a\) est un nombre premier

C'est fini, \(a\) a une décomposition évidente en produit de facteurs premiers.

\(a\) n'est pas un nombre premier

\(a = a_1 a_2, 1 < a_1 < a\) et \(1 < a_2 < a.\) On peut appliquer l'hypothèse de récurrence à \(a_1\) et \(a_2,\) qui se décomposent en produit de facteurs premiers, donc \(a\) se décompose aussi de la même façon.

Donc \(P(a)\) est vraie si \(P(k)\) est vraie pour tout entier \(2 \leq k \leq a - 1\)

--- Conclusion : lorsque la propriété est vraie pour tout nombre entier positif de \(2\) à \(a - 1,\) elle est vraie aussi pour \(a.\) Comme elle est vraie pour 2, elle est donc vraie pour tous les entiers supérieurs ou égaux à 2.

On va encore faire une démonstration par récurrence utilisant la forme forte du principe d'induction.

--- Énoncé de la propriété \(P(n) :\) Le nombre entier \(n\) positif supérieur ou égal à 2 n'admet qu'une unique décomposition en produit de facteurs premiers, (à l'ordre des facteurs près).

--- Initialisation : de façon évidente, le nombre 2 n'admet qu'une décomposition en produit de facteurs premiers puisqu'il est un nombre premier : \(P(2)\) est vraie.

--- Hérédité de la propriété : On suppose que cette unicité ait été montrée pour tous les entiers de \(2\) à \(a - 1.\) On va montrer cette unicité pour l'entier \(a.\) On suppose que l'entier \(a\) ait deux décompositions :

\(a = p_1 ^{\alpha 1} p_2 ^{\alpha 2}... p_n ^{\alpha n}= q_1^{\beta 1}q_2 ^{\beta 2}... q_r ^{\beta r}\)

avec les \(p_i\) premiers distincts et les \(q_i\) premiers distincts, que l'on suppose rangés en ordre croissant.

\(p_1< p_2< ... <p_n \quad \textrm {et} \quad q_1< q_2< ... <q_r\)

On veut montrer que \(p1 = q1.\) Sinon, on suppose que \(p1<q1.\) Alors \(p_1\) est distinct de chacun des \(q_i.\) D'après les propriétés montrées précédemment, si \(p_1\) et \(q_i\) sont des nombres premiers distincts, \(p_1\) est premier avec toute puissance \(q_i ^{\beta i}\) de \(q_i,\) et est donc premier avec leur produit. Or \(p_1\) divise \(q_1 ^\beta q_2 ^\beta ... q_r ^\beta ,\) ce qui est contradictoire. On a donc \(p_1=q_1.\) Alors on simplifie l'égalité

\(a = p_1 ^{\alpha 1} p_2 ^{\alpha 2}... p_n ^{\alpha n}= q_1^{\beta 1}q_2 ^{\beta 2}... q_r ^{\beta r}\)

par \(p_1\) et on applique l'hypothèse de récurrence au nombre \(a'\) inférieur à \(a,\) défini par \(a = a'p_1.\)

\(a' = p_1 ^{\alpha 1-1} p_2 ^{\alpha 2}... p_n ^{\alpha n}= p_1^{\beta 1-1}q_2 ^{\beta 2}... q_r ^{\beta r}\)

Ce nombre \(a'\) admet une unique décomposition en facteurs premiers. Donc les nombres premiers qui figurent dans les deux décompositions sont les mêmes, avec les mêmes exposants.

--- Conclusion : Comme l'unicité de la décomposition est vraie pour 2, parce qu'on sait que si elle est vraie pour tous les entiers de 2 à \(a - 1,\) elle est vraie aussi pour \(a,\) on en conclut que la décomposition en facteurs premiers est unique pour tous les entiers supérieurs ou égaux à 2.