DÉCOMPOSITION DES NOMBRES ENTIERS EN FACTEURS PREMIERS
89. Nous avons vu que tout nombre entier peut se décomposer, d'une manière et d'une seule, en un produit de nombre premiers (facteurs) qui sont distincts ou non. IN nus entendons par là qu'il y a une seule décomposition et non pas un moyen unique de l'obtenir.
Pour effectuer cette décomposition nous ne pouvons procélcr que par tâtonnement, et le moyen le plus simple qui se présente à nous est d'essayer successivement, sur le nombre à décomposer, les divers nombres premiers plus petits que lui, en commençant par les plus petits. Chaque fois qu'un essai réussit, on prend le quotient du nombre étudié par le nombre premier reconnu comme facteur de celo -ci, et l'on fait porter les essais suivants sur le nouveau Qooibre; de sorte que chaque essai qui réussit simplifie l'opération à deux points de vue, d'abord en donnant l'un d s facteurs cherchés, puis en reportant les autres essais sur un nombre moindre que le précédent.
Ceprocédéestfacileàjustifier: en effet, soit N =a.6.c..../ un produit de facteurs premiers, distincts ou non, et supposés rangés par ordre de grandeurs croissantes, c'est-àdire dans un ordre tel qu'aucun de ces nombres ne soit inférieur à ceux qui le précèdent. Lorsqu'on fera l'essai des
nombres 2, 3, 5, 7, , jusqu'à a, on ne rencontrera qu'un
essai qui réussisse, celui qui est relatif à a. Si alors on dé-
DâcO^OSmON D9S N0M3RBS BNTIBRS 155
signe par N' le quotient de N par a, on a N' s= b.e /, j|j
et Ton voit que pour obtenir les autres facteurs premiers ^
de N, il suffit de s'occuper du nouveau nombre N'; il est -'H
inutile d'ailleurs d'essayer sur ce nouveau nombre, N\ les ^
nombres premiers inférieurs à a, car si l'un d'eux divisait '%
N', il diviserait aussi N, qui est un multiple de N\ et ce V«
facteur eût été rencontré dans les essais que l'on a déjà |
faits sur N. Sur N' on doit essayer le nombre premier a, '1
car il peut appartenir plusieurs fois à N. On arrive ainsi, en *ï paiiant de *a, à un nouveau facteur premier 6, et l'on continue le même moyen d'opération, jusqu'à ce que le dei^ nier nombre obtenu N^*) soit reconnu premier.
Exemple. — Soit le nombre 3780 à décomposer en facteurs premiers. On dispose les résultats sur deux colonnes : dans une première colonne, celle de gauche, on écrit les uns au-dessous des autres les divers
nombres N, N,' N', , sur lesquels portent les
essais, et dans la seconde colonne, celle de droite, on met à côté de chacun des nombres précédents le facteur premier que l'on a essayé.
Le premier essai donne % et le quotient de 3780 par 2 est 1890, sur lequel 2 réussit encore; le nouveau quotient est 946 et le facteur premier 2 n'appartient plus à ce nombre. On essaie alors 3, qui réussit, et le nouveau quotient est 315, encore divisible par 3; et ainsi de suite. On est ainsi conduit à la décomposition :
L'imperfection théorique d'un pareil procédé est manifeste. On voit en effet que, môme en se bornant aux nombres usuels, il faudra une table de nombres premiers très étendue, et qu'un grand nombre d'essais peuvent être nécessaires à chaque fois. Ce procédé ne sera commode que pour les nombres ayant seulement des facteurs premiers très
simples. Prenons encore pour exemple le nombre 345499. Les facteurs premiers de : ce .nombre sont 7, 7, 11, 641. Jusqu'au nombre premier 11, les essais se font rapidement; mais pour reconnaître que 641 est premier, il faut déjà un assez grand nombre d'essais.
On peut être aidé, il est vrai, dans cette recherche, par la connaissance des caractères de divisibilité les plus simples, qui permettent de reconnaître presque immédiatement si un nombre est divisible par 2, par 3, par 5, 7 ou 11 ; mais au delà de 11, il faut faire la division à chaque fois.
90. Diviseurs d'un nombre entier. — L'une des premières applications qui se présentent est la recherche des diviseurs d'un nombre.
Pour cela, il faut d'abord savoir à quel caractère on reconnaît qu'un nombre B est diviseur d'un autre nombre
A. Or, si B est diviseur de A, on peut écrire A = B.C, G étant un certain nombre entier; on peut donc, pour décomposer A en facteurs premiers, suivre le procédé suivant : décomposer d'abord B et G séparément en leurs facteurs premiers, puis faire le produit de tous ces nombres. Il résulte de là que chaque facteur premier de B appartient à A, avec un exposant au moins égal à celui qu'il possède dans B.
Gette condition est d'ailleurs suffisante ; car, en écrivant A et B sous forme de produits de facteurs premiers, on a
A = a«ôPcT^ A,
a, 6, c, , / étant des nombres premiers, et a, p, y» •••••» ^
certains nombres entiers; de même
B = a«'ôP'cT^' A',
*»', P' y'» » ^' 6^2"^^ d^s nombres entiers non supérieurs à
B, P, Y» , X, et certains d'entre eux pouvant être nuls (car
DÉCOMPOSITION DBS NOMBRES RNTIERS 157
il n'est pas nécessaire que B contienne tous les facteurs de A). Il est visible alors que si Ton pose C = a«-a'*?-p'cT-r [k-v^ on a A = B . C,
égalité dans laquelle C désigne un nombre entier et qui montre bien que A est divisible par B.
On obtiendra donc tous les diviseurs de A en formant les divers nombres
B = a«'*P'cT' [k\
où Ton donne successivement à a' les valeurs 0, 1, 2, ...., a, à p' les valeurs 0, 1, 2, ...., p, etc.
Il y a deux diviseurs particuliers qui méritent d'être signalés; ce sont ceux qu'on obtient en donnant à a', p',
y, , X' la valeur 0, ou bien les valeurs «, p, fi i^- ^^
premier est égal à 1 (car nous avons vu qu'on doit toujours
prendre a^ = 1, b^ = 1, ); le second est le nombre
A lui-môme.
Pour former tous les diviseurs d'un nombre, il faudra donc combiner de toutes les façons possibles les diverses valeurs de a«' avec celles de b?\ puis les résultats avec les diverses valeurs de c^\ etc. A cet effet, on écrit dans un premier tableau les diverses valeurs de a*',
pois on les multiplie successivement par les diverses valeurs de 6P',
