Recherche des communs diviseurs à plus de deux nombres

La recherche des communs diviseurs à plus de deux nombres repose sur le théorème suivant :

Dans la recherche des communs diviseurs à plusieurs

l4 CHAP. I. — RAPP£L DBS THÉORIES LES PLUS ÉLÉMENTAIRES.

nombres, on peut remplacer deux de ces nombres par leur plus grand commun diviseur.

Soit, en effet, à chercher les communs diviseurs aux nombres (i^ 6, c, rf.

Soil D le plus grand commun diviseur de a et 6.

On a vu plus haut que les communs diviseurs à a et 6 sont diviseurs de D.

Réciproquement, les diviseurs de D sont communs diviseurs à a el 6. 11 en résulte que les communs diviseurs à a, ft, c, d sont les mêmes que les communs diviseurs à D, c, rf. C'est ce que nous voulions démontrer.

On ramène ainsi la recherche des communs diviseurs à n nombres, à la recherche des communs diviseurs à /i — i nombres. De proche en proche, on est ramené à deux nombres. Leurs communs diviseurs ne sont autres que les diviseurs de leur plus grand commun diviseur. Ce dernier nombre est donc le plus grand commun diviseur des nombres proposés, et l'on voit que le théorème du n" 28 s'étend à plus de deux nombres.

Il en est de même des théorèmes du n** 29, comme on le voit facilement. En particulier :

32. Lorsqu^on divise plusieurs nombres par leur plus grand commun diviseur, les quotients obtenus n'ont plus d'autre diviseur commun que l'unité. On dit qu'ils sont premiers dans leur ensemble. Il faut distinguer cette expression de celle de nombres premiers entre eux deux à deux.

§ III. — Nombres premiers. Décomposition des nombres en facteurs premiers.

33. On appelle nombre premier absolu ou, plus simplement, nombre premier, un nombre différent de i , et qui n'a d'autre diviseur que lui-même ou l'unité (*). Exemple * deux, trois, cinq, sept, etc.

(^) Nous ne comptons pas i au rang des nombres premiers; certains auteurs le comptent. La question n'a d'ailleurs qu'un intérêt secondaire. Toutefois notre façon de voir a Tavantage qu'elle permet d'énoncer sans restriction le théorème sui-

Tout nombre qui n'est pas premier est dit composé. L'importance des nombres premiers résulte du théorème suivant :

34. Tout nombre qui n'est pas premier est décomposable en un produit de facteurs premiers, et cela d'une seule façon.

Soit en effet un nombre N. Si N n'est pas premier il admet un

diviseur n, et

N= nq.

Si /i et ^r sont premiers, N esl décomposé en facteurs premiers; sinon, et si n par exemple n'est pas premier, il se décompose luimême en un produit /2{^t, et

N =-- niçtq,

et ainsi de suite. 11 est évident que cette décomposition ne peut se prolonger indéfiniment. Donc, à un certain moment, N sera décomposé en facteurs premiers. Ces facteurs ne sont pas d'ailleurs forcément différents entre eux. Supposons qu'il y en ail a égaux à a, p égaux à 6, Y égaux à c, . . . , X égaux à /. On aura

Reste à montrer que cette décomposition n'est possible que d*une seule façon.

Soit en effet, d'une part,

N = abc . .,qr

(les facteurs premiers a^b^Cy , . .^ q^r étant différents ou non) et,

d'autre part,

vant : Un nombre n*est décomposable que d'une seule façon en facteurs premiers,

A notre point de vue, nous distinguons trois espèces de nombres : les nombres composés, les nombres premiers et les nombres unités, la dernière espèce ne contenant qu^un échantillon, le nombre i.

Dans la théorie des nombres entiers négatifs, la dernière espèce contient deux échantillons.

Dans celle des nombres entiers algébriques, la dernière espèce peut contenir plus de deux, et même une infinité d'échantillons.

l6 CHAP. I. — RAPPEL DES THÉORIES LES PLUS ÉLÉMENTAIRES.

de sorte que

(8) abc ,..qr ^a'b'c' ,. ,q' r'.

Le nombre premier a, divisanl le premier membre de cette égalité, divise le second. Or, si a n'est pas égal à a\ il est évidemment premier avec lui (puisque a et a' sont premiers absolus), a étant premier avec a', et divisant le produit de «' par yd,,.q^i^^ divise è'c'... grV.

De même, si a n'est pas égal à b\ il doit diviser le produit d , ., <//•'. En poursuivant ce raisonnement, on voit que, si a n'est égal à aucun des facteurs a', b\ c\ . . . , y', il doit diviser r', ce qui n'est possible que si a = /. Ainsi tout facteur de l'un des membres de Tégalité (8) se trouve dans l'autre. Les deux membres sont donc composés identiquement des mêmes facteurs.

35. Vu l'importance des nombres premiers, il serait utile d'en avoir une table. On doit donc d'abord se demander s'il existe un nombre limité ou non de nombres premiers. La réponse est que :

La suite des nombres premiers est illimitée. Autrement dit : Étant donné un nombre premier p y il en existe un plus grand. En effet, faisons le produit de tous les nombres premiers de i à /> et ajoutons-lui i. Nous obtenons un nombre A.

Si A est premier, comme il est évidemment plus grand que /?, le théorème est vérifié.

Si A n'est pas premier, il a des diviseurs premiers. Or ces diviseurs premiers sont plus grands que />. En effet, un nombre premier plus petit que/?, divisant le produit «.3.5.7 .../>, ne peut diviser ce produit augmenté de i.

Le théorème est donc démontré.

36. Crible d' Eratosthène, — H résulte de là qu'on peut seulement construire une table des nombres premiers depuis i jusqu'à une certaine limite. On y arrive par le procédé dit crible d^Ératosthène.

On écrit tous les nombres, depuis i jusqu'à la limite en question, puis on barre successivement tous les nombres qui ne sont pas premiers.

I n'est pas un nombre premier, on l'efface. 2 est premier, mais les nombres 4, 6, 8, ..., de deux en deux à partir de 2, ne sont pas premiers; on les efface. 3 est premier, mais les nombres 6, 9, . . ., de trois en trois à partir de 3, ne sont pas premiers; on les efface. Et ainsi de suite. On remarque que :

i" Quand on a effacé les multiples d^un nombre premier p, le premier nombre non effacé après p est premier, — En effet, il ne peut avoir de diviseur premier, puisque les multiples de tous les nombres premiers, plus petits que lui, ont été effacés.

2** Quand on efface les multiples d^un nombre premier q^ on peut commencer à q^, — En effet, les multiples précédents de q ont été effacés, comme multiples de nombres premiers plus petits que q.

3** Excepté 2, tous les nombres premiers sont impairs. D'ailleurs, dans la suite des nombres impairs, les multiples d'un nombre impair p se succèdent àe p en /? (*), comme dans la suite naturelle des nombres. On peut donc se borner à écrire les nombres impairs depuis i jusqu'à la limite voulue, et à leur appliquer le procédé qui vient d'être décrit. On rétablira ensuite dans la table le nombre 2 .

37. Quant au problème suivant : Reconnaître si un nombre est premier, on pourra toujours le résoudre, même si l'on ne possède pas de table des nombres premiers, en essayant les divisions du nombre donné parles nombres plus petits que lui. Si aucune ne réussit, ce nombre est premier (2).

38. Remarque, — Tous les nombres premiers sont des multiples de 4 augmentés ou diminués de 1 ; ce sont aussi des multiples de 6 augmentés ou diminués de i . Les réciproques de ces théorèmes ne sont pas vraies.

39. Application de la décomposition des nombres en facteurs premiers, — La décomposition des nombres en facteurs

(') Ceci n'est pas évident, mais résulte simplement de ce qu'un multiple de /?, kp, est impair lorsque k est impair et dans ce cas seulement. Les multiples impairs de p sont donc /?, 3/?, 5/?, La différence entre deux consécutifs est

égale à 2/?; donc ils se suivent de /? en /> dans la suite des nombres impairs.

(2) Voir la note C.

l8 GHAP. I. — RAPPEL DES THÉORIES LES PLUS ÉLÉHEIfTAlRES.

premiers met en évidence certaines propriétés de ces nombres. Par exemple si l'on considère, d'une part, que pour faire le produit de deux nombres il suffit de former un produit unique avec tous les facteurs premiers contenus dans ces deux nombres ; d'autre part, que le produit ainsi obtenu se trouve décomposé en facteurs premiers et ne peut l'être d'une autre façon, on en conclut que :

Pour qui! un nombre soit divisible par un autre, il faut et il suffit qu'il en contienne tous les facteurs premiers avec un exposant au moins égal,

40. D'une façon analogue, on voit qu'wn nombre est une puissance m^^"^^ parfaite lorsque les exposants de ses facteurs premiers sont tous divisibles par m.

41. Quand deux nombres ne sont pas premiers entre eux ils ont forcément des facteurs premiers communs. De cette remarque on déduit facilement les théorèmes suivants :

Quand un nombre est premier avec plusieurs autres, il est premier avec leur produit,

42. Quand deux nombres sont premiers entre eux, deux puissances quelconques de ces nombres sont premières entre elles,

43. Recherche du plus grand commun diviseur de plusieurs nombres, — Plusieurs nombres étant décomposés en facteurs premiers, pour qu'un nombre les divise tous, il faut et il suffit que ce nombre ne contienne que des facteurs premiers communs à ces nombres, chacun de ces facteurs avec un exposant an plus égal à celui qu'il a dans le nombre où il a le plus petit.

Donc, pour former le plus grand commun diviseur des nombres proposés, il faut faire un produit avec tous les facteurs premiers communs aux nombres, chacun d'eux étant pris avec un exposant égal à celui qu'il a dans le nombre où il a le plus petit.

Exemple : Le plus grand commun diviseur de

720 = vt^.S'.S, I 3-20 = a'.S .5 .11,

est