Pour appliquer ces relations à la solution de l'équation
ax — M ?/=: 1 ,
on prendra N = M,Ni = a. Comme ces nombres sont premiers entre eux, on finira par trouver Na: = 1, N^ + i =0, de manière qu'on ait
M = [fli, ffa. • • ■) Cf/J.
a = [02, . • . , a*] , (— l)* = [a2, «3, •••, «A-i] X M — [aj, Og, . . ., «A-i] X a.
On peut donc prendre
« = (— l)*-i[ai,a2, .. . , a^-i],
J/ = (— 1)''~'[«2. a,i. • •• . «A^-i]- Si l'on fait le calcul de la manière ordinaire , le dernier quotient Uk est au moins égal à 2, et l'on peut le remplacer par les deux quotients flA: — 1 et 1 , de manière que le nombre total des quotients est à volonté pair ou impair. Il est à peine besoin de dire que
«s + '-.-L. i-, ttk
On voit sans peine que, aj^, y^ étant une solution particulière de
ax — My = 1 ,
la solution la plus générale sera renfermée dans les formules
a; = Xa + M < )
Il est clair aussi que l'équation indéterminée
ox-j- 62/ = c
sera impossible si c n'est pas divisible par d = (a, b). Mais , si cette condition est satisfaite, il y a toujours une infinité de solutions. Soita;o,2/o une solution particulière , la solution la plus générale sera
X — Xq-\- , ( I
v^yo—^t]
11. Nous allons considérer maintenant le problème suivant, qui se rencontre très souvent :
Trouver tous les nombres x qui satisfont au système suivant de n congruences
x — a (modA), a; = /î (raodB), a; = )'(modC), ..., a; = A(modL),
Soit M le p. p. c. m. des modules A, B, C, . . . , L, il est clair que, si la valeur x = .Cg satisfait aux conditions , il en sera de même de toutes celles comprises dans la formule
ajo 4- M « (< = 0, ± 1 , dz 2, . . .).
Réciproquement, si l'on a deux solutions x^ et x^, la différence x^^ — x^ doit être divisible par M, puisqu'elle est divisible par A, par B, . . . , par L. Il résulte de là que , parmi les nombres
formant un système complet de résidus pour le module M , il y en aura tout au plus un qui satisfait aux conditions , et nous pouvons dire :
Si le problème proposé admet des solutions , ces solutions seront toutes renfermées dans la formule
a; = a (mod M) ,
où a est un nombre déterminé de la série 0, 1 , . . . , M — 1.
Mais , si aucun des nombres 0,1,..., M — Ine satisfait au problème, on sera assuré que le problème est impossible et n'admet aucune solution.
Supposons maintenant d'abord que A, B, C, . . . , L soient premiers entre eux, alors M = ABC . . . L, Si l'on divise maintenant chacun des nombres
par A, par B, . . . , par L, on obtiendra en tout M systèmes de résidus qui seront tous différents. Mais, d'autre part, on ne peut donner à a que A valeurs, à /î B valeurs, etc., en sorte que le nombre total des systèmes de résidus possibles est M.
En divisant donc les nombres
0, 1, 2, ..., M-1 par A, B, C, . . . , L, on obtiendra effectivement tous les systèmes possibles de résidus , et chaque système une seule fois.
Théorème II. — Les modules A, B, C, . . . , L étant premiers entre eux , le système des congruences
XEHa (modA), a5EEE|8 (modB), ..., x^k (modL) admet toujours des solutions, renfermées toutes dans la formule
x^^a (modM), où
12. Lorsque les modules A, B, C, . . . , L ne sont pas premiers entre eux , M est plus petit que le produit A B C . . . L.
Or il y a toujours A, B, C, . . . , L systèmes de résidus possibles (si l'on prend a, fi, y, ..., l arbitrairement). Mais le problème ne sera possible que si le système a, fi, y, . . . , k se trouve parmi les M systèmes de résidus qu'on obtient en divisant les nombres
par A, B, C, . . . , L. On voit donc que, dans ce cas, le problème ne sera pas possible toujours: il faudra, pour cela, que a, fi, . . . , l satisfassent à certaines conditions que nous énoncerons plus bas. Mais toujours, lorsque le problème est possible, la solution est donnée par une formule
33 = a (modM).
13. Revenons au cas où A, B, C, . . . , L sont premiers entre eux pour voir comment on obtiendra la solution x'z^a (modM).
Puisqu'on doit avoir a; = a (modA), on posera
x = a-\- ky, et il viendra
Ay^^fi — a (modB), A y = y — a (mod C).
ifUR LA THÉORIE DES NOMBRES. 297
La première congruence donnera
on substituera cette valeur dans les autres congruences, etc.
On remplacera cette méthode souvent avec avantage par la suivante indiquée par Gauss.
Déterminons d'abord les nombres auxiliaires a\ /S', . . . A' par les congruences
BCD...La'==l (modA), ACD...L,8'Er;l (modB), ABD...L/=r=l (modC),
AB...KA' = 1 (modL).
alors on aura
x~ BCD...Laa' + ACD...L^j8' + ABD...L7/
+ A B C . . . K A A' (mod M = A B C . . . L).
On vérifie , en effet , immédiatement que cette valeur de x satisfait aux congruences proposées, et il est facile de s'apercevoir que cette méthode revient à résoudre la question successivement dans les cas particuliers où l'un des résidus a, /î, . . . , A est 1 et où tous les autres sontO. On compose ensuite la solution générale avec ces solutions particulières. Il est clair que cette méthode sera surtout avantageuse lorsqu'on aura à résoudre le même système pour diverses valeurs des résidus a , /5 , . . . , A , les modules A , B , . . . , L restant les mêmes. Les mêmes nombres a', /5', . . . , A' servent alors pour les diverses solutions.
14. Revenons maintenant au cas général où les modules A, B, ..., L ne sont pas premiers entre eux. On peut d'abord poser comme tout à l'heure
x = a-\- ky,
et la seconde congruence deviendra
Ay^^ — a (mod B).
Il faudra donc que p — a soit divisible par (A , B) = d. Si cette condition n'est pas satisfaite , le système n'admet aucune solution. Mais , si elle est satisfaite , on aura
et, par conséquent,
