Décomposer un nombre donné en ses facteurs premiers

Le procédé le plus naturel pour résoudre cette question est d*essayer la division du nombre proposé, successivement par les nombres premiers 2, 3, 5 , 7, 11, etc. Ainsi on essayera d'abord de diviser le nombre proposé par 2 : si la division réussit/on essayera de diviser par 2 le quotient qu*on aura trouvé ; si cette seconde opération réussit, on essayera de diviser ce second quotient par 2, et ainsi de suite jusqu'à ce qu'on arrive à un quotieiit qui né soit plus divisible par 2. On essayera alors de le diviser par 3, et autant de fois de suite par 3 qu'il sera possible; on parviendra ainsi à un quotient qui ne sera plus divisible par 3 : on essayera de le diviser par 5 , et autant de fois de suite par 5 qu'on le pourra ; et l'on continuera ainsi jusqu'à ce qu'on arrive à un quotient qui soit un nombre premier, ce qui aura pécessairement lieu , sans quoi la décomposition dû nombre proposé en facteurs n'aurait pas de fin ; et ce nombre étant ainsi le produit d'une infinité de facteurs, tous plus grands que l'unité , serait par conséquent infini. On divisera le dernier quotient par lui-même, ce qui donnera pour résultat l'unité, et alors l'opération sei'a terminée.

Soit pour exemple le nombre 4725.

Ce nombre , étant impair^ n'est pas divisible par 2 , mais il l'est par 3, et le quotient de cette division est 1575, qui est encore divisible par 3. En effectuant cette division, on trouve pour quotient 525, nombre divisible par 3; le quotient de cette troisième division est 175, nombre qui n'est plus divisible par 3 , mais qui l'est par 5. Le quotient de 175 par 5 est 35, nombre

qui est encore divisible par 5 et donne pour quotient le nombre premier7.IIrésultedelàque4725=3.l575;que 1575=3.525,

donc 4725 = 3«. 525; que 525=3. 175, donc 4725 = 3». 175; que 175 = 5. 35, donc 4725 = 3*. 5. 35; enfin que, 35 étant le produit de 5 par 7, on aura 4725 = 3». 5*. 7. Ainsi, 4725 est le produit de 3 facteurs 3, de 2 facteurs 5 et du facteur 7.

Quoiqu'on n*ait essayé la division du nombre proposé par aucun facteur plus grand que le dernier de ceux que Ton a trouvés, on ne peut point craindre de n'avoir pas mis en évidence tous les facteurs premiers de ce nombre; car nous avons vu qu'un nombre ne peut être décomposé qu'en un seul système de facteurs premiers (88).

*80. Proposons-nous actuellement de former tout les diviseurs Sun nombre. >

Nous décomposerons d'abord ce nombre en ses facteurs premiers (88); et si Ton suppose, pour fixer les idées, qu'il ait été divisé p fois de suite par a, q fois de suite par 6, rfoisUe suite par c, son expression sera de la forme n = a". 6*. c*".

Cela posé, il en résultera que le nombre n sera divisible par toutes les puissances de a, de h, de c, depuis la première jusqu'à la p**"* pour a, jusqu'à la g""' pour 6, jusqu'à la r**"* pour c : de plus, comme ces différentes puissances de a, de 6 et de c sont premières entre elles deux à deux (83), le nombre n sera divisible par leurs produits deux à deux et trois à trois (84). D'ailleurs le nombre n n'aura pas d'autres diviseurs, en vertu du principe du n» 86. En conséquence, pour former tous les diviseurs du nombre n, on écrira sur trois lignes horizontales respectivement

1 et les puissances de a jusqu'à la p**""' ,

1 deb . . . . . g'*"S *

1 de c ..... r**"%

et Ton formera le produit des nombres contenus dans ces trois lio-nes, ce qui se fera en multipliant successivement tous les termes de la première par ceux de la seconde, puis tous les tiîrmes du produit par ceux de la troisième. Or le produit des

deux premières lignes se composera de 1, des puissances de a, des puissances de b, et des produits des puissances de a par celles de b. Maintenant on multipliera ce produit des deux premières lignes par la troisième, ce qui donnera : Tunité, les puissances de a, les puissances de &, les puissances de c, les produits des puissances de a par celles de b, les produits des puissances de a par celles de c, les produits des puissances de b par celles de c, et les produits des puissances de a par celles de b et par celles de c.

Nous aurons donc bien formé ainsi tous les diviseurs du nombre w.

*00. Dans la pratique, pour obtenir tou3 les diviseurs d'un nombre, on dispose les calculs de la manière suivante :

Les deux premières colonnes à gauche contiennent le tableau des calculs nécessaires pour trouver 1* facteurs premiers du nombre 4725 (88); la troisième colonne renferme tous les diviseurs tant simples que composés de 4725; pour les obtenir, on a écrit en tête de celte colonne le diviseur 1, on Fa multiplié par le premier facteur 3, et l'on a écrit le prod uit audessous de. ce diviseur 1 ; on a formé de même tous les autres diviseurs, en multipliant tous ceux déjà trouvés par le facteur premier suivant, et en ayant soin de ne pas écrire deux fois le même produit.

On voit que de cette manière on a formé : !• le diviseur 1 et toutes les puissances de 3 qui peuvent diviser 4725; îa- le diviseur 5 et toutes ses combinaisons avec les diverses puissances

de 3; 3* la deuxième puissance de 5 et ses combinaisons lavec les diverses puissances de 3; enfln, le diviseur 7 et ses combinaisons avec les diverses puissances de 3, avec les diverses puissances de 5, et avec les produits des diverses puissances de 3 par celles de 5 : donc on à bien formé ainsi tous les diviseurs tant simples que composes du nombre 4725 (89).

'91, Le nombre total des diviseurs d'un nombre (en y comprenant ce nombre et Vunitè) est égal au produit des exposants de ses facteurs premiers, augmentés chacun d*u>ne unité.

Nous avons vu qu'on pouvait former tous les divheurs d'un nombre n=a'. 6«. c', en effectuant le produit de trois lignes qui contiennent respectivement 1 et toutes les puissances ^ a jusqu'à bjo'*"', 1 et toutes les puissances de 6 jusqu'à lag'*°*% 1 et toutes les puissances de c jusqu'à la r'^*^ (89) : ainsi ces lignes se composent respectivement de (p -f 1), (^ + 1), (»• + 1) termes; donc en multipliant la première ligne par un terme quelconque de la seconde, le produit contiendra (p + 1) termes; donc, le produit des deux premières lignes renfermera autant de fois (p + 1) termes qu'il y en a dans la seconde, c'est-à-dire (P + ^)« (9 + 0* Maintenant, en multipliant le produit des deux premières lignes par un terme quelconque de la troisième, le produit contiendra fp + !)• {Q + 1) termes : donc le produit des trois lignes se composera d'autant de fois (p-f !)• (?+ 1) termes qu'il y a de termes dans la troisième ligne, c'est-à-dire de (r+1) fois (p+l).(g+lj termes, ou de (p+ I).(ç + l).(r+l) termes, ce qui démontre le principe énoncé.

Cette règle fournit le moyen de vérifier si, dans la formation des diviseurs d'un nombre (90), on n'en a omis aucun : ainsi le nombre 4725, qui égale 3'. 5*. 7, doit avoir un nombre de diviseurs égala (3+l).(2 + l).(l -f 1)=4.3.2 = 24, et c'est en effet ce que l'on a trouvé.

^ydW

2. Nous avons vu (86) que, pour qu^un nombre en divisé n autre, 11 faut qu'il ne contienne pas d'autres facteurs premiers que cet autre, et qu'il ne contienne pas les facteurs pre-

micrs de ce nombre à des puissances plus élevées que celui-ci ne les conlienl lui-même. Si doncnous^écomposons plusieurs nombres donnés en leurs facteurs premiers, et si nous faisons le produit de tous les facteurs premiers communs ainsi trouvés, en affectant chacun d'eux du plus petit exposant qu'il a dans ces nombres, ce produit sera le plus grand nombre qm Jes divise. Donc le plus grand commun diviseur de plusieurs nombres est le produit de tous leurs facteurs premiers communs affectés chacun du plus petit exposant qu'il a dans ces nombres.

Exemple. Quel est le plus grand commun diviseur de 7260 et de 5544? On trouvera : 1« que 7260= 2». 3. 5. 11*; 2» que 5544 = 2'. 3*. 7. 1 1 ; 3* que le plus grand commun diviseur demandé est 2\ 3. 11=132.

Il suit immédiatement de la composition du plus grand commun diviseur de deux nombres, qu'on n'altère pas ce plus grande commun diviseur en divisant ou en multipliant Fun d'eux par im facteur qui soit premier avec Vautre^ puisqu'en opérant ainsi on ne saurait supprimer ni introduire de facteur premier commun aux deux nombres proposés (85). Donc, lorsque l'on cherchera le plus grand commun diviseur de deux nombres par la méthode du n° 76, on pourra supprimer dans les restes successifs les facteurs que Ton y apercevra, pourvu qu'ils soient premiers avec le reste précédent, ce qui simplifiera les calculs.

On pourra encore diminuer le nombre des divisions successives en faisant en sorte que chaque reste soit moindre que la moitié du précédent. Il suffira pour cela de forcer Vunité (50) sur le quotient, lorsque le reste surpassera la moitié du diviseur; car alors la différence entre le dividende et le produit du diviseur par le nouveau quotient, étant celle môme qui existe entre le divisetir et le reste qu'on avait trouvé, sera moindre que la moitiéBu diviseur. Ainsi, dans l'exemple dun* 75, nous vivons vu que la division de 56 par 21 donnait 2 pour quotient ^ et 14 pour reste, de sorte que 56secomposede2fois21,p/u^l4. Gomme }4 surpasse la moitié de 21, nous écrirons 3 au quotient, et la différence entre le dividende 56 et le produit du

diviseur 21 par le quotient 3 sera 3 fois moins 2 fois 21 moins 14, c'est-à-dire 21— 14 = 7. Ce nombre 7 sera donc le diviseur de la division suivante; et comme elle réussit, 7 est le plus grand commun diviseur de 56 et de 21 .

Exemple. Trouver le plus grand commun diviseur entre

38449 et 24431 :

Le reste 14018 de la première dWsion surpassant la moitié du diviseur, on a forcé Tunité sur le quotient, ce qui a donné 10413 pour reste de cette première division; on a divisé ce nombre par 9, ce qui est permis, puisque 9 est premier Savec le diviseur 24431, et on a pris 1157 pour le second diviseur; de même on a divisé le reste 134 par 2, qui est premier avec 1157, Quant au troisième reste 18, il est évidemment premier avec le diviseur 67, puisque ni l'un ni l'autre de ses facteurs premiers 2 et 3 ne divise ce nombre : donc les deux nombres proposés sont premiers entre eux (77).

^93. Les deux problèmes que nous avons résolus aux n°' 88 t 80 sont d'une grande importance , et le premier va nous fournir le moyen' de trouver le plus petit nombre divisible à la fois par plusieurs nombres donnés^ question dont nous verrons biaitôt une application (i08).

Nous avons vu que, pour qu'un nombre soit divisible par un autre, il faut qu'il contienne tous les facteurs premiers de cet autre, et chacun autant de fois au moins que celui-ci les contient lui-même (87) : d'après cela , pour déterminer le plus petit nombre divisible par plusieurs nombres donnés y on décomposera chacun de ces nombres en ses facteurs premiers, et Von formera le produit de tou^ les facteurs premiers différents ainsi obtenus ^ '

en donnant à chacun d'eux le plus grand exposant dont il est affecté dans les nombres proposés.

Ainsi , pour trouver le plus petit nombre divisible à la fois par 90, 126 et 540, on verra d'abord (88) que 90=2.3*. 5, que 126 = 2.3*. 7, et que 540=2". 3*. 5. Par conséquent, le plus petit nombre divisible à la fois par 90, 126 et 540, est

On résout encore ce même problème par une autre méthode qui est plus commode lorsque Tun des nombres proposés a pour facteur premier un nombre considérable et que l'on n'a pas de Tables des nombres premiers. Considérons d'abord le cas de deux nombres seqlemcnt, et proposons-nous de trouver le plus petit nombre divisible à la fois par deux nombres donnés À et B.

Il est clair qu'en vertu du principe du n» 87 le nombre demandé doit renfermer tous les facteurs premiers de A et de B, et chacun d'eux à une puissance marquée par le plus grand exposant qu'il a dans ces nombres. On obtiendra donc le plus petit multiple de A et B en multipliant l'un deux, A par exemple, par le produit de tous les facteurs premiers de B qui ne se trouvent pas dans A *. En conséquence, on cherchera le plus grand commun diviseur de k et B; on divisera B par ce plus grand commun diviseur, et, en multipliant A par le quotietU B* de cette division, on obtiendra un produit A. B' qui résoudra le pro^ blême; car B' est le produit de tous les facteurs premiers de B qui ne se trouvent pas dans A (92).

En raisonnant de la même manière, on prouvera facilement que pour trouver le plu>s petit multiple des trois nombres A, B, G, il faut chercher le plus grand commun diviseur de k.B' et G, diviser G par ce pUis grand commun diviseur y et multiplier A. B' par le quotient G' de cette division » et ainsi de suite.

^ Si par exemple A = 2^3.5 et B = 2^3^7, il faudrait mul&plier À par 3-7.

PROPRIËTËS DES NOMBRES. 67

Exemple. Quel esl le plus petit nombre divisible par 1220, 555, 6771 et 83509 î On trouvera: l«»que le plus grand commun diviseur de 1220 et de 555 est 5, que %= 111, et qu'ainsi le plus petit multiple de 1220 et de 555 est 1220. 111 = 135420; 2» que le plus grand commun diviseur de 135420 et de 6771 est 6771 lui-même, et qu'ainsi 135420 est le plus petit multiple des nombres 1220, 555 et 6771; 3^ que le plus grand commun diviseur de 135420 et de 83509 est 2257, que 4^^=37, et qu'ainsi le nombre demandé est 135420. 37 = 5010540 *.

* On pourra faire ce calcul bien plus simplement, en observant que l'on peut obtenir le plus grand commun diviseur entre un nombre D et un produit de plusieurs facteurs A, B, G, sans effectuer ce produit ; mais quMl suffira, en vertu du principe du n" 03, de chercber le plus grand commua diviseur F entre le 1*' facteur A et le nombre D; celui F' entre le 2* facteur B et le quotient D' de la division de D par F; celui F'' entre le 3* facteur G et lé quotient D' de la division de D' par F', et de multiplier entre eux ces trois plus grands communs diviseurs F, F', F*. En conséquence^ aprè^ avoir " trouvé que 1220.111 est le plus petit multiple des nombres 1220 et 555, je cbercbe le plus grand commun diviseur entre 6771 et 111 ; il est 111 ; puis celui qui existe entre ^^=61 et 1220; et comme je trouve pour résultat 61, j'en conclus que 6771 est lui-même le plus grand commun diviseur entre 6771 et 1220.111 ; de sorte que 1220.111 est le plus petit multiple des trois nombres 1220) 555 et 6771. On verra de même que le plus grand commun diviseur entre 83509 et 111 est 37, que celui entre ^^P = 2257 et 1220 est 61 , de sorte que le plus grand commun diviseur entre 83509 et 1220.111 est 37. 61. Le quotient de 83509 divisé par 37.61 est 37 , et par conséquent le plus p3tit multiple des nombres 1220, 555, 6771 et 83509 est 1220.111.37=5010640.