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 Ni^ 1, Nfc4.i ^0, de manière qu'on ait

a = [a2, • • -, a*], (— D* = [«2 . «3 . • • • 1 «* - 1] X M — [«1 , a.3 , . . . , «fc i] X a.

On peut donc prendre

a; = (— l)*-'[ai, a,^, ... , a^-i], «/ = (— l)*-i[a2, aa, . .. , a^-i].

Si l'on fait le calcul de la manière ordinaire, le dernier quotient a* est au moins égal à 2, et l'on peut le remplacer par les deux quotients flft — 1 et 1, de manière que le nombre total des quotients est à volonté pair ou impair. Il est à peine besoin de dire que

M[qi,a2 , ak]^ . 1

On voit sans peine que, x^), y^ étant une solution particulière de

ax — My = l, la solution la plus générale sera renfermée dans les formules

Il est clair aussi que l'équation indéterminée

ax-\-by=: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. SoitXo,yo une solution particulière , la solution la plus générale sera

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

a; = a (modA), a; = /î(raodB), «^^(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 =: x^ satisfait aux conditions , il en sera de même de toutes celles comprises dans la formule

iCo + Mi (« = 0, ±1,±2,...).

Réciproquement, si l'on a deux solutions Xy et x^, la différence Xq — 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, G, . . . , 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 , à jô B valeurs , etc. , en sorte que le nombre total des systèmes de résidus possibles est M.

En divisant donc les nombres

par A, B, G, . . . , 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

a; ES a (mod A) , a; = /5 (mod B) , . . . , a; se A (mod L) admet toujours des solutions , renfermées toutes dans la formule

x^^a (mod M), 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, /S, 7, . . . , A arbitrairement). Mais le problème ne sera possible que si le système a, ^, y, . . . , X 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, ^ , . . . , k satisfassent à certaines conditions que nous énoncerons plus bas. Mais toujours , lorsque le problème est possible , la solution est donnée par une formule

a; = a (mod M).

13. Revenons au cas où A, B, C, .. ., L sont premiers entre eux pour voir comment on obtiendra la solution x^E^a (mod M).

Puisqu'on doit avoir x^^a (mod A) , on posera

x = a-\-Ay,

et il viendra

Ay^/S — a (modB), A. y = y — n (mod C).

La première congruence donnera

y = yo + ^i,

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', /?',... A' par les congruences

BCD...La' = l (modA), ACD...L|8'eee1 (raodB), ABD...L/ = 1 (raodC),

AB...KA' = 1 (modL).

alors on aura

a;= B CD... La a' 4-ACD...L|8/î' + ABD...LJ'}''

+ ABC...K>IA' (raodM = ABC...L).

On vérifie, en effet, immédiatement que cette valeur de a; 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, p, . . . , k est 1 et où tous les autres sont 0. 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, ;S, . . . , A, les modules A, B, . . . , L restant les mêmes. Les mêmes nombres a', fi', . . . , k' 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

et la seconde congruence deviendra

A y ^ /8 — a (mod B).

Il faudra donc que (i — 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

y = yo + \t (< = o, ±i,±2,...)

et, par conséquent,

x — a + Aî/o ^mod— ji

et cette congruence remplace maintenant les deux premières x = a

kl d

AB (mod A), a; = /? (mod B) On remarquera que le module ~t- est bien le

p. p. c. m. de A et B.

On pourra combiner maintenant la congruence

avec la troisième

x^E^y (mod C) ,

et ainsi de suite. Il est clair qu'on arrivera de cette façon toujours , soit à s'assurer que le problème est impossible , soit à trouver la solution sous la forme

x^a (mod M) si elle existe.

Cette méthode , toutefois , a l'inconvénient de ne faire souvent connaître l'impossibilité du problème qu'après de longs calculs qui ont été inutiles alors On ne peut remédier à cet inconvénient qu'en donnant le moyen de reconnaître a priori la possibilité ou l'impossibilité du problème. C'est là l'objet du théorème suivant:

Théorème III. — Pour que le système des congruences

a3 = a (mod A), a; = /9 (modB), ..., xehA (modL) admette des solutions, il faut et il suffit que les différences

a — p, a — y, ji — y, ..., x — l soient divisibles respectivement par

(A,B), (A,C), (B,C), ..., (K.L). Que ces conditions sont nécessaires, cela est clair d'après ce qui

précède. Pour montrer qu'elles sont suffisantes , nous supposerons que la proposition est exacte dans le cas de n — 1 congruences , et ferons voir qu'elle est alors exacte aussi dans le cas de n congruences. Puisqu'on sait que, dans le cas n^2, le théorème est vrai, il sera ainsi démontré généralement.

En effet, la proposition étant vraie pour n — 1 congruences, on pourra remplacer les n — 1 premières congruences par celle-ci

» = < (modM') et le système complet par

(1) . ■ x^Et (modM'), xeebX (mod L).

Ici M' = [ A, B, C, . . . , K |. Or, d'après notre hypothèse ,

A — a, X — ^, ..., X — x sont divisibles par

(L,A), (L,B), ..., {L,K) respectivement, et il est clair que

a — t, P — t, ..., X — t sont divisibles par A, B, C, ..., K respectivement, donc aussi par (L, A), (L, B), . . . , (L, K) respectivement. On voit par là que la différence

X — t est divisible par (L, A), par (L, B), . . . , par (L, K) et, par conséquent, aussi par le p. p. c. m. de ces nombres qui est (L, M') (Chap. I, n" 11). Mais cette divisibilité de A — t par (L, M') est précisément la condition nécessaire et suffisante pour que les congruences (1) et par là aussi les congruences proposées admettent une solution.

On peut démontrer ce théorème aussi en faisant voir qu'il y a exacv tement M systèmes de résidus a, (i, . . . , X qui satisfont aux conditions exigées.

15. On peut réduire le cas général au cas où A, B, . . . , L sont premiers entre eux. Pour cela , mettons le p, p. c. m. M des modules sous

la forme

où A', B', C, . . . , L' sont premiers entre eux et divisent respectivement A, B, C, . . . , L (Chap. I, n°' 18, 19).

Il est clair que les solutions du problème proposé satisferont aussi aux congruences

x = a (mod A') , a; EEi /S (mod B') , . . • , rc = A (raod L') ,

mais ce dernier système admet , nous le savons , toujours des solutions renfermées dans la formule

a; = a (mod M).

Si donc on s'est assuré préalablement que le problème proposé admet des solutions, ces solutions sont encore renfermées dans la formule précédente. Mais, si l'on ne savait pas si oui ou non le système proposé admet des solutions, cette valeur x^z^a (mod M) pourrait ne pas satisfaire aux conditions imposées , qui seraient alors incompatibles. Considérons , par exemple , le système

a;= 31 (mod 72 = 23.32),

a;= 22 (mod 105 = 8.5.7),

x= 50 (mod 77 = 7.11),

a; = 387 (mod 899 = 8.7.19).

On a ici M = 23.32. 5. 7. 11. 19 = 526680 et ABCD:M = 441. Donc, si les résidus 81, 22, 50, 887 avaient été pris au hasard, il n'y aurait qu'une chance sur 441 que le problème soit possible. Il convient donc de s'assurer d'abord si le problème est possible ou non. Or, les nombres

étant divisibles respectivement par

8, 1, 3, 7, 21, 7, le problème est possible. La décomposition de M

M = 72 X 35 X 11 X 19 permet maintenant de remplacer les congruences données par celles-ci

»= 31 (mod 72),

a;= 22 (mod 35),

XE^ 50= 6 (mod 11),

a; = 387 = 14 (mod 19).

En appliquant maintenant la méthode de Gauss , les nombres auxi liaires a', /?', y', ô' se déterminent par les congruences

35. 11. 19 a' = 43 a' ES 1 (mod72), 72.11.19/?' = — 2 /?'.-; 1 (mod35), 72.35.19>''= 8^'=! (modll), 72.35.11^'^— ^'=^1 (modl9), d'où

et, finalement,

+ 17.72.11.19.22 (mod 526 680), + 7.72.85.19. 6 — 72.35.11.14

x = 323 527 (mod 526 680).