Nombres premiers et factorisation première 

Généralités

Un nombre premier est un entier naturel qui admet exactement deux diviseurs distincts entiers et positifs (qui sont  1 et lui-même).

Les nombres premiers sont : 2, 3, 5, 7, 11, 13, 17, 19…

Remarques : 1 n’est pas un nombre premier car il n'a qu'un seul diviseur entier positif ; 0 n’est pas un nombre premier car il est divisible par tous les entiers positifs.

Le théorème fondamental de l'arithmétique assure qu'un nombre composé est factorisable en un produit de nombres premiers, et que cette factorisation est unique à l'ordre des facteurs près.

Ce théorème permet de déterminer des notions de pgcd (plus grand commun diviseur), ppcm (plus petit commun multiple), et de nombres premiers entre eux, qui sont utiles pour la résolution de certaines équations diophantiennes, notamment la caractérisation des triplets pythagoriciens.

Comment décomposer en produit de facteurs premiers ?

Pour trouver les facteurs premiers d'un nombre n, on balaye la liste des nombres premiers en testant si le nombre premier p divise n. Si oui, on recommence pour le nombre  n/p, en ne testant que les diviseurs premiers encore envisageables...

Par exemple, pour trouver les facteurs premiers de 36 : 

Autre exemple, trouvons les facteurs premiers de 42.