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…
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.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.