ChronoMath, une chronologie des MATHÉMATIQUES
à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges
 

Décomposition d'un entier naturel en produit de facteurs premiers

Ce résultat fondamental d'arithmétique fit l'objet des propositions XXXIII et XXXIV des Éléments d'Euclide. Mais il est parfois appelé théorème d'Al-Farisi en l'honneur du mathématicien perse (1260-1320) à qui l'on doit sa première démonstration en termes "modernes" :

Tout entier naturel n admet une unique factorisation de la forme n = p₁^α × p₂^β × ... × p_k^γ
où p₁, p₂,..., p_k sont les diviseurs premiers de n et α, β, γ, ... des entiers non nuls.

Par exemple : 1400 =  2³ × 5² × 7.

Preuve :     

On sait (ou on apprendra) que tout entier naturel n autre que 0 ou 1 possède au moins un diviseur premier p₁ ne pouvant excéder sa racine carrée. Notre entier peut donc s'écrire :

n = k₁ × p₁, k₁ entier

Si k₁ est également divisible par p₁, alors n = k₂ × p₁², etc. Finalement :

n = k_α × p₁^α, p₁ ne divisant pas k_α

Si  k_α = 1, le théorème est validé pour notre entier n. Sinon k_α est au moins égal à 2 et on peut lui appliquer l'algorithme précédent à k_α. On obtiendra le résultat attendu au bout d'un nombre fini d'opérations.

Programmation :   

Le programme ci-dessous applique l'algorithme en cherchant à diviser le nombre donné n par 2 tant que faire se peut, ce qui élimine tous les diviseurs pairs en construisant éventuellement le diviseur du type 2^α. On procède de même avec 3, ce qui élimine les multiples de 3, puis par 6a ± 1 (condition nécessaire de primarité) pour a décrivant N.

La démarche est semblable au Crible d'Ératosthène. Si un diviseur de cette forme est trouvé, c'est un diviseur premier car tous ses diviseurs éventuels ont été éliminés auparavant.

• Par exemple, le cas a = 6 fournit 6a + 1 = 37 qui est premier et 6a - 1 = 35 = 5 × 7. Ce n'est pas un nombre premier mais il ne peut diviser le nombre résultant des divisions précédentes par 5 et 7 qui ont déjà été essayés pour a = 1.