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-Farasi 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 = p1αp2β...pkγ
où p1, p2,..., pk sont les diviseurs premiers de n et α, β, γ, ... des entiers non nuls.

Par exemple : 1400 =  23527.

Preuve :     

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

n = k1p1, k1 entier

Si k1 est également divisible par p1, alors n = k2p12, etc. Finalement :

n = kαp1α, p1 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.

                  

PGCD :         Nombre de diviseurs d'un entier :         JavaScript :


© Serge Mehl - www.chronomath.com