Considérons la congruence du premier degré
ax-\-h = Q (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 a\X,axziiay 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
x + ^^0 [mody
r uisque -r et ^ 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 cl classes , car les d nombres
,M ,„M ,M irwn^
sont incongrus suivant le module M, mais un nombre quelconque
M Xq-^ -ry est congru , suivant le module M, avec un de ces d nombres.
Théorème I. — La congruence
a a; + 6 = 0 (mod M)
est possible seulement lorsque b 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
ax-\-b~0 (mod M).
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 = l (mod M);
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 t/= 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 , Ni , Ng , . . . liés par les relations
|N =aiNi + N2,
|Ni =a2N2 + N3, (1) N2 =a3N3 + N,,
alors on peut exprimer successivement N par N^ et Ng, par Ng et Ng,
N = (ai02 + l)N24-aiN3,
N = (Oi Og 03 + ai + ag) N3 + («i Og + 1) N4 ,
Introduisons un symbole
[àj, «2» • • • > «*]> déterminé par les relations
[aj] = ai , [oi Og] = «1 Og + 1 ,
[Oj. Cg, . . . , afc]:=[ai, «2» • • • > «A-l ]«* + [«D «2> • • • > «ft-2]i
alors on aura généralement
(3> . . . N = [ai, ttg, . . ., afc]NA; + [ai, a2, . . ., a&i]Nfc + i.
Il est clair qu'on aura aussi
Ni = [a^, «3, . . . , a;f] N^ + [«2> «3, . . . , a^ 1] N^ + 1 , N2 = [«3, • . • , ak]^k + [«3. • • • ) a* - 1] Na: + 1 ,
et, si l'on substitue ces valeurs dans la première relation (1), on obtient une expression de N par N* et Ns + i qui doit être identique avec (3). D'où l'on conclut
(4) . . [«1, 02, ..., a;t] = ai[a2, «3. ■••> «a] + [«3> ■■■> «*]>
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) . . . . [tti, «2, ..., ak'] = lak, Uk-u ..., a^, aj. En joignant à l'équation (3) celle-ci
(6) . . . Ni = [a2, CTs) • ••> «A:]NA; + [a.2, ag, ..., a/,i]NA + i,
on a deux équations ; d'où l'on pourra tirer la valeur de N/c en fonction de N et Nj. Mais cette valeur s'obtient aussi directement, car on obtient de proche en proche
+ N2 = N-aiNi,
— Ng = Og N — [%, ttg] Nj,
+ N4 = [fls, «J N — [«1, a^, aJi Nj,
Généralement ,
(7) . . (— l)*N4 = [a2, «3. •••,a'fc-i]N — [ai, 02, ...,a/c-i]Ni.
En comparant cette valeur de Ns avec celle tirée de (3) et (6), on a
(8) [tti, a^, ..., ajxfe «3, ,.., a^-i]— [«1, «2, ..., «a^-iIx^. a,j, ..., aA] = (— 1)*.
Ce sont là les formules dont nous aurons besoin; nous en donnons encore quelques autres qui sont quelquefois utiles. On a
Nat =[aA; + i, afc-f-ij, . . . , ak+i] N^+i + [0^ + 1, . . . , ak+i-i]Nk + i-^i,
Ni + l =[afc + 2, . . ., «ft + ONA + i 4-[«*+2, • . • , aA: + (-l]NA:i i4-i.
Substituant ces valeurs dans (3), on a l'expression de N par N^+j et Nyt4 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, «2, •••, «4 + 0 =
= [ai, 02, ...,aA:]X[a/(+i, ...,aft + i] + [ai, 02, ...,afc-i]X[aft+2,...,aA+0.
Enfin nous ajouterons la relation suivante
(10) [oi, a.>, .. ., Or; 61, 62. •• •> à,; c^.c^, ..., cj X [61, 62. •••> &J —
— [oi, . .., Ori 61, ..., 6J X [61, ..., &,; Cl, .. ., cj] =
= (— 1)» [Oi , 02 , . . . , «r- 1] X [C2 , C3 , . . . , C(]
qui, pour r = / = l, reproduit la formule (8) et, pour s = 0, la formule (9).
