Cliquez pour afficher

Je propose l'algorithme suivant (avec k entier quelconque, pas forcément une factorielle):
Ecrivons sous forme de son développement en facteurs premiers:

Prenons son plus grand facteur premier
-Si est impair, alors prenons comme facteur de ou de . Si est entier, reprendre l'algorithme avec ce nombre. Sinon, la décomposition est impossible.
-Sinon si est pair , écrivons ou   et sont impairs et prenons et comme facteur l'un de et l'un de . Si est entier, reprendre l'algorithme avec ce nombre. Sinon, la décomposition est impossible.
S'arrêter lorsque l'on atteint 1.

Démonstration:
remarque:
------------------------------------------------------------------------------------------------------------
Pour qu'un facteur premier apparaisse dans la décomposition de A, il faut qu'il apparaisse dans la décomposition de n (ou de m). s'il est dans la décomposition de avec une multiplicité , il apparaitra dans avec une multiplicité (au moins, voir plus bas), et donc avec une multiplicité dans A (au moins, voir plus bas et aussi si apparait dans la décomposition de )
Une autre manière pour qu'un facteur apparaisse est qu'il existe un nombre premier dans la décomposition de et tel que divise .
------------------------------------------------------------------------------------------------------------

Si est impair, apparait forcément comme facteur de ou de .
En effet, si ce n'est pas le cas:
            si apparait avec une multiplicité strictement supérieure à dans ou , il apparaitra trop de fois dans la décomposition de A.
            Sinon, il existe un autre nombre premier dans la factorisation de ou tel que divise :
                        Si il apparait avec une multiplicité strictement inférieure à dans ou (pas dans les deux), il n'apparaitra  pas assez de fois dans la décomposition de . et devra donc apparaitre dans la décomposition de une fois supplémentaire.
                        Si il apparait à la fois dans les décompositions de et de , il apparaitra un nombre pair de fois dans la décomposition de A, à moins qu'il n'apparaisse une fois supplémentaire dans la décomposition de  
Or on avait supposé que était le plus grand facteur premier. Or est supérieur à ce qui est absurde.

Donc dans le cas ou est impair, on n'a pas le choix d'avoir , dans la décomposition de ou de

- Si est pair, même raisonnement, les seuls choix possibles sont ceux décrits par l'algorithme.