Trouver* tous les diviseurs (Tun nombre

Supposons le nombi^e donné A. décomposé en facteurs premiers. Tout diviseur de A, en dehors de 1, devra être composé de facteurs premiers qui figurent dans A, avec des exposants égaux ou moindres. En écrivant tous les nombres ainsi composés, on obtiendra tous les diviseurs de A.

Pour n'en oublier aucun, on peut procéder comme il suit.

Soit, par exemple, A = 360 = 2' X 3* X 5.

Sur une première ligne, on écrit les nombres

ils sont, avec le diviseur 1, les diviseurs qui ne contiennent pas d'autre facteur premier que 2 ; sur une seconde ligne on écrit les nombres

on multiplie les nombres de la première ligne par chacun des nombres qui figurent dans la seconde ligne; on formera ainsi les nombres

qui sont, avec le nombre 1, tous les diviseurs où n'entrent pas d'autres facteurs premiers que 2 et 3; enfin, en multipliant tous ces nombres par chacun de^ nombres

on reproduira, d'une part, tous les diviseurs précédemment obtenus, et en outre, ceux qui contiennent le facteur 5 ; on obtiendra ainsi les nombres

ou

. Ce sont tons les diviseurs cherchés. Leur nombre est évidemment

le produit des nombres de termes qui se trouvent dans les lignes (1), (2), (3), c'est-à-dire, en général, le produit des exposants, augmentés chacun d'une unité, des facteurs premiers différents qui figurent dans la décomposition de A. Ce nombre est pair si Tun des exposants est impair ; il n'est impair que si tous les exposants sont pairs, c'est-à-dire si A est le carré d'un nombre que Ton obtiendrait en divisant par 2 l'exposant de chaque facteur premier qui entre dans A. Par exemple, si l'on avait

le nombre des diviseurs serait 5 X 7 X 3 = 105, et A serait le carré de 2* X 3'X 7, puisque l'on a (n** 81)

166. Quand on se donne deux ou plusieurs nombres A, B, C, ..., décomposés en facteurs premiers, on reconnaît de suite s'ils ont quelque diviseur commun autre que un : un tel diviseur, décomposé en facteurs premiers, ne peut comprendre que des facteurs premiers ' communs à tous les nombres A, B, C, ... ; inversement tout produit de facteurs premiers ainsi formé estun commun diviseur de A, B,C, ...; le plus grand d'entre eux s'obtiendra en prenant tous les facteurs premiers communs à A, B, G, ... et en répétant chacun autant de fois que possible, c'est-à-dire autant de fois qu'il figure dans celui des nombres A, B, G, ... où il est répété le moins de fois. D'après la règle pour la formation des diviseurs d'un nombre, il est clair que les diviseurs communs des nombres A, B, G, ... seraient les mêmes que les diviseurs de leur plus grand commun diviseur.

Règle. — Pour former le plus grand commun diviseur de deux ou plusieurs nombres décomposés en facteurs premiers, on fait le produit de tous les facteurs premiers différents communs à ces nombres et l'on affecte chacun d'eux d'un exposant égal au plus faible des exposants dont ce facteur est affecté dans les différents nombres.

Exemple : soient les trois nombres

A = 2»x3»Xb'X 7 Xil», B = 2 X 3» X 5 X H X 13, C = 2 X 3» X 5» X H X 19.

Le plus grand commun diviseur sera

Si les nombres A, B, C, ... n'ont pas de facteurs premiers communs, ils sont premiers entre eux.

167. Avec la décomposition en facteurs premiers, les théorèmes des n®* 143, 144 deviennent intuitifs; à la vérité, ces théorèmes ont servi (n* 161) à montrer qu'un nombre ne pouvait être décomposé que d'une seule façon en facteurs premiers ; mais on a vu que cette proposition pouvait être établie directement. Il en est de même des propositions suivantes : si on multiplie, ou si on divise deux ou plusieurs nombres par un même nombre, on multiplie ou on divise leur plus grand commun diviseur par ce nombre ; si on divise deux nombres par leur plus grand commun diviseur, les quotients sont premiers entre eux, puisque, après la division, il ne reste plus de facteurs premiers communs; si on les divise par tout autre diviseur commun que le plus grand, il reste quelques facteurs communs et les quotients ne sont pas premiers entre eux, etc..

168. Leplus petit commun multiple de plusieurs nombres A, B,C,..., décomposés en facteurs premiers, s'obtient aussi aisément.

Chaque multiple commun, décomposé en facteurs premiers, doit contenir tous les facteurs qui figurent dans chacun des nombres A, B, C, ..., et chacun de ces facteurs doit être répété au moins autant de fois qu'il l'est dans chacun des nombres A, B, C, ..., c'està-dire autant de fois qu'il est répété dans celui des nombres A, B, C, ... où il est répété le plus. grand nombre de fois. Réciproquement tout nombre décomposé en facteurs premiers qui satisfait à ces conditions est un multiple commun de A, B, C, ... : leplus petit s'obtiendra en ne prenant que les facteurs premiers qui figurent dans chacun des nombres A, B, C, ... et en ne répétant pas l'un quelconque d'entre eux plus souvent qu'il n'est répété dans celui des nombres A, B,C, ... oùil eslrépétéle plusgrand nombre de fois. Tout multiple commun sera un multiple du plus petit commun multiple.

Règle, — Pour former le plus petit commun multiple de plusieurs nombres décomposés en facteurs premiers, on forme le produit de tous les facteurs premiers différents qui figurent dans les nombres A, B, G, ..., et l'on affecte chacun d'eux de l'exposant qu'il a dans celui des nombres A, B, C, ... où il figure avec l'exposant le plus élevé.

Par exemple, le plus petit commun multiple des nombres

2'»X3«X5, 2x3»x7xH, 3« X 7» X 19 est

2»xyx8x7*XllXl9.

NOMBRES PREMIERS. 13fi

Si Von divise le plus petit commun multiple des nombres A., B, C, ... ainsi formé par ces nombres eux-mêmes, les quotients n'auront plus de diviseur commum; car s'il subsistait, dans ces quotients, un facteur premier commun, en multipliant ces quotients par A, 6, G, ..., ce facteur se trouverait dans les produits avec un exposant plus élevé que dans tous les nombres A, B, C, ... ; on n'aurait donc pas appliqué la règle. Le plus petit commun multiple est le seul multiple commun qui jouisse de cette propriété.

Enfin si Ton ne considère que deux nombres A, B et si on multiplie leur plus grand commun diviseur par leur plus petit commun multiple, on voit que chacun des facteurs premiers qui entrent dans A, ou dans B, figure dans le produit; si ce n'est pas un facteur premier commun à A et à B, il figure dans le produit avec Texposanl qu'il a. dans A ou dansB; si c'est un facteur premier commun, il entre dans le produit avec un exposant qui est la somme de son plus grand et de son plus petit exposant dans A et dans B, c'est-à-dire la somme de ses deux exposants dans A et dans B ; le produit considéré est donc le produit des nombres A, B; c'est la règle du n* 163.

169. Les propriétés des nombres ont attiré de bonne heure l'attention des Grecs. On voit déjà les Pythagoriciens spéculer sur les nombres premiers, sur les nombres triangulaires y caiTés^ polygonaux (Ex. 104), sur les nombres pyramidaux (Ex. 105), sur les nombres parfaits (Ex. 154), sur les nombres amiables (tels que chacun d'eux soit égal à la somme des parties aliquotes de l'autre). Les Éléments d'Euclide, qui constituent un résumé des connaissances essentielles auxquelles les Grecs étaient parvenus, vers l'an 300 avant J.-C, tant en Géométrie qu'en Arithmétique, contiennent les propositions les plus importantes du chapitre actuel et du chapitre précédent, en particulier, la notion du plus grand commun diviseur, celle du plus petit commun multiple, le théorème du n^ 160, dont la démonstration offrait assurément une grande difficulté, enfin le théorème du n® 157 sur l'infinité des nombres premiers. La méthode même pour la recherche du plus grand commun diviseur de deux nombres est souvent désignée sous le nom à' algorithme d'Euclide. La démonstration que nous avons donnée du théorème relatif à Tinfinité des nombres premiers est celle même que l'on trouve dans Euclide('). La règle pour la formation d'une table de nombres

1. Une généralisation bien naturelle de ce théorème est fournie par l'énoncé suivant : Dans toute progression arithmétique dont la raison et le premier terme sont des nombres premiers entre eux, il y a une infinité de termes qui sont des nombres premiers absolus. I>a démonstration de cette proposition est très difficile; elle a été donnée, dans ce siècle, par Lejeune Dirichlefc.

premiers est aussi très ancienne : elle est attribuée à Eratosthène (vers Tan 250 av. J.-C.) et est souvent désignée sous le nom de crible d'Éraiosihène{^).

Exercices.

123. Considérons la suite des nombres premiers jusqu'à p; soit A le produit de quelques-uns de ces nombres, B le produit de tous les autres. Démontrer que le nombre A + B admet un diviseur premier plus grand quep; il en est de même, en supposant A > B, du nombre A — B, à moins qu'il ne soit égal à un.