Problème. — Résoudre la congruence du premier degré

axXi -4- ajjr, 4-. . .4- anX^'^b (mod.p).

Cette congruence revient à l'équation indéterminée

(l ) pX -4- a.jr, -f ttiXi -h ... -4- QnOl^n = b.

Soit a< le plus petit des nombres /?, a,, a^,,...; et soit p = a^m'^ p\ a^ = a^m^-^- d^^...^p\ a^,... étant les restes minima de la division de

i LIVRE PREMIER.

p, aa,... par a^% Posons

X| = X, -4- mx -h ITliXi -+-...,

jc\ étant une nouvelle indéterminée; il vient

p'x -4- aix\ -4- a\x2 -f- . . . = 6,

équation analogue à la précédente, mais avec des coetlicients plus petits. Si p\à^,... ne sont pas tous nuls, on répétera ce procédé; et il est clair qu'on parviendra enfin à une équation

où tous les coefficients soient nuls, sauf un seul, d. D'ailleurs, il est évident que Pf ai, a^,... ont le même plus grand commun diviseur que p\ a^, a,,...; de même k chacune des réductions suivantes : donc d sera ce plus grand commun diviseur. S'il ne divise pas ^, l'équation (2) sera impossible :

mais s'il le divise, on aura ^ = ^î et l'on aura x, a?!,..., Xn exprimés en

fonction linéaire de z et des n indéterminées affectées de coefficients nuls dans l'équation (ii), lesquelles restent arbitraires.

Remarque. — La congruence ax^b (mod. p) est toujours résoluble, d'après ce qui précède, si a est premier kp. Soient x, xl deux de ses racines : a{xi— x') sera divisible par/?; donc a? = a?'-h A/?, k étant entier. Parmi les nombres de cette progression, il en est évidemment un, et un seul, qui

soit </? et non négatif. Nous le désignerons par le symbole - (mod. p).

Congruences de degrés supérieurs.

3. Les congruences les plus intéressantes sont celles dont le module est un nombre premier. Nous les considérerons exclusivement dans ce qui va suivre, à moins que nous n'avertissions expressément du contraire.