La congruence du premier degré
(i) ûx-h^^o (mod.M'l
peut se mettre sous la forme
(2) ûx -h ^ = M/,
et la recherche de ses racines est ramenée à celle des solutions en nombres entiers de l'équation (2) qui renferme les deux inconnues xely. Si a et M sont premiers entre eux y réquation(2) est toujours résoluble en nombres entiers; on obtient une première solution Xo, y^ (n** 13)
par la réduction de — en fraction continue ; après quoi
toutes les solutions sont données par les formules
où t désigne une indéterminée. On peut disposer de cette indéterminée de manière à obtenir une valeur de x comprise entre zéro et M, et, si Ton représente cette valeur par Xo, les autres valeurs de x continueront à être données par la première des formules qui précèdent.
Il résulte de là que la congrucnce du premier degré ( i ) n'admet qu'une seule racine, quel que soit le module, lorsque le coefficient de l'inconnue est premier avec ce module.
On arrive à la même conclusion au moyen du Icmme du n"" 283 (Corollaire). Effectivement, si l'on donne à X les M valeurs
le premier membre de la congruence (i) prendra M valeurs incongrues suivant le module M; l'une de ces
SBCTIOIf III. CHAPITRE I. I7
valeurs sera donc nulle , relativement à ce module, et la valeur correspondante de x sera la racine demandée. Si Xo désigne cette racine, on peut écrire
^0^ (mod. M],
comme Gauss Ta pro'posé.
Si le coefficient a n*est pas premier avec le module M et que d désigne le plus grand commun diviseur de ces deux nombres, la congruence (>) ne sera résoluble que si b est divisible par d. Quand il en est ainsi, la congruencCi divisée par d, devient
on rentre alors dans le cas que nous venons d'examiner.
Soit Xq la racine de la congruence (3) ; les valeurs de x
qui pourront y satisfaire seront toutes comprises dans la
formule
et Ton voit que la proposée admettra les d racines
qui sont incongrues suivant le module M.
289. Lorsque le module M est un nombre composé , la résolution de la congruence
(i) «jr-h^EEso (mod. M),
où l'on suppose a premier avec M, peut être ramenée à celle d'autres congruences dans chacune desquelles le module est un facteur de M.
S. — Alg. sup,, u. a
i8 cocRS d'algèbre supérieurs.
Soit, en effet,
M = Mt M„
M| et M9 étant des nombres entiers.
Il est évident que la racine de la congruence (i) doit satisfaire à la congruence
(2) ax-^b^o (mod.'Mi);
désignons par a la racine de cette congruence : les valeurs de X qui satisfont à la proposée seront de la forme
jr==a -f- M| X,.
X| étant une indéterminée, et en substituant cette valeur il viendra
(fla-h ô) 4- Mt o.r, E=o (mod. M).
Par hypothèse, aa -H i est divisible par M| ; si donc on
pose
/la -4- A ,
la précédente congruence, divisée par M|, deviendra
axx -+- ^|Ei^o [raod. M,).
Si Ton désigne par a^ la racine de cette nouvelle congruence, la formule
donnera la racine de la proposée.
On concbit de là que, si Ton a
M = M, M, . . . Mjt,
M|, M), •••, Mji étant des nombres entiers, la résolution de la congruence
ax -^ b^i^o (mod. M)
SECTiOlf III. — chapithe I. ig
peut être ramenée à celle d'autres congruences de la forme
ax-{-b ^o (mod. M|), «jT-f-è, =H0 (mod. Mt),
a jr -h 6jt i ^ o (mod. Mjt].
En particulier^ on peut prendre pour les nombres M|, M2, ... les facteurs premiers dont le module est le produit.
Exemple. — Soit la congruence
1237J? — 4^96^0 (mod. 675).
Le module 675 est égal au produit 27 X ^5 ; on peut donc commencer par résoudre la congruence
1237J7 — 4^96^0 (mod. 27),
qui y en rabaissant les coefficients au-dessous du module,
devient
Sx — 8^0 (mod. 27),
ou, si Ton veut,
La valeur^ = i donne x = 7 ; on fera, en conséquence,
jf = 7 -f- 27 xj ; en substituant cette valeur, la proposée devient
1287 >; 27x1 4- 4563 ==0 (mod. 27X^5), ou, en divisant par 27,
1287x1 -h 169^1=0 (mod. 25);
rabaissant les coefficients au-dessous du module 25, on
obtient
12x1 — 6^0 (mod. 25)9
OU, en divisant par 6, qui est premier avec le module,
axi — iE==o (mod. a5).
On tire de là
