Considérons la congruence du premier degré
ax -^ b^o (modM).
Supposons d'abord a premier avec M. Pour voir si la congruence admet des racines, mettons pour x successivement les valeurs
ou, si l'on veut, M valeurs quelconques formant un système complet de résidus. Il est clair que les valeurs correspondantes de ax -f- b sont incongrues, car la re-
2/i T.-J. STIELTJES.
lation
ax -H 6 ^ ay -h h
exige qu'on ait ax ^ ay ou encore x ^JK? puisque a est premier avec M.
Les valeurs de ax -f- b forment donc également un système complet de résidus, et, parmi ces valeurs, il y en a donc une qui est congrue avec o. La congruence proposée admet donc une racine.
Supposons maintenant (a, M) = rf. Dans ce cas, il est clair que b doit être divisible par d\ dans le cas contraire, la congruence est impossible évidemment. Admettant donc que b soit divisible par rf, la condition imposée à x revient à celle-ci
Puisque ^ et -j sont premiers entre eux, nous savons qu'il existe une seule racine
par rapport au module -j* Soit x^ cette racine, l'ensemble des valeurs de x qui satisfont à la question est comprise dans l'expression
^0-*- ^7, .r = Oï ±ï» ±2, ±3, ....
Mais il est clair que, suivant le module M, ces nombres se répartissent en rf c/«55^5, car les d nombres
M M ^M .^ vM
a?o, ^o-H-n^» Xo+2-T» iTo-l-a-jj ..., x^-^{a — O'j'
sont incongrus suivant le module M, mais un nombre quelconque Xq-\- --ty est congru, suivant le module M, avec un de ces d nombres.
Théorème L — La congruence
aar + 6 = o (mo(JM)
est possible seulement lorsque b est divisible par d =^ {a ^ M). Si cette condition se trouve satisfaite, elle admet exactement d racines.
On voit que cet énoncé renferme aussi le résultat particulier qui a lieu pour d =1,
9. Il nous reste à donner une méthode pour trouver effectivement, sans trop de peine, la racine de la congruence
ax-^b^o (modM).
Il est clair que nous pourrons nous borner au cas où a et M sont premiers entre eux, puisque le cas général se ramène immédiatement à ce cas particulier. Ensuite il suffira de considérer la congruence
ax==i (modiM);
car, la racine de cette congruence étant obtenue, il suffira évidemment de la multiplier par — b pour obtenir la racine de la congruence proposée. Le problème revient donc à satisfaire à Féquation indéterminée
ax — M j^ = I .
On développe en fraction continue le rapport M:a ou, ce qui revient au même, on applique à a et M l'algorithme d'Euclide. On peut alors exprimer de proche en proche comme fonctions linéaires homogènes de a et M tous les restes obtenus et finalement le p. g. c. d. lui-même qui est i. Comme ce mode de calcul est encore utile dans d'autres circonstances, nous allons l'expliquer avec détails.
Supposons qu'on ait une suile de nombres N, N,, Nj, . . . liés par les relations
N, =aîNi-i-N3, •••>
alors on peut exprimer successivement N par Ni et N2, par Na et Ns, . . .,
N = (aia2-^0Nî-+-aiN3,
N = (aiai^a-f- ai-+- a8)Ns-i- («laj-t- i)N4,
Introduisons un symbole
[rti, a,, . ..,a^], déterminé par les relations
j [a|] = a,, [ai,«2] = flr,a,-hi,
alors on aura généralement
(3) N = [ai, aj, . . ., «itj\/t-h [«i, «i, . . ., ak~\]^k-\-i-
26 T.-J. STIELTJES.
Il est cJair qiron aura aussi
Ni = [aj,a3, . . ., aji.]Nfc-h [ai,a3» •• •» «'a-iINa-h, N2= [«3, . ..,a^]N;t •+■ [«3, ..., aA-il^AM-i,
el, si Ton substitue ces valeurs dans la première relation (i), on obtient une expression de N par Ny^etNA^, qui doit être identique avec (3). D'où Ton conclut
(4) [ai, aj, . . ., a^i] = ai[ai, «3, . . ., a^t] -^ [«s» . • •» ^a]j
ce qui donne un nouveau moyen pour obtenir par récurrence la valeur du symbole. A Taide de ces relations (a) et (4), on démontrera facilement celte formule
(5) [ai, aj, . . ., Uk] = [«A, «*-i, •• -, ^«» ^il- Enjoignant à l'équation (3) celle-ci
(6) Ni= [at, «3, .. ., axJNA-H- [«tï«3» • • m «*-i]Nji-h,
on a deux équations; d'où l'on pourra tirer la valeur de N^ en fonction de N et N|. Mais cette valeur s'obtient aussi directement, car on obtient de proche en
proche
+Nî=N-a,Ni,
— N3=aîN — [a,,a,]Ni,
Généralement,
(7) (—i)^Na== [at, «3, ...,«A-i]N — [ri|,aj, .. ,^/it-,]N,. En comparant cette valeur de Na avec celle tirée de (3) et ((3), on a
(8) [«ij^t, . . ., aji] X [ai, as, . . ., Uk-t] — [«i, aj, . . ., ax-i] x [ai, a^, . .., a^] = (— i)*.
Ce sont là les formules dont nous aurons besoin ; nous en donnons encore quelques autres qui sont quelquefois utiles. On a
^k — [ak-^\, a^+i, . . ., aAH-/]N)t+/-h [a^+ij • • -, aA.-H/-i]Njt^-/-hi,
Substituant ces valeurs dans (3), on a l'expression de N par Na-|/ et N)n/+i, expression qu'on peut obtenir aussi en remplaçant k par k -^ l dans la même formule. On trouve, par comparaison,
(9) l^'lJ «i) •• -jOAm-/]
= [a\j aj, ..., ax] x [a^+i, . . ., a/ç^i] h- [ai, a», . . ., «a-i] x [a^^i, . . •, «A+/]-
Enfin nous ajoulepons la relation suivante
(10) [ai, «j, : .., (ir; bu bi, .. ., b^; Cj, Cj, .. .,C/] x [6|, bx, . . ., bg] — [«1, ...,«/.; ^1, . . ., bg] X [^1, ...fbg-yCi, . . ., C/1 = (— i;*[ai,a,, .. .^cip-i] X [c,, Cj, . . ., Ci]
qui, pour /• = / = i, reproduit la formule (8) et, pour 5 = o, la formule (9).
