Considérons la congruence du premier degré
aa;4-& = 0 (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 -\-b sont incongrues , car la relation
ax-\-b^ay -\-b
exige qu'on ait ax::^ay ou encore x^^y^ puisque a est premier avec M.
Les valeurs de ax-\-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 0. La congruence proposée admet donc une racine.
Supposons maintenant (a,M) = d. 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 d, la condition imposée à x revient à celle-ci
mod
Puisque 7J et -r sont premiers entre eux , nous savons qu'il existe une
seule racine par rapport au module -r- Soit Xq cette racine, l'ensemble
des valeurs de x qui satisfont à la question est comprise dans l'expression
Mais il est clair que, suivant le module M, ces nombres se répartissent en d classes , car les d nombres
O/Q , Xq-j- -j, Xo-\- 2 -^f Xq-]- S-^, . . . , Xo-\- (d 1 ) —
sont incono-fus suivant le module M, mais un nombre quelconque
M Xq-\- .y est congru, suivant le module M, avec un de ces d nombres.
Théorème I. — La congruence
aa; + 6 = 0 (modM)
est possible seulement lorsque h est divisible pard:=(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
aa: + 6 = 0 (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
aa;=l (modM);
car, la racine de cette congruence étant obtenue , il suffira évidemment de la multiplier par — b pour obtenir la racine de la congruence pro posée. Le problème revient donc à satisfaire à l'équation indéterminée
ax — Mî/= 1.
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 1. Comme ce mode de calcul est encore utile dans d'autres circonstances, nous allons l'expliquer avec détails.
Supposons qu'on ait une suite de nombres N, Nj , Ng, . . . liés par les relations
fN =aiNi + N2, Ni =a2N2 + N3, (1) N2 =a3N3 + N4,
alors on peut exprimer successivement N par N^ et Ng, par Ng et Ng, . ..,
N = aiNi + N2,
N = (aia2+l)N24-«iN3,
N = («1 02 Og + ai + 03) N3 + (Oi «2 + 1) N4 ,
Introduisons un symbole
[«1, «2, . .. , Cfc],
déterminé par les relations
, j[ai] = ai. [«1021 = 0102 + 1,
( [Oi. O2, . . . , Ofc] = [ai, O2, . . . , Ofc i ]«* + [Oi, «2, . . . , Oft 2],
alors on aura généralement
(3) . . . N = [Oi, 02, .. ., aA:]N&4-[«i.«2> •••» «*-i]Nft + i-
Il est clair qu'on aura aussi
Ni = [02, Og, ..., OA]Nft + [a2, Og, ..., aA i]NA + i, N2 = [a3, ••■, «A]Nfc +[«3» ■■•> ak-\]Nk + i,
et, si l'on substitue ces valeurs dans la première relation (1), on obtient une expression de N par Nt et Na+i qui doit être identique avec (3). D'oii l'on conclut
(4) . . [Oi, O2, ..., at] = 0i[02, Og, .. ., O/J + COg, ..., flft],
ce qui donne un nouveau moyen pour obtenir par récurrence la valeur
du symbole. A l'aide de ces relations (2) et (4), on démontrera facilement cette formule
(5) . . . . [«1, «2. •••>«*] = [«*. «ft-l) •••) «2) «]]•
En joignant à l'équation (8) celle-ci
(6) . . . Ni = [a2, ffg, ...,afc]Nfc + [a2,a3, ..., o;i i]Nft + i,
on a deux équations ; d'où l'on pourra tirer la valeur de N* en fonction de N et Nj. Mais cette valeur s'obtient aussi directement, car on obtient de proche en proche
-fN2 = N-aiNi,
— N3 = a2N — [ai,02]Nj,
-f N4 = [02, a.J N — [fli, flg, «s] Ni,
Généralement ,
(7) . . (— l)'^NA = [a2, «3. •••.aA:-i]N — K, a2, ...,afc]]Ni. En comparant cette valeur de N^ avec celle tirée de (3) et (6), on a
(8) [ai, ttg, ..., ttkjXla^, «3, ..., a^-i]— [ai, a2, ..., a^ -i]X[a2. a^, ..., ak] = {— 1)*.
Ce sont là les formules dont nous aurons besoin; nous en donnons encore quelques autres qui sont quelquefois utiles. On a
Nfc =[afc-t-i, aft-f 2, • • • , cik+i] ^k+i -\- [cik+i, ...jak+i-iJi^k+i+i, Nfe + i ^[aA;+2, . • . , ak+ij^k+i + [a* +2, . . . , ak-\-i-i]Nk + i + \.
Substituant ces valeurs dans (3), on a l'expression de N par Na:^-; et Nt+i+i, expression qu'on peut obtenir aussi en remplaçant k par k -\- l dans la même formule. On trouve , par comparaison ,
(9) [ai,a2, ..., afc + i] =
= [ai, ag, ...,Ofc]x[aft-|-i, ...,aA+(] + [ai, ttg, ...,«ft-i]X[afc+2, .••,aA + î].
Enfin nous ajouterons la relation suivante
(10) [ai, «2) •• •» «r; &i, 62. • • •; ^»; <^\> C2, . . ., c<] X [61, 62« • • •> ftj —
— [ai, ..., ari 61, ..., 6s] X[6i, ..., 65; Cl, ..., C(] = = (— l)*[ai, a2, ..., ar-i] X[C2,C3, ...,C(]
qui , pour r = < ^ 1 , reproduit la formule (8) et , pour s = 0 , la formule (9).
