AE EN

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+ pb exige qu'on ait ax —ay où 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 (&, 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

0 [mal |

: a M : Un Puisque à et 4 sont premiers entre eux, nous savons qu’il existe une

a b TRE |

seule racire par rapport au module + Soit x, cette racine, l’ensemble

des valeurs de x qui satisfont à la question est comprise dans l’expression

M To + Y mOi ds che nous

Mais il est clair que, suivant le module M, ces nombres se répartissent en d classes, car les d nombres

M M M M Lo; % + g” Go +2) +3; .., %+(4—1T

sont incongrus suivant le module M, mais un nombre quelconque

Lo + — est congru, suivant le module M, avec un de ces d nombres.

Théorème I. — La congruence ax + b—0 (mod M) est possible seulement lorsque b est divisible par d = (a, M). Si cette

condition se trouve satisfaite, elle admet exactement 4 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 pre-

miers 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 =] (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—My=l.

On développe en fraction continue le rapport M : « 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,N,, N,,... liés par les relations N —a@N +N:, N, —æN+N;, D. Hem, SAN, (Nr: =0axNr + Nxt:,

alors on peut exprimer successivement N par N, et N,, par N, et N:,...,

N=aN; + N;, N—={(a a +1)N, + a, N3, N — (a, @ a3 + & + 3) N3 + (id + D N,,

Introduisons un symbole L@is Mes .. Gxl, déterminé par les relations

[a] =, La do] = 4 +1, [u.@,...,ax]—={[@; @o,...,@n 1]@x+-[@,@,...,ax-0],

alors on aura généralement (8)... . N=[a,,@,..., ii +IG, M. 08 LR Il est clair qu'on aura aussi

N;, = [@, a3, ..., Gx] Nx + [ao gs ee. Gk—1]Nxti, No — [az ..., ax] Nr + Las, ..., ax—1]Nx+:;

et, si l’on substitue ces valeurs dans la première relation (1), on obtient une expression de N par N4 et N;+1 qui doit être identique avec (3). D'où l’on conclut

(4). farm, ss means lie... il

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 dl, tal los, ii is ml En joignant à l’équation (3) celle-ci | ÉORPEN N; —[ü, gp.) ax] Ne + La, Ags +.) ax—1] Ne+1, on a deux équations ; d'où l’on pourra tirer la valeur de N; en fonction de N et N,. Mais cette valeur s'obtient aussi directement, car on obtient de proche en proche

+N=N—-aN,,

+ Nil, a3]N —[a,, a, as] N;,

Généralement, (7) . . —IDÉNZ=l@, 08, ..., 4u 1]N —[a,@,...,ax 1]N.. En comparant cette valeur de N; avec celle tirée de (3) et (6), on a (8) Las, @, …, ax] X TG, Ass vo Gr —1]—[@, do, …, @x 1] XTQo. dy, ax] —=(—1Y. Ce sont là les formules dont nous aurons besoin; nous en donnons encore quelques autres qui sont quelquefois utiles. On a Nx —[ax+1, ax+,..., Gr] Neyi + [@x+1, ..., Ami 1]Nxtus, Net —{ax+e, ..., 4x+4i] Nxyi + Lax+e, ..., xt 1] Nepita. Substituant ces valeurs dans (3), on a l’expression de N par N:1, et

Nx+141, expression qu’on peut obtenir aussi en remplaçant 4 par k +} dans la même formule. On trouve, par comparaison,

Qi, Gil —=[a;, ds, ..., ax] X{[@x+1,...,ax+i] +[a, Up, 4x—1]X[ax+0,...,@rx+1]. Enfin nous ajouterons la relation suivante mi D... 0.50, 0,,..,41X 0, be... b]— —[m,...,0:0,,...,0] X[b,...,bs; &,...,c] = =(—1l})'{a,æ,...,a 1] X[@,c,...,0ce]

qui, pour r—={—1, reproduit la formule (8) et, pour s—0, la formule (9).

10. Pour appliquer ces relations à la solution de l’équation ax—My=lil,

on prendra N—M,N,—a. Comme ces nombres sont premiers entre eux, on finira par trouver N;—=1, N;+;1—0,de manière qu'on ait

M —{a;, 0, se ax],

a—[as, ..., ax], (— 1} —=[a,a3,..., 4x1] X M—[a,@,...,ax-1]X a. On peut donc prendre x—=(—1)#—1[a,æ,...,a@x 1], y=(—1}# 1m; e,. 2.5: 1]

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 ax — 1 et 1, de manière que le nombre total des quotients est à VOIOnÉE pair ou impair. Il est à peine besoin de dire que

Hilo 1 __[a; Moses x] a se :

Las, :, ,@x] — SE

On voit sans peine que, &,, y, étant une solution particulière de ax —My—=l, la solution la plus générale sera renfermée dans les formules z—%o + Mt) y=Yy+at| 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 con-

dition est satisfaite, il y a toujours une infinité de solutions. Soit x,, y, une solution particulière, la solution la plus générale sera

É=0 + +82 a en:

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 (mod A), x—=B (modB), æ=7y (modC), ..., æx—71 (mod L), 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

to + Mt En +i,E£5,.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

SE DER CAT pee

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

x = 4 (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 —1 ne 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

Pr 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, à 8 B valeurs, etc., en sorte que le nombre total des systèmes de résidus possibles est M.

En divisant donc les nombres on, La. ns 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 IT. — Les modules A,B,C,...,L étant premiers entre eux, le système des congruences

æ—a (mod A), #8 (modB), des æ—=À (mod L) admet toujours des solutions, renfermées toutes dans la formule x—a (mod M), où M—ABC...L.

12. Lorsque les modules A, B,C,...,L ne sont pas premiers entre eux, M est plus petit que le produit A BC...L.

Or il y a toujours A,B,C,..., L systèmes de résidus possibles (si l’on prend a, 8, y,..., arbitrairement). Mais le problème ne sera possible que si le système a, B, y, ..., 1 se trouve parmi les M systèmes de résidus qu’on obtient en divisant les nombres

DOS NN 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, B,..., À satis-

fassent à certaines conditions que nous énoncerons plus bas. Mais toujours, lorsque le problème est possible, la solution est donnée par une

formule z=a (mod M).

13. Revenons au cas où A,B,C,...,L sont premiers entre eux pour voir comment on obtiendra la solution x == (mod M). Puisqu’on doit avoir x = a (mod A), on posera

æ—=a+AYy, et il viendra

La première congruence donnera

y=Y+Bz, 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’, B',... 1 par les congruences ACDi.ibats (mod A), AOD: .. LP — (mod B), ABD...Ly = (mod C),

alors on aura

LABC...Ki1 (modM—ABC...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, B,..., 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,B,...,4, les modules A,B,...,L restant les mêmes. Les mêmes nombres a’, B',..., 4 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

æ— a + À y, et la seconde congruence deviendra

Ay=B—a (modB).

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

B Y=Y+ at ((=0,+1,+2,...) et, par conséquent, z=a+AY% (mod $e)

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

(mod A), x—B (mod B) On remarquera que le module — est bien le

p, p.c..m.de A'etB.

On pourra combiner maintenant la congruence x—=a+AY% (mod +) 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 Ja 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 æ—a (mod A), — ff (modB), Vs x==À (modL) admette des solutions, il faut et il suffit que les différences ad—p, a—7y, B—7y, ..., x —À soient divisibles respectivement par (A,B), (A,0), AB, Obs 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

T = (mod M’)

et le système complet par vue senrsrous sui : LIN0û N°), æz—=À (mod L). Ici M=|A,B,C,...,K|. Or, d'après notre hypothèse,

RD PO 0 Pop sont divisibles par

ŒiAe -g Bi ss. Li, K) respectivement, et il est clair que

a—t, Bt, ..., 4 —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 1—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 2 — + 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 exac-

tement M systèmes de résidus a, B,...,1 qui satisfont aux conditions exigées, 15. On peut réduire le cas général au cas où A, B,..., L sont pre-

miers entre eux. Pour cela, mettons le p. p. c. m M des modules sous la forme

HA B'C'..4, où À’, 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

æ—a (mod A’), —# (mod B/), Ses æ—=À (mod L’),

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

t=à (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 = a (mod M) pourrait ne pas satis-

faire aux conditions imposées, qui seraient alors incompatibles. Considérons, par exemple, le système

x—= 81 (mod 72 — 2,82), — 22 (mod 105 = 8.5.7), xæ—= 50 (mod - 77 = 7.11), x = 337 (mod 399 — 3.7.19).

OnaiciM—2.%.5.7.11.19 — 526680 et A BCD : 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

9, 19, 306, 28, 315, 287 étant divisibles respectivement par ds 4 ET, 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

x—= 81 (mod 72), x—= 22 (mod 35), xæ= 50—= 6 (modl1il), x—337—14 (mod 19).

En appliquant maintenant la méthode de Gauss, les nombres auxi liaires a’, B/, y’, 9’ se déterminent par les congruences