Décomposition en produit de facteurs premiers

En mathématiques et plus précisément en arithmétique, la décomposition en produit de facteurs premiers, aussi connue comme la factorisation entière en nombres premiers, consiste à chercher à écrire un entier naturel non nul sous forme d'un produit de nombres premiers. Par exemple, si le nombre donné est 45, la factorisation en nombres premiers est 32 × 5, soit 3 × 3 × 5.

Par définition, un nombre premier ne peut pas être décomposé en produit de plusieurs nombres premiers. On peut aussi dire qu'il est sa propre décomposition. Quant au nombre 1, c'est le produit vide[1].

5 = 5
25 = 5 × 5 = 52
125 = 5 × 5 × 5 = 53
360 = 2 × 2 × 2 × 3 × 3 × 5 = 23 × 32 × 5
1 001 = 7 × 11 × 13
1 010 021 = 17 × 19 × 53 × 59

La factorisation est toujours unique, en accord avec le théorème fondamental de l'arithmétique. L'écriture des nombres entiers en produits de facteurs premiers en facilite la manipulation dans des problèmes de divisibilité, de fraction ou de racine carrée.

La recherche d'algorithmes de décomposition est d'une importance considérable en mathématiques, en cryptologie, en théorie de la complexité des algorithmes, et pour les calculateurs quantiques.

Décomposition en produit de nombres premiers

Le théorème fondamental de l'arithmétique permet d'affirmer que tout entier strictement positif possède une décomposition en facteurs premiers. C'est-à-dire qu'il peut s'écrire de manière unique comme le produit fini de nombres premiers à une puissance adéquate.

Pour tout nombre entier naturel n supérieur ou égal à 1[2], il existe une suite finie unique (p1, k1) … (pr, kr) telle que :

  1. les pi sont des nombres premiers tels que, si i < j, alors pi < pj ;
  2. les ki sont des entiers naturels non nuls ;
  3. n est le produit des nombres piki.

Une définition plus formelle de la décomposition en facteurs premiers fait appel à la notion de valuation p-adique.

Pour tout nombre premier p et tout entier naturel n non nul, on détermine le plus grand entier naturel k tel que pk divise n. Cet entier se note vp(n) et s'appelle valuation p-adique de l'entier n.

Ainsi vp(1) = 0 pour tout nombre premier p, v3(45) = 2 et v5(45) = 1.

Si l'on note alors l'ensemble de tous les nombres premiers, tout entier naturel non nul n peut s'écrire sous la forme du produit

Les vp(n) étant nuls sauf un nombre fini d'entre eux, ce produit infini est en fait un produit fini. Cette écriture est unique, c'est-à-dire que, s'il existe une famille d'entiers naturels, tous nuls sauf un nombre fini d'entre eux, telle que

alors pour tout p, . On appelle alors cette écriture la décomposition de n en produit de facteurs premiers.

Dans d'autres langues