Le plus petit commun multiple des nombres

a>b>c> ...>l est évidemment au moins égal à a , et il ne peut être égal à a que dans le cas où b, c, . . . , l sont des diviseurs de a.

5. Un nombre qui divise à la fois a, 6, c, . . . , l s'appelle un commun diviseur de ces nombres. Parmi ces communs diviseurs , il y en a

nécessairement un , plus grand que les autres , et qui s'appelle le plus grand commun diviseur de a, &, c, ..., l.

Théorème II. — Le plus grand commun diviseur ô des nombres a, b, c, . . . , l est un multiple de tout autre commun diviseur ô' de ces nombres.

Soient, en effet, ô, ô', à", ... les communs diviseurs des nombres donnés. Puisque a est divisible par è, ô', ô", . . . , il est encore divisible par le plus petit commun multiple de ô, ô', ô", . . . , et il en est de même pour b, c, . . . , l. Par conséquent, le plus petit commun multiple de ô, ô', ô", ... est encore un commun diviseur de a, b, c, . . . , l. Ce plus petit commun multiple est donc nécessairement égal k ô, et ô', ô", . . . sont les diviseurs de ô. L'ensemble des communs diviseurs de a, b, c, . . . , l est identique avec l'ensemble des diviseurs de ô.

6. Pour chercher le p. g. c. d. (p. p. c. m.) de a, 6, c, . . . , ^ on peut diviser ces nombres en divers groupes , chercher le p. g. c. d. (p. p. c. m.) des nombres contenus dans ces groupes , ensuite le p. g. c. d. (p. p. c. m.) des nombres ainsi obtenus.

On pourra donc ramener le problème toujours au cas où il n'y a que deux nombres a et b, et, dans ce cas, l'algorithme d'Euclide conduit de la façon la plus simple à la connaissance du p. g. c. d. Par une suite de divisions , on obtient les relations

= qb

et r'*+i' est le p. g. c. d. de a et b.

Soit ô le p. g. c. d. de a, 6, c, ..., /, alors les nombres ma, mb, ..., ml sont tous divisibles par mô, leur p. g. c. d. est donc nécessairement divisible par mô, mais on reconnaît immédiatement que ce p. g. c. d. est exactement mô.

Pour abréger , nous emploierons quelquefois les symboles

pour désigner respectivement le p. g. c. d. et le p. p. c. m. de a, b, ..., l. On a donc

{ma, mb, . . . , wO = m X (a, b, . . . , l) et de même

\ma, mb, ..., mi\ = m X ,a, b, ..., l\. De là on peut conclure le lemme suivant qui est souvent utile. Lemme. Soient d le p. g. c. d. (p. p. c. m ) des a nombres

a, a', a", ..., e le p. g. c. d. (p. p. c. m.) des /î nombres

b, b', b", ..., alors le p. g. c. d. (p. p. c. m.) des a^ produits

ab, nb', ab", ..., a'b, u'b', ..., a"b, a"b', ...

est de.

En effet , les p. g. c. d. (p. p. c. m.) des divers groupes

ab, ab', ab", . . . ,

sont respectivement ae, a'e, a"e, ..., et le p. g. c. d. (p. p. c. m.) de ces derniers nombres est de.

7. La recherche du p. p. c. m. peut se ramener toujoiars à celle du p. g. c. d., et réciproquement.

Le p. p. c. m. de a, 6, c est de la forme

abc ,bc , ^ ca ab

-~- = aX -r = b X -r = cx -:rd d d d

donc d doit être un commun diviseur de bc, ca, ab. Pour avoir le p. p. c. m. , il faut évidemment prendre pour d le p. g. c. d. de bc, ca, ab.

Théorèrre III. — Le p. p. c. m. (p. g. c. d.) de a, b,c, . . . ,1 est égal au produit abc. . . l divisé par le p. g. c. d. (p. p. c. m.) des produits

bc . . .1, ac . . .1, . . . , abc . . . k.

8. Dans le cas de deux nombres a et b, le produit du p. g. c. d. et du p. p. c. m. est ab. Cette relation n'a plus lieu dans le cas où l'on a n nombres. Cependant ou peut rétablir l'analogie, et il faut, pour cela, considérer, non seulement le p. g c. d. et le p. p. c. m., mais une suite de n nombres qui dérivent d'une façon particulière des nombres donnés

Nous allons entrer dans quelques détails sur cette théorie , comprise dans des recherches plus générales de M. Smith dont nous aurons à parler plus loin.

Considérons n nombres

Prenons deux nombres, par exemple a et 6, de ce système et remplaçons-les par leur p. g. c. d. et leur p. p. c. m. On aura ainsi un second système (Aj)

En répétant la même opération sur (Aj) pour en déduire un système (Ag), puis un système (Ag), . . . , on finira toujours par obtenir un système dans lequel deux nombres quelconques sont eux-mêmes leur p g. c. d. et p. p. c. m., c'est-à-dire l'un de ces nombres divise l'autre. Si l'on ordonne les nombres de ce système définitif par ordre de grandeur croissante

Bk divise 6*^.1, et nous dirons que ces nombres forment le système réduit , ek est le A'^"*' nombre réduit. En effet, on verra que ce système réduit est unique et indépendant de la manière dont on a dirigé les opérations.

9. Pour faciliter un peu le langage , nous dirons que deux nombres forment un couple réduit lorsque l'un de ces nombres divise l'autre. Il est clair que , si a et 6 sont un couple réduit , les groupes (A) et (Aj) sont identiques ; on peut donc se dispenser de combiner les couples

réduits. Si tous les couples de (A) étaient réduits , ce groupe serait déjà le système réduit.

Nous allons faire voir qu'en combinant deux nombres qui ne forment pas un couple réduit , on augmente toujours le nombre total des couples réduits.

Considérons , pour cela , les divers couples réduits de (A), On peut distinguer les quatre catégories suivantes :

]° Les couples réduits f, g qui ne renferment ni a, ni 6. Il est bien clair que ces couples réduits se retrouvent dans (Aj).

2° Les couples réduits a, f qui renferment le nombre a et qui soni tels que b, f n'est pas un couple réduit. Dans ce cas , au moins un des couples a', f et h', f sera réduit , et ils peuvent l'être tous les deux. En effet, si f divise a, il est clair qu'il divise aussi 6', et, si /"est multiple de a, il sera aussi multiple de a'. [On suppose a' = (a, b), b'-^\a, b\7\

3° Les couples réduits b, f qui renferment le nombre b et qui sont tels que a, f n'est pas un couple réduit. Il est clair que ce que nous venons de dire pour le second cas s'applique encore ici.

4^ Les couples réduits a, f qui sont tels que 6, /est en même temps un couple réduit. Dans ce cas, on reconnaît facilement que les couples a', f et b', f sont aussi réduits tous les deux. Il suffit d'examiner successivement les trois hypothèses possibles : f divise a et b; f est multiple de a et de 6; /" divise l'un des nombres a, b et est multiple de l'autre.

Nous avons ainsi énuméré déjà dans le système (A^) au moins autant de couples réduits que dans (A). Mais le système (A^) renferme encore le couple réduit a', b', par conséquent le nombre des couples réduits du système (Aj) surpasse au moins d'une unité le nombre des couples réduits de (A).

Par un nombre fini d'opérations , on arrivera donc nécessairement à un groupe de n nombres dont tous les couples sont des couples réduits , et qui est ainsi le système réduit. Il reste à faire voir que ce système réduit est unique.

10. On constate d'abord qu'en remplaçant o et 6 par a' et b', on ne change ni le p. g. c. d, , ni le p. p. c. m. des nombres du système.

Envisageons maintenant les divers produits k k k des nombres (A), pour voir quelles modifications résultent, pour ces produits, par le remplacement de a et 6 par a' et 6'.

Les divers produits A à A se composent :

1° Des produits qui ne renferment ni a, ni b;

2" Des produits qui renferment a et 6;

3° Des produits qui renferment un seul des nombres a et 6.

Il est clair que ce sont les derniers produiis seulement qui sont affectés par le remplacement de a et 6 par a' et b'. Ces produits sont, d'ailleurs , en nombre pair et peuvent être écrits ainsi

aP, aP', aP", a P'", ..., 6P, 6P', 6P", 6P"', ...,

P, P', P", . . . étant les divers produits k — 1 à A — 1 des nombres c,...,l. En remplaçant maintenant a et 6 par a' et b', cela revient évidemment à remplacer chaque couple

(aP, 6P), (oP', 6P'), (aP", 6P"), .••

par son p. g. c. d. et son p. p. c. m. Cette opération, nous l'avons déjà remarqué, n'influe ni sur le p. g. c. d , ni sur le p. p. c. m. des divers produits k k k.

Par conséquent, le p g. c. d. Di et le p p. c. m M^ des divers produits k k k des nombres (A) ne changent pas en passant aux nombres (Al). Dft et Mft sont aussi le p g. c. d. et le p. p c. m. des produits k k k du système réduit

c'est-à-dire

Dft = «1^2- ••<'*) Mk = enen-1. ..Pn-it + l.

De là on conclut les relations suivantes

^1 Uk-i D„ 1

'"=■■"■■ '-=1: — =iêi '-=i£-

qui mettent en évidence ce fait que le système réduit est unique et

donnent l'expression des nombres réduits en fonction de a, b, c, . . . , l. Les relations

ej = Di = M„ : M„i, f„ = Mi = D„ : D„i reproduisent le théorème III. Puisque ek divise Bk+i, on voit que D| divise Da^ + iD^-i, M| est multiple de M^+iM^-i; on pourrait le démontrer directement en s'appuyant sur le lemme du n° 6. On voit que Dk ne peut être égal à D^ i , à moins qu'on n'ait D^ = Dg = . . . = D* = 1.

11. Lemme. a' et b' étant le p. g. c. d. et le p. p. c. m. de a et b, le p g. c. d. et le p. p. c. m. de

{m, a) et {m, b) sont respectivement

{m, a') et {m, b').

De même, le p. g. c d. et le p. p. c. m. de

I w , a i et \m, b\ sont respectivement

I m, a' I et 1 w, 6' |.

Pour démontrer la première partie, on remarque d'abord que le p. g. c. d. de (m, a) et (m, b) est évidemment (m, a, b) = {m, a'). Cela étant, pour démontrer que {m, b') est le p. p. c. m. de (m, a) et (m, b), il suffira de faire voir que

Mais cela est évident; car, d'après le lemme du n° 6, on a

{m , a) X (m , b) = {m\ ma, mb, ab) = {m^, m a', a b) , {m, a')X{'n, b')^{m% ma', mb', a'b')-={m^, ma', a' b'). Pour la seconde partie , on remarque d'abord que le p p. c m. de

I »n, a I et \m,b\ est évidemment \m, a,b\:=\m,b' \; et ensuite il est clair que

On conclut de ce lemme que les nombres réduits de

(m, a), {m, b), (m, c), . . . , {m, l) sont

(m, gj), {m, «a), {m, e^), ..., (w, e„).

De même , les nombres réduits de

|»w,ai, \m,b\, im,c|, ..., \m,l\ sont

l»»,ei|, \m,e^\, \m,e^\, ..., \m,e„\.

12. Nous avons considéré, dans le n" 10, les divers produits k k k des nombres a, b, c, . . . , l. Si, au lieu de cela, on avait considéré simplement les divers groupes khk, non pour en former les produits, mais pour en prendre le p. g. c. d. ou le p. p. c. m., on serait arrivé aux résultats suivants :

«1 est le p.g.c.d. de |a|, |6|, |c|, ..., Ul; *2 „ \a,b\, \a,c\, ..., \k, l\;

*3 » l«> &, c|, la, 6, d|, ,..;

puis aussi

e„ est le p. p. c. m. de (a), (b), ..., (l);

««-2 » ia,b,c), ia, b,d), ...;

Cette recherche n'offre aucune difficulté en s'appuyant sur le lemme du n" 11.

13. On dit que deux nombres sont premiers entre eux (ou bien a est premier avec b) lorsque leur p. g. c. d. est égal à l'unité; leur p. p. c m. est alors égal à leur produit.

Lemme. — On a

(a, bc) = (a, c) X (a, b).

En effet , il est clair que

(a, bc) = (a, bc, ae), or

(bc,ac)=zc X (a, b).

Théorème IV. — Lorsque a et 6 sont premiers entre eux, tout commun diviseur de a et bc est aussi commun diviseur de a et c. Il suffît évidemment de montrer que

(a,bc) = (a,c), II 18

mais cela est évident d'après le lemtne précédent , puisque (a, 6) = 1 par hypothèse.

On déduit de ce théorème les conséquences suivantes : 1" Si c est aussi premier avec a, bc est premier avec a. Il est facile de généraliser ce résultat ainsi. Les nombres

étant tels que chaque nombre a, a', ... est premier avec tous les nombres 6,6',..., le produit aa' a" ... est premier avec b b' b" . . . , a"* est premier avec 6". 2" Lorsque bc est divisible par a (a et 6 étant premiers entre eux) , c est divisible par a.

14. On dit que plusieurs nombres a,b, c, ... ,1 sont premiers entre eux lorsque deux quelconques d'entre eux le sont. On peut remplacer cette définition par la suivante qui lui est équivalente. Plusieurs nombres a, b, c, . . . , l sont premiers entre eux lorsque a est premier avec bc ...l, b avec cd ... l, ..., enfin k avec l.

Le p. p. c. m. des nombres a,b,c, ..., l, qui sont premiers entre eux, est égal à leur produit, et cette propriété est caractéristique. En effet,

ayant

\a, b, c, . . . , l\ =abc . . . l,

il est impossible que deux de ces nombres aient un diviseur commun > 1. Car , si ô divise a et 6 ,

-^Xcd..,l

est un commun multiple de a, 6, c, . . . , Z.

Un nombre admettant les diviseurs a , 6 , c , . . . , Z premiers entre eux, est divisible par leur produit abc . . .1.

On peut dire encore : les nombres a, b,c, ...,l sont premiers entre eux lorsque le (n — l)'^"® nombre réduit e„i = 1. En effet, e„-\ est le p. p. c. m. des nombres

On a alors aussi

Pour que plusieurs nombres a, b, c, . . . , l soient premiers entre eux, il ne suffit pas que leur p. g. c. d. soit égal à l'unité, il faut que le p. g. c. d. D„i des produits

bc . . .1, ac . . .1, . . . , abc . . .k soit égal à l'unité. (Voir le théorème III et la fin du n» 10.)

Lemme. — Le p. g. c. d. des nombres m, a, b étant l'unité, on a

(w, aô) = (w , a) X (wî , b).

En effet, d'après le lemme du n'' 6,

{m, a) X {m, 6) = (m^ ma,mb, ab), or

(w^ ma, inb)^m X {m, a, b) = m

d'après l'hypothèse.

Plus particulièrement, on aura

{m , ab) = {m,a)X{m,b) lorsque a et 6 sont premiers entre eux. Ce résultat peut se généraliser immédiatement ainsi.

Théorème V. — Les nombres a, b, c, ..., l étant premiers entre eux , on a

{m,abc...l) = {m,a) X{m,b) X{in,c) X . ■ . X(m,l). Remarque. — Ce résultat est compris aussi comme cas particulier dans les propositions obtenues dans le n*' 11. En effet , le w'*""® nombre réduit de

c'est-à-dire leur p. p c. m. est égal à

En suppo.sant a, b, c, ..., l premiers entre eux , on retrouve le théorème ci-dessus. On peut en tirer la conséquence que voici. Les nombres a, b, c, . . . , l étant premiers entre eux, un diviseur ô de leur produit peut être toujours mis d'une seule façon sous la forme

ô = a'b'c' ...l', où a' divise a, b' divise b, . . . ,1' divise l. En effet, si cette décomposition en facteurs est possible, a' doit diviser a et d, et par conséquent (a , d).

Mais, d'après le théorème V, on a

ô = (a,ô)xib,ô)x...X{l,ô); d'où il est clair que la décomposition est possible , et d'une seule manière.

D'autre part, on obtient toujours un diviseur de a 6c. . .Z, en multipliant un diviseur quelconque a' de a par un diviseur b' de b, etc.

On peut donc conclure:

Théorème VI. — Les nombres a, b, c, . . . , l étant premiers entre eux, on obtient tous les diviseurs de leur produit a 6c ... Z, et chaque diviseur une seule fois , en multipliant chaque diviseur de a par chaque diviseur de 6, ... , par chaque diviseur de l.

Corollaire. — En désignant par f{m) le nombre des diviseurs de tn (ou la somme de ces diviseurs , ou la somme de leurs k^^^^ puissances) , on a

r{abc . . . 0 =/■(«) X m X /•(c) X ... X ni)

lorsque a,b, c, . . . ,1 sont premiers entre eux.

15. Tout nombre a (excepté l'unité) a au moins les deux diviseurs a et 1. Tout nombre qui n'admet pas d'autres diviseurs s'appelle nombre premier. Nous ne compterons pas l'unité parmi les nombres premiers : les plus petits nombres premiers sont

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, .... Tout nombre qui n'est pas premier est dit composé. Un nombre composé a est toujours égal à un produit 6 c dont les facteurs sont > 1 tous les deux.

Soient p un nombre premier, a un nombre quelconque; si p ne divise pas a,aetp seront premiers entre eux.

Lorsqu'un nombre premier p divise le produit abc . . .1, p doit diviser au moins un des facteurs a, 6, c, , . . ,1; car, dans le cas contraire, p serait premier avec a, avec 6, . . . , avec l, par conséquent premier avec a6c . . . i et ne pourrait diviser ce produit.

Théorème VII. — Tout nombre composé admet un diviseur premier.

En effet, il est clair que le plus petit diviseur, surpassant l'unité, d'un nombre composé , est nécessairement un nombre premier.

Théorème VIII. — Tout nombre composé est égal à un produit de facteurs premiers ou, comme on dit, il est décomposable en facteurs premiers. Cette décomposition ne peut se faire que d'une seule manière.

En effet , mettons le nombre composé a sous la forme d'un produit

bc.l

de facteurs > 1, de toutes les manières possibles. Le nombre de ces facteurs sera toujous inférieur à n, en supposant 2" > a. Parmi ces produits égaux à o, il y en aura donc un , au moins , dans lequel le nombre des facteurs est le plus grand. Soit

Pi P2---Pk

un tel produit, il est clair que tous les facteurs sont des nombres premiers ; car, si par exemple p^ était composé , on pourrait obtenir un produit égal à a et renfermant k-\-l facteurs.

Remarque. — Il est clair qu'on obtient toujours par un nombre fini d'essais les divers produits égaux à a que nous considérons. Il suffit d'écrire les nombres

de prendre leurs divers produits un à un , deux à deux , . . . , n — 1 à n — 1 (avec répétitions) et de ne conserver que ceux de ces produits qui sont égaux à a.

La première partie du théorème se trouve ainsi démontrée ; quant à la seconde partie , supposons deux décompositions en facteurs premiers

a = PlP2P3--- = ?l3233---

Il est clair que q^ doit diviser le produit PiP^p^ . . . , et , par conséquent, un des nombres Pi, P2» Ps» • • • • donc q^ est égal à un de ces nombres, par conséquent p^ := q^.

On en conclut

d'où

Le théorème étant ainsi complètement démontré, on voit qu'on

peut mettre un r ombre quelconque, et cela d'une seule manière, sous la iorme

p" q^r^ ..., p, q, r, . .. étant des nombres premiers distincts, a, ^, y, . . . des nombres quelconques.

On peut déduire ce théorème aussi du théorème VIL

16. Pour que deux nombres soient divisibles l'un par l'autre, il faut et il suffit qu'en ayant décomposé les deux nombres en facteurs premiers le diviseur n'ait pas d'autres facteurs premiers que le dividende , et que ces facteurs ne figurent pas dans le diviseur avec de plus grands exposants que dans le dividende. Cela est évident d'après ce qui précède.

A l'aide de ce résultat , on peut reconnaître immédiatement la vérité de tous les théorèmes que nous avons obtenus sur le p. p. c m. , le p. g. c. d. , en supposant tous les nombres décomposés en facteurs premiers. Nous n'insisterons pas sur ce sujet, cependant on doit remarquer que ce n'est là, à proprement parler, qu'une espèce de vérification ; cela devient sensible surtout lorsqu'il s'agit de propositions plus compliquées, comme celles du n° 11 sur les nombres réduits. Mais nous devons expliquer encore comment on obtient immédiatement les nombres réduits dea, b, c, . . . , l, lorsqu'on a décomposé ces nombres en facteurs premiers.

Supposons donc

a = P7PF---Pk''>

'kl

C=plrpl2...pl^,

Pour plus de symétrie, nous avons introduit partout les mêmes nombres premiers Pi,P2, . . . ,pic, ce qui peut se faire en admettant pour les exposants aussi la valeur 0.

Considérons les exposants de pi

«i. (^i) ïi) •••) ^»-

Supposons qu'en les écrivant par ordre de grandeur croissante on ait

ai^bi^Ci^ . . .^ U.

Alors on aura

ei=P?'P?.

■ ■ Pt',

e„ = p*' pS» .

. • Pk",

• • Pic",

■Pi'.

C'est ce qu'on vérifie directement en remarquant, par exemple, que

?! ("2 . . . Ca = Dfc

est bien , avec ces valeurs de e^, eo, ■ . . , e„,\e p. g. c. d. des produits k à k des nombres a, b, c, . . . , l. On vérifie encore sans peine les expressions des Ch que nous avons obtenues dans le n° 12. Les diviseurs de |3" sont

leur nombre est a-\-l, leur somme

Un nombre quelconque admet donc

{a-\-l)X{ft+l)X{Y + l)...

diviseurs , et leur somme est

17. Décomposer un nombre donné en facteurs premiers , c'est un problème dont la solution exige un grand nombre de tâtonnements. On a imaginé de nombreux artifices pour abréger le travail; mais, quoi qu'on fasse , cette décomposition est , en réalité , impraticable pour un nombre un peu grand. Aussi serait-il , par exemple , à peu près impossible d'obtenir de cette façon le p. g. c. d. de deux nombres

de douze à quinze chiffres; l'algorithme d'Euclide conduit sans trop de peine au but.

On voit par là que ce n'est pas seulement en se plaçant au point de vue théorique qu'on peut exiger de ne pas faire intervenir la décomposition en nombres premiers dans des questions où ces nombres premiers ne figurent pas expressément.

Il y a une infinité de nombres premiers. En efifet , p étant un nombre premier, on peut toujours trouver un nombre premier plus grand que/). Soit, pour le montrer,

P = 2 X3 X ... Xp

le produit de tous les nombres premiers qui ne surpassent pas p. Mettons le nombre P d'une façon quelconque sous la forme d'un produit de deux facteurs