HE CHERCHES

congruences qui reviennent à ig-f-S^-f-z/^o, lO-j-sZ-f^az/^o 5^5/+3m^o (mod. 4). Chacune d'elles sera évidemment satisfaite, si u^t-i-i ( mod. 4 )• Concluons de laque les valeurs de x^2, 5, 8, II que l'on obtient en faisant successivement /=o, I, 2, 3, doivent être combinées respectivement avec les valeurs 3, 6, g, o de z } desorte qu'il y a quatre solutions.

j:^2,5,8,ii ,j^ II, II, II, II, j z^3,6,9,o (mod. 12).

A ces recherches qui remplissent la tâche que nous nous étions proposée dans ce chapitre , nous joindrons quelques propositions qui se rapportent aux mêmes principes , et qui seront d'un fréquent usage par la suite.

38. Problème. Trouver combien il y a de nombres plus -petits qiûun nombre donné A, et premiers avec lui? Désignons, pour abréger , le nombre cherché par le caractère (p placé avant le nombre donné j le nombre cherché sera (pA.

i". Quand A est premier, il est évident que tous les nombres, depuis I jusqu'à A — i, sont premiers avec^, et partant, dans ce cas , on a (pAz=:A — i.

2'. Quand A est une puissance d'un nombre premier p , p"" par exemple -, tous les nombres divisibles par p ne seront pas premiers avec A , les autres le seront ; c'est pourquoi de p"" — i nombres, il faut rejeter ceux-ci :p, 2p,5p,.,( ;?'»—— i) p. Il en restera donc

■p^ I — (;?'""" — I )=/?'" — yo"'-* =/?'"-' (yt7— I ) donc

(pp"'z=p"'^\(p — i).

3°. Les autres cas se ramènent facilement à ceux-ci , au moyen de la proposition suivante : Si on décompose A en facteurs .... M, N, P, etc. premiers entr*eux ^ onaura(pA=:(pM,(p'î^ .(pF., etc., qui se démontre ainsi qu'il suit. Soient m, m', m", etc. les nombres premiers avec Met plus petits que lui. Soient de même 72, n% n", etc., p, p, p", etc., etc. les nombres premiers avec iV, F, etc. respectivement, et plus petits qu'eux j il est évident que tous les nombres premiers avec A le seront aussi avec les facteurs M, N, P , etc. , et réciproquement ( n° 19 ) , et que tous les nombres qui seront congrus à l'un quelconque des nombres m, m' , etc. suivant le module M, seront premiers avec M) de même pour Nf Pi etc. L^

question est donc réduite à déterminer combien il y a de nombres au dessous de A y qui soient congrus à quelqu'un des nombres 772, m' , eic. suivant le module M, à quelqu'un des nombres n, n'y etc. suivant le module iV, etc. j mais (n°32) tous les nombres qui ont des résidus donnés suivant chacun des modules M, N , P f etc. doivent être congrus suivant leur produit A , et parconséquent il ne peutj en avoir qu'un seul congru à des résidus donnés suivant les modules M, N, P, etc. , et qui soit plus petit que A. Ainsi le nombre cherché sera égal au nombre des combinaisons des différens nombres ttz, m' , ttz" , etc. avec les nombres n, 7i' , n' , etc. et les nombres ;?, ;»', p' y etc., etc. Or par la théorie des combinaisons, ce nombre est (p {M) .<p(^N) .(^{P) . etc.

4'. On voit facilement comment on peut appliquer cette proposition au cas dont il s'agit. On décomposera A en facteurs pre-

miers; c'est-à-dire, qu'on le réduira à la forme abc etc. , a, h yC y etc. étant des nombres premiers différens. Alors on aura

^A=(pa*' .(pb .çc^. etc. z=a^'^(a — i).b'\b — i).c^ ^{c — 1) etc.^ qui peut se mettre sous la forme plus élégante

(pAz=zA. .— r- . etc.

T abc

Exemple : Soit ^=60 = 2*. 5. 5, on aura :p^=6o.{.|.f .|=i6 Ces nombres premiers avec 60, sont : i, 7, n ^ i5, 17, ig, 25, 29, 5i , 57, 41, 45, 47, 49, 55, 59.

La première solution de ce problê/ne se trouve dans le Mémoire d'Euler , intitulé : Theoremata arithmetica noi'â methodo demonsirata. (Comment, nov. ace. Petrop. VIII, pag. 74). La démonstration en a été donnée encore dans une autre dissertation intitulée : Speculatlones circa quasdam insignes proprielates numerorunu (Acta Petrop. VIII, p. 17).

39. Si la signification du caractère <p est déterminée de manière à ce que '^A exprime combien il j a de nombres premiers avec A , et non plus grands que -«^j alors on uaura plusÇi=o, mais=i> mais dans tous les autres cas il n'j aura rien de changé. En adoptant cette définition ; nous aurons le théorème suivant ;

SI a, a', a', etc. sont tous les diviseurs de A, l'unité et Af compris, onaura <pa-|-(pa'H-(:pa''-f-^^.=A. Par exemple^ si^=3o, on aura

Démonstration, Si l'on multiplie tous les nombres premiers

A avec a et non plus grands que lui par —, de même tous les nombres

premiers avec d par -7- , etc. j on aura cpa -|- (i^d -f- Q^d + etc. ,

nombres tous non plus grands que A ', mais

1". Tous ces nombres seront inégaux j car il est évident que ceux qui proviennent du même diviseur de ^ sont tous inégaux. D'ailleurs s'il en résultait deux égaux provenant de diviseurs differensil/etiV, et de nombres jw. et y qui leur soient respectivement premiers j

c'est-à-dire, sironavait-^/A=-^i', ou bien Nfx^^Mv, en posant

M'^N, (ce qui est permis ), il s'ensuivrait, puisque M'est premier avec fxet qu'il divise NfA, qu'il devrait aussi diviser N , ce qui est absurde.

2'. Entre ces nombres on trouvera tous ceux qui composent la

suite 1,2,3 A, En effet, soit t un nombre quelconque qui

ne surpasse pas ^, et J^ le plus grand commun diviseur entre

A et t, -y sera le diviseur de A avec lequel j sera premier. Donc

le nombre t se trouvera parmi ceux qui ont été produits par le

,. . A diviseur y;

Z\ Il suit de là que le nombre total en est A 5 donc. . .-

A =:<^a-\' <pd -f- ^a" -f- etc.

40. Si ^ est le plus grand diuiseur commun des nombres . . . A, B, C, D, etc» on peut toujours déterminer les nombres a, b, c, d, etc, de manière qu'on ait aA-f-bB-f-cC-f-d-Zciir:/^.

Considérons d'abord deux nombres >^ et B seulement, et soit A leur plus grand diviseur commun. Alors la congruence Ax^X ( mod. B) sera résoluble ( n" 5o ). Soit la racine ^ot , et que l'on

fasse "^ "^^ /3 . on aura a.^-f-j85=A.

S'il

ARITHMÉTIQUES. j5

S'il y a un troisième nombre C , soit A' le plus grand diviseur commun de A et de C , il sera en même temps celui des trois nombres A, B , C, C^). On déterminera les nombres k ety àe manière qu'on ait àà-|-;/C=A', et l'on ama. ket.A'^kôB'j'yC=^?^\

S'il y a un quatrième nombre D , soit X' le plus grand diviseur commun de A' et de D , il sera en même temps celui des quatre nombres A, B , C, D, On fera â:'A'-|- </"/)= A', et partant on aura «a^ H- A:'yî:/3^ 4- A> ^ cTZ) = A'.

On procéderait de la même manière s'il y avait plus de nombres.

Si les nombres -^, B , C , etc. n'avaient pas de diviseur commun, il est clair qu'on aurait a^-4-ôjB-|-cC+ etc. = i.

4i . «S"/ p est un nombre premier , et qu'on ait p choses parmi les^ quelles il peut s* en trouver un certain nombre d'égales entr* elles, pourvu que toutes ne le soient pas : le nombre des permutations de ces choses sera dii^isible par p.

Par exemple , cinq choses A, A, A, B, B peuvent se disposer de dix manières diflférentes,

La démonstration de ce théorème se déduit facilement de la théorie connue des permutations. En ejBPet, supposons que, parmi ces p choses, il y en ait a égales kA^b égales k B^c égales à C, etc. , desorte qu'on ait a-(-ô-|^c+ etc.=/7, les nombres^, b,c, etc, pouvant aussi désigner l'unité. Le nombre des permutations sera

= i.3..a.i.'2.%.V.2^...c. etc. ' ""^ ^^ numérateur est évidemment di^ visible par le dénominateur , puisque le nombre des permutations est entier -, mais il est divisible par p , tandis que le dénominateur, qui est composé de facteurs plus petits que p , n'est pas divisible par;? ( n'. i5) ; donc le nombre des permutations sera divisible par p.

Nous espérons cependant que la déxnonstration suivante ne déplaira pas à quelques lecteurs.

C) En eîFet si a' n'était pas le plus grand commun diviseur de ^, B, C, il y en aurait un plus grand que k'. Or celui-ci divisera A et B , partant il divisera *-^-f-^j5 ou A , ce qui est absurde.

^6 HECHETICHES

Lorsque dans deux permutations l'ordre des choses ne différera qu'en ce que celle qui tient la première place dans l'une, en occupe une différente dans l'autre , mais que du reste toutes les autres choses, à partir de celle-là, suivent le même ordre dans chacune des permutations , de manière que la dernière de l'une se trouve placée immédiatement avant la première dans l'autre-, nous les appellevons permutations seuib/ables (*). Ainsi ABCDE GtDEABC, ABAAB et ABABA seront semblables.

Or comme chaque permutation est composée de p choses , il est clair qu'on pourra en trouver p — i , semblables à une quelconque d'entre elles, si l'on met successivement à la seconde , à la troisième place, etc. , la chose qui occupait la première ; donc si aucunes de ces permutations semblables ne sont identiques , il est évident que le nombre total des permutations sera égal à p fois le nombre des permutations dissemblables , et conséquemment sera divisible par p. Supposons que deux permutations semblables PC . . . TV. .,YZ, V,., rZPQ ...T puissent être identiques , et que P qui occupe la première place dans la première , occupe la 71 -|- i^'^'"*^ dans la seconde : on aura dans la dernière série le „ ^ litme ferme égal au i^s le /z+2'^™*= égal au s'^™*', etc., d'où résulte que le a/z-f-i'"'"^ est encore égal au premier, et parconséquent le 3/2+ i^*^*"^, et généralement le A-/z + 77z>^'"« égal au ;^^icme ^ où quand kn-^^m^p , il faut imaginer qu'on reprenne toujours par le commencement , la série V. . . VZPQ. . . .T, à moins qu'on ne retrapche de kn-^jn, le multiple de/7, qui en approche le plus en moins ). Cela posé , si on détermine k de manière que kn^i (mod.p), ce qui peut toujours se faire, puisque p est premier, il suivra de là que généralement le W*'^^ terme serait égal au 772 j-.iième ^ c'est-à-dire qu'un terme quelconque serait égal au, suivant , ou que tous les termes seraient égaux entre eux, ce qui est contre l'hypothèse.

42 Si les coefficiens 2iy b, c, etc» , n^ a% b'„c', etc, , fi^yd0 deux fonctions de la forme

(*) Si l'on écrivait en cercle les permutations semblables, de manière tjûfe" la dernière chose touchât à la première, il ii'y aurait aucune différence ejitxe elleay parcequ'aucune place ne peut s'appeler la première ai la dernière. / „. ''\l -j-K»

50«^ /oz/5 rationnels , mais non pas tous entiers , et que le produit soit x'"-+-'"'+Ax'"-+-"''-'-f.. . .-{-^JescoefficietisA, B,C; etc. , N ne peui^entêtre tous entiers*

En effet, réduisons à leur plus simple expression tontes les fractions qui peuvent se trouver parmi les nombres a^ by c , etc. j a' f h' y d , etc. j et choisissons un nombre premier/? qui divise un jou plusieurs des dénominateurs de ces fractions. Supposons que p divise le dénominateur d'un coefficient fractionnaire de (P), il est clair qu'en divisant (Ç) paryt?, on aura aussi

dans ^-^ au moins un coefficient fractionnaire dont le dénomi-

nateur sera divisible par p ( le coefficient du premier terme -, par

exemple ). Or on voit facilement qu'on pourra toujours trouver qn terme fractionnaire de (P) dont le dénominateur contienne yo élevé à une puissance plus grande que dans tous les termes qui précèdent, et non moindre que dans tous ceux qui suivent. Soit ce terme Gx^ et t l'exposant de p dans le dénominateur. On trouvera un terme pareil dans ^^^ , que nous supposerons être Yx^ , l'exposant de p dans le dénominateur , étant t ; on aura au moins

/-f-T=2. Cela posé, le terme x^ ^ du produit de(P)par (<J) aura un coefficient fractionnaire dont le dénominateur renfer- ^mera p élevé à la puissance t-^-r — i .

En effet , soient 'Gx^-^' , '.Gx^^^y etc. , les termes qui précèdent J&x^ dans (jP) ; G'x^^^ , G^x^"^ , etc. ceux qai le suivent. Soient

ée même dans ^ , T.^:^"*'' , rx'^+^ , etc. , les termes qui précèdent Yx^ ; et VoP^"^ , Vc?^^ , etc. ceux qui le suivent. Dans le produit de (P) par ^ le coefficient de x^^'^ sera évidemment

<:?r-f' Gr-i-''CT''+etc.