Décomposer un nombre donné en ses facteurs premiert

Le procédé le plus naturel pour résoudre cette question â*essayer la division du nombre proposé, successivement les nombres premiers 2, 3, 5, 7^ 11, etc. Ainsi on essajnl d'abord de diviser le nombre proposé par 2 : si la division ré»| sit, on essayera de diviser par 2 le quotient qu'on aura troofi; si cette seconde opération réussit^ on essayera de diviser ce»' cond quotient par 2, et ainsi de suite jusqu'à ce qu*on arrmi un quotieut qui ne soit plus divisible par 2. On essayera alon de le diviser par 3, et autant de fois de suite par 3 qu'il sen possible; on parviendra ainsi à un quotient qui ne sera plos 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 ains jusqu'à ce qu'on arrive à un quotient qui soit un nombre pre* mier^ ce qui aura nécessairement lieu y sans quoi la décomposition du nombre proposé en facteurs n'aurait pas de fin ; et ce nombre étant ainsi le produit d'une infinité de facteurs, toas plus grands que l'unité, serait par conséquent inGni. On divisera le dernier quotient par lui-même, ce qui donnera pour résultat l'unité, et alors l'opération sera 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.Ilré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 l'on a trouvést 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 sys- .» tème de facteurs premiers (8Kj. ^ //"^

*80. Proposons-nous actuellement de former tous les diviseurs (Tun nombre.

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

Gela posé, il en résultera que le nombre n sera divisible par toutes les puissances de o, de b, de c, depuis la première jusqu'à la p**"' pour a, jusqu'à la g'*""' pour 5, jusqu'à la r**"** pour c : de plus, comme ces différentes puissances de a, de & et de c sont premières entre elles deux à deux (85), 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 de 5 ç'*"*,

1 de c r**"",

et l'on formera le produit des nombres contenus dans ces trois lignes, ce qui se fera en multipliant successivement tous les termes de la première par ceux de la seconde, puis tous les termes 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 6, et des produits des puissances de a par ceUes 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 6, 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 n.

*90. Dans la pratique, pour obtenir tous 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 les 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 Ta multiplié par le premier facteur 3, et Ton a écrit le produit 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é : 1* le diviseur 1 et toutes les puissances de 3 qui peuvent diviser 4725 ; 2» le diviseur 5 et toutes ses combinaisons avec les diverses puissances

de 3; ^3"* la deuxième puissance de 5 et ses combinaisons avec 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 a bien formé ainsi tous les diviseurs tant simples que composés du nombre 4725 (89).

•01. Le nombre total des diviseurs d'un nombre {en y comprenant ce nombre et l'unité) est égal au produit des easposants de ses facteurs premiers^ augmentés chacun d'une unité.

Nous avons vu qu'on pouvait former tous les diviseurs d'un nombre n= a'. 6«. (?*■, en effectuant le produit de trois lignes qui contiennent respectivement 1 et toutes les puissances de a jusqu'à lap'*"*, 1 et toutes les puissances de & jusqu'à la g**"", 1 et toutes les puissances de c jusqu'à la r**""' (89) : ainsi ces lignes se composent respectivement de (p+ l),(g+ l),(r4- l)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 + !)• fe + !)• Maintenant, en multipliant le produit des deux premières lignes par un terme quelconque de la troisième, le produit contiendra (p -f 1). (g + 1) termes : donc le produit des trois lignes se composera d'autant de fois (p + 1). (g+ 1) termes qu'il y a de termes dans la troisième ligne, c'est-à-dire de (r-f-1) fois (p4-1).(^+1) termes, ou de (p+ 1).(^+ 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-f-l).(2-|- l).(l -f-l)=4.3.2 = 24, et c'est en effet ce que l'on a trouvé.

*9i. Nous avons vu (86) que, pour qu'un nombre en divise un autre, il faut qu'il ne contienne pas d'autres Êicteurs premiers que cet autre, et qu'il ne contienne pas les facteurs pre-

micrs de ce nombre à des puissances plus élevées que cdo ne les contient lui-même. Si donc nous décomposons pli nombres donnés en leurs facteurs premiers, et si nous le produit de tous les facteurs premiers communs ainsi véSy en affectant chacun d*eux du plus petit exposant qnlj dans ces nombres, ce produit sera le plus grand nombrei les divise. Donc le plus grand commun diviseur de pli nombres est le produit de tous leurs facteurs premiers comt affectés chacun du plus petit exposant qu*il a dans ces nomhm.

Exemple. Quel est le plus grand commun diviseur de 72 et de 5544? On trouvera : !• que 7260= 2*. 3, 5. 11*; 2* 5544 = 2'. 3*. 7.11; S** que le plus grand commun diviseori mandé est 2\ 3. 11 = 132.

Il suit immédiatement de la composition du plus grandi mun diviseur de deux nombres, qu'on rCaltère pas ce grand commun diviseur en divisant ou en multipliant l'un ii par un facteur qui soit premier avec l'autre, puisqu'on 0| ainsi on ne saurait supprimer ni introduire de facteur pi commun aux deux nombres proposés (83). Donc, lorsque fc cherchera le plus grand commun diviseur de deux nombres] la méthode du n° 76, on pourra supprimer dans les restes cessifs les fadeurs que Ton y apercevra, pourvu qu'ils soie premiers avec le reste précédent, ce qui simplifiera les calcok]

On pourra encore diminuer le nombre des divisions si sives en faisant en sorte que chaque reste soit moindre quel moitié du précédent. Il suffira pour cela de forcer l'unité ^1 sur le quotient, lorsque le reste surpassera la moitié âudin*! seur; car alors la difl'éreuce entre le dividende et le produit M diviseur par le nouveau quotient, étant celle même qui exisk entre le diviseur et le reste qu'on avait trouvé, sera moindn que la moitié du diviseur. Ainsi, dans l'exemple du n« 78, nos avons vu que la division de 56 par 21 donnait 2 pour quotiedl et 14 pour reste, de sorte que 56 se compose de 2 fois 21, plus li Gomme 14 surpasse la moitié de 21, nous écrirons 3 au quo* tient, et la différence entre le dividende 56 et le produit dn

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 division 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 avec 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).

* 03. Les deux problèmes que nous avons résolus aux n*" 88 et 90 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 bientôt une application (108).

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 , on décomposera chacun de ces nombres en ses facteurs premiers, et Von formera le produit de tous les facteurs premiers différents ç,

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

Ainsi y 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 plospetit 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 Ton n'a pas de Tables des nombres premiers. Considérons d*abord le cas de deux nombres seulement, et proposons-nous de trouver le plus petit nombre divisible à la fois par deux nombres donnés A et B.

II 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 ketB; on divisera B par ce plus grand commun diviseur^ ety en multipliant A par le quotient B' de cette division y on obtiendra un produit A. B' qui résoudra le problè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 plus petit multiple des trois nombres A, B, C, il faut chercher le plus grand commun diviseur de A. B' et C, divir ser C par ce plus grand commun diviseur ^ et mvJtiplier 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 multiplier A par 3M.

Exemple. Quel est le plus petit nombre divisible par 1220, 555, 6771 et 83509? On trouvera : 1« 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 Ton 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 qu'il suffira, en vertu du principe du n" 92, de chercher le plus grand commun diviseur F entre le l*** 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 C et le 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 cherche 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 S^S = 2Î57 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=5010540.