2.1.2.2 Calcul du pgcd et du ppcm : décomposition en facteurs premiers

Définition 2.1.3

Un nombre $p \in {\mathbb{N}}$, $p \not= 1$, est dit premier s'il n'admet comme diviseur positif que lui-même et 1.

La proposition suivante permet de déterminer les nombres premiers inférieurs à un entier donné. Elle nous servira à écrire un programme pour déterminer ces nombres. Mais il n'y a pas de « formule(s) » déterminant tous les nombres premiers.

Proposition 2.1.2
$p$ est premier SSI il n'a pas de diviseur $q$ premier tel que $1 < q^2 \leqslant p$.

Démonstration :

Si $p$ n'est pas premier $p=nm$ ($n >1$ et $m>1$). Si $n^2 > p$ et $m^2 >p$, alors $n^2m^2 > p^2$, ce qui est impossible ; donc $1 < n^2 \leqslant p$ ou $1 < m^2 \leqslant p$. Si $n$ et $m$ ne sont pas premiers, on recommence : on trouvera un diviseur $q$ premier tel que $1 < q^2 \leqslant p$.

C.Q.F.D.

Exemple d'application :

Pour voir que 107 est premier, il suffit de s'assurer qu'il n'est pas divisible par 2, 3, 5 ou 7, car le nombre premier suivant, 11, vérifie $11^2 =121 > 107$.

Théorème 2.1.7 (admis)
Soit $n \in {\mathbb{Z}}$. Alors $n=\pm p_1^{k_1}p_2^{k_2}\dots p_r^{k_r}$, où $p_1,p_2,\dots,p_r$ sont premiers. Cette décomposition est unique à l'ordre près des facteurs.

Si $n=\pm p_1^{k_1}p_2^{k_2}\dots p_r^{k_r}$ et $m=\pm q_1^{l_1}q_2^{l_2}\dots q_s^{l_s}$ sont les décompositions de $n$ et $m$ en facteurs premiers, leur pgcd est le produit des facteurs premiers communs ; leur ppcm est le produit de tous les facteurs premiers des deux décompositions, chaque facteur commun n'étant compté qu'une seule fois.

Exercice 2..10
Calculer le pgcd et le ppcm de $1 697 850$ et de $1 086 085$ par les deux méthodes.