AB
a; = a + Aj/o (mod-^j.
et cette congruence remplace maintenant les deux premières x^=a
AB (mod A), a; = j8 (mod B) On remarquera que le module ^ est bien le
p. p. c. m. de A et B.
On pourra combiner maintenant la congruence
ic^a + Aî/o (mod-^-j
avec la troisième
x^^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
Xz^a (mod A), a; = /î (modB), ..., x^^X (modL) admette des solutions, il faut et il suffit que les différences
a — p, a — y, (i — y, ..., }c — X 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
xs^t (modM') et le système complet par
(1) x~t (modM'), x^k (modL).
Ici M' ^ A , B , C , . . . , K |. Or , d'après notre hypothèse ,
l — a, A — /9, . . ., k — x sont divisibles par
(L,A), (L,B), ..., (L,K) respectivement, et il est clair que
a~t, ft — t, ..., i — 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
l — 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 exactement M systèmes de résidus «, /S, . . . , A 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'MS, 19),
Il est clair que les solutions du problème proposé satisferont aussi aux congruences
x^a (mod A') , a; = /S (mod B') , • • . , xE^k (mod L') ,
mais ce dernier système admet , nous le savons , toujours des solutions renfermées dans la formule
rc = 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 rc==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 = 3.5.7),
a;= 50 (mod 77 = 7.11),
XEE^SSl (mod 399 = 3.7.19).
On a ici M = 2^.32. 5. 7. 11. 19 = 526680 et ABCD : M = 441. Donc, si les résidus 31, 22, 50, 337 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
le problème est possible. La décomposition de M
permet maintenant de remplacer les congruences données par celles-ci
a;= 31 (mod 72),
33= 22 (mod 35),
a;~ 50= 6 (mod 11),
a; = 337 = 14 (mod 19).
En appliquant maintenant la méthode de Gauss, les nombres auxi liaires a', fi', y', ô' se déterminent par les congruences
35, 11. 19 a' = 43 a' =1 (mod72), 72.11.19/Î'es— 2/?'£EEl {mod35), 72 . 'à5 . 19 y' E^ Sy'FEil (mod 11), 72.35. Il <5' = — ô'^l (mod 19), d'où
et, finalement,
+ 17.72.11.19.22 (mod 526 680), + 7.72.85.19. 6 — 72.35.11.14
a; = 323 527 (mod 526 680).
