Revenons maintenant à la congruence ax +a!=0 (mod. b

en ne supposant plus les nombres «a et b premiers entre eux; soit d leur plus grand commun diviseur.

On veut trouver un nombre entier æ tel que ax + a! soit un multiple de b: s'il en est ainsi, aæ + a’ sera un multiple de d; or d divise a et par suite ax; il devra donc diviser a'. D'où cette première conclusion: si 4! n’est pas divisible par d, le problème est impossible. Supposons donc «! divisible par d, et soient, pour abréger,

4 —"4d, b = bd, Mate VU

di, di, & étant des nombres entiers, a, et b, étant premiers entre eux. On

veut trouver un nombre entier æ tel que le produit d(ayx + a,) soit divi-.

sible par db,; il faut et il suffit, pour cela, que le nombre ax + a soit divisible par b,, c’est-à-dire que æ soit une racine de la congruence du premier degré

| ax +a—=0 (mod. b,),

dans laquelle a, et b, sont premiers entre eux; cette congruence admet des solutions: si x, estune solution, toutes les solutions de cette congruence, et par suite de la congruence proposée, seront données par la formule.

T= Lo + Mb,

où m est un nombre entier quelconque.

Si l’on donne à m la suite des valeurs entières, l'expression æ, + mb,

prendra une suite de valeurs entières, les restes, relativement au module b, se reproduiront périodiquement de den d (n° 503), les restes différents

correspondront à d valeurs attribuées à = et incongrues entre elles suivant.

le module d, par exemple, aux valeurs, 0,1,2,...,d— 1; par conséquent, si les nombres entiers a, b admettent d comme ps grand commun diviseur, la congruence

ax + a =0 (mod.b)

n’admettra pas de solution dans le cas où a’ n’est pas divisible par d; si a!

est divisible par d, elle admettra d solutions, incongrues suivant le module b, à savoir, en désignant par x, l’une de ces solutions,

b b | b To» Bo + à To + 2 FAURE Lo + (d—1)3;

On déduit de R les conclusions suivantes :

L'équation du premier degré à deux inconnues x, y et à coefficients entiers 4, b, c, ax + by + c—0,

n'admet pas de solutions si le nombre © n’est pas un multiple du plus grand commun diviseur d de a, b; sic est divisible par d, elle admet des solutions : si &, y, forment une de ces solutions, celles-ci seront toutes données par les formules 2= 2 + me, Y = Yo — mn

où m est un entier quelconque.

511. Il résulte de là que si d est le plus grand commun diviseur des deux entiers a, b, il existe deux entiers +, y, positifs ou négatifs, tels que l’on ait.

ax + by = d.

C'est là une proposition importante d’Arithmétique. Elle résulte très. facilement, comme on va le voir, de l’algorithme d'Euclide; elle aurait trouvé sa place dans le chapitre IV, si l’on n'avait pas craint, alors, d'employer des nombres négatifs.

Si l’on cherche, en effet, le plus grand commun diviseur des nombres. a, b, on est amené à une suite d’égalités telles que

a=dbgq+r, b=rm Er,

P = Tig2 + Ta

Te = Tn—1In Pre Th ,

qui expriment les résultats des divisions successives que l’on effectue. Supposons que 7} soit le plus grand commun diviseur de a et de b. On tire de la première égalité

r= à — bg; il existe donc deux nombres #5 = 1, yo = — q tels que l’on ait T = 4%) + 0Yo.

De la seconde égalité on tire ri = 0 — qi,

et en remplacant dans le second membre » par ax, + by,, on voit qu’il existe deux entiers

Bi = — lo Yi—= 1 — GiYo tels que l'on ait

ri = 421 + by.

Le raisonnement se continue évidemment, et, finalement on voit qu’il existe deux entiers æ, , y" tels que l’on ait

Th + 0Yn = Th :

VA One UE VAT Va pe PS RE ER Vi SE NE SR ENT de LES ET ER CAT AN SOIT IT RERO PAR PNA

c'est ce qu'il falaie den nn En particulier, si 4, b so premiers entre eux, on voit ainsi qu'il existe deux entiers x, y tels que l'on at

ax + by = 1,

et l'on a, dans ce qui ce un moyen régulier pour IrobRee ces deux +

nombres. | |

Afin de montrer l'utilité du théorème qu’on vient d'établir, je vais ob. su ürer une démonstration nouvelle de la proposition fondamentale du. n°142: « Si a, b sont premiers entre eux, les diviseurs communs de a et de c sont les mêmes que ceux de a et de be. »

I] suffit, comme on l’a déjà fait observer, de montrer que les diviseurs communs de a et de bc divisent c : or, ayant déterminé les nombres x et y tels que Fon ait

ax + by —= = on obtient, en multipliant les deux membres par c,

acæ + bcy = c,

“et il est clair que tout nombre qui divise a et bc, divisant les deux parties du premier membre, divise aussi le second.

512. Observons, en passant, qu’un raisonnement semblable à celui qu'on a développé dans l’avant-dernier numéro permet de compléter les Propost tions du n° 500.

Soient A, B deux nombres entiers tels que l’on ait

A =B:" (mod. à

Supposons que les deux nombres A, B admettent un diviseur commun 4, et soit d le plus grand commun diviseur de a et de b. Posons pour abréger :

At A,a, b=— B,a, (1 Ag on 4, = b — bd, Ve:

A,, B4, &, d, étant des nombres entiers dont les deux derniers sont premiers entre eux. Par hypothèse, A— B— a,d(A,—B,) est un multiple de b—b,d par conséquent a {A,;—B;) est un multiple de b, et, comme b, est pre-

mier à @4, il faut qu’il divise A; — B;; par conséquent, la congruence

A = : (mod, où

En particulier, si la division peut se faire exactement, on peut diviser par un nombre premier au module les deux termes d’une congruence.

entraine la congruence

2”. Te 1 Li fé.

LS d "1

ne à