Revenons maintenant à la congruence

ax -\-a'^0 (mod. 6),

en ne supposant plus les nombres a et 6 premiers entre eux; soitd leur plus grand commun diviseur.

On veut trouver un nombre entier x tel que ax + a' soit un multiple de 6 : s'il en est ainsi, ax + 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 a' n'est pas divisible par d, le problème est impossible. Supposons donc a' divisible par d, et soient, pour abréger,

a = fljcf, b == 6,(f, a' = a\dy

ai, 6i, a[ étant des nombres entiers, a^ et 6j étant premiers entre eux. On veut trouver un nombre entier x tel que le produit d{aiX + a\) soit divisible par dbi ; il faut et il suffît, pour cela, que le nombre a^x + a[ soit divisible par bj, c'est-à-dire que x soit une racine de la congruence du premier degré

a^x -f «', ^ 0 (mod. 6,),

dans laquelle a^ et 6i sont premiers entre eux; cette congruence admet des solutions : si Xq est une solution, toutes les solutions de cette congruence, et par suite de la congruence proposée, seront données par la formule.

x = Xq 4- w6j,

où m est un nombre entier quelconque.

Si l'on donne à m la suite des valeurs entières, l'expression x^ + in6, prendra une suite de valeurs entières, les restes, relativement au module 6, se reproduiront périodiquement de d en d {n" 503), les restes différents correspondront à d valeurs attribuées à ni et incongrues entre elles suivant le module rf, par exemple, aux valeurs, 0, 1 , 2, ..., d — i ; par conséquent, si les nombres entiei^s a, b admettent d comme plus grand commun diviseur, la congruence

a,r + 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 6, à savoir, en désignant par Xq l'une de ces solutions,

^0» ^o + j' OTo + 2 ^, ..., Xq+ (d—i)^'

On déduit de là les conclusions suivantes :

L'équation du premier degré à deux inconnues Xj y et à coefficients entiers a, 6, c,

. nx + by + e = 0, ..

n'admet pas de solutions si le nombre c n'est pas un multiple du pins

^rand commun diviseur dde a^ b; si c est divisible par d, elle admet. des

solutions : si Xq, Vq forment une de ces solutions, celles-ci seront toutes

données par les formules

ou m est un entier quelconque. ...

511. 11 résulte de là que si d est le plus grand commun diviseur des deux entiei's a, 6, il existe deux entiers x, y, positifs ou négatifs, tels que Ton oit

aJû + by = d.

Cesi 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 Ton n'avait pas craint, alors, d'employer des nombres négatifs.

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

a=zbq + r.

qui expriment les résultats des divisions successives qvie Ton effectue. Supposons que r» soit le plus grand commun diviseur de a et de b. On tire de la première égalité

r = a — bq;

il existe donc deux noinbres Xq= 1, y^ = — q tels .que Ton ait

De la seconde égalité on lire

et en remplaçant dans le second membre r par oXq +, 6^0» on voit qu'il existe deux entiers

«i = — ^1^0» yi = i— Mo tels que Ton ait

r, = ojpj + 6yj.

Le raisonnement se conihmé évidemment, et, finalement on voit qu'il existe deux entiers »„ , y» tels que l'on ait

4ix„ + byn^rn: ■. • -

TA3(XEET. 30

466 LEÇONS D*AR1THMÉTIQU£.

c^est ce qu'il fallait démontrer. En particulier, si a, 6 sont premiers enlre eux, on voit ainsi qu'il existe deux entiers x, y tels que l'on ait

ax + by= \,

et Ton a, dans ce qui précède, un moyen régulier pour trouver ces deux nombres.

Afin de montrer l'utilité du théorème qu'on vient d'établir, je vais en tirer une démonstration nouvelle de la proposition fondamentale du n'142: « Si a, 6 sont premiers entre eux, les diviseurs communs de a et de c sont les mêmes que ceux de a el de bc. »

il suffit, comme on l'a déjà fait observer, de montrer que les diviseurs communs de a et de 6c divisent c : or, ayant déterminé les nombres x et y tels que l'on ait

ax-^ by =: 1,

on obtient, en multipliant les deux membres par c,

acx + 6cy = c,

et il est clair que tout nombre qui divise a et 6c, divisant les deui parties du premier nombre, 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 propositions du n» 500.

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

A^B (mod. 6).

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

A = A|a, B = BjO, ^ a = ajd, 6 = b^dy

A|, Bj, fft, 6i étant des nombres entiers dont les deux derniers sont premiers entre eux. Par hypothèse, A — B= ajd(Aj — B,) est un multiple de 6 = 6,cf; par conséquent a,(Aj — Bj) est un multiple de 6j et, comme 6, est premier à «1, il faut qu'il divise Aj — Bj ; par conséquent, la congruence

A = B (mod. 6)

entraine la congruence

- (mod. -Aa \ dj

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