Revenons maintenant à la congruence

ox + a' = 0 (mod. 6),

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

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

a = ajrf, b = b^dy a' = a\dj

a,, ôj, a[ étant des nombres entiers, aj et 6, étant premiers entre eux. On veut trouver un nombre entier x tel que le produit d(aiX + a,) soit divisible par (f6| ; il faut et il suffit, pour cela, que le nombre aiX + a[ soit divisible par 6|, c'est-à-dire que « soit une racine de la congruence du premier degré

a^x + «1 ^ 0 (mod. ôj),

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

où m est un nombre entier quelconque.

Si Ton donne à m la suite des valeurs entières, Texpression Xq -{- m6| 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 à m 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, 6 admettent d comme plus grand commun diviseur, la congruence

a.r 4- a' = 0 (mod. 6)

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,

On déduit de là les conclusions suivantes :

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

ax -\- by -\- c = Oy

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

grand commun diviseur d de a, 6 ; 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

a? = Xo + «ig. y=yo— w^'

où m est un entier quelconque.

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

ax + by = d.

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

Si l'on cherche, en effet, le plus grand commun diviseur des nombrei a, 5, on est amené à une suite d'égalités telles que

a = bq {- r, b=rq^-i- f\,

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

r = a — bg;

il existe donc deux nombres x^— 1 . f/o = — Q tels que l'on ait

r = uxq 4- %o-

De la seconde égalité on tire

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

a?i = — ^i-To, 2/1 = 1— gi2/o tels que Ton ait

r^^axt -(-bj/j.

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

(t^n + byn = r„ :

Tanniry. 30

c'est ce qu'il fallait démontrer. En particulier, si a, 6 sont premiers entre eux, ou voit ainsi qu*il existe deux entiers x, y tels que Ton ait

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

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

11 suffit, comme on Ta déjà fait observer, de montrer que les diviseurs communs de a et de 6c divisent c : or, ayant déterminé les nombres x eiy tels que Tou ait

on obtient, en multipliant les deux membres par c,

acx + bcy = c,

et il est clair que tout nombre qui divise a et 6c, 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 propositions du n* 500.

Soient A, B deux nombres entiers tels que Ton 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|, Bj, a„ 6i étant des nombres entiers dont les deux derniers sont premiers entre eux. Par hypothèse, A— B= a,rf(Ai — B,) est un multiple de 6=6,d; par conséquent a4(A,— Bj) est un multiple de 6, et, comme 6i est premier à Oj, il faut qu'il divise Aj — Bj; par conséquent, la congruence

A = B (mod. 6) entraîne la congruence

\ (mod. ^).

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

THÊOKËME DE FERMAT. 467

§ 3. — Nouvelles Gonséqaences de la périodlGlIé des restes. Théorème de Fermât.

613. Développons maintenant d'autres conséquences de la périodicité des restes, relatifs au module 6, de la suite des multiples

d'un nombre entier a.

Supposons a et 6 positifs et a < 6.

Imaginons un cercle dont la circonférence soit divisée en 6 parties égales et supposons que, en parcourant la circonférence dans un sens déterminé, on ait placé, sur les points de division, les numéros 0, j, 2, ..., 6— I, puis que, en marchant dans le même sens. Ton joigne ces points de division de a en a par des droites, en partant du point marqué 0; on joindra ainsi successivement les points dont les numéros sont respectivement

tant que ces nombres sont intérieurs à 6; mais dès qu'ils deviennent égaux ou supérieurs à 6, les termes de cette suite, doivent être remplacés par leurs restes (mod. b).

D'après les résultats qui précèdent, on voit que le premier point par lequel, en continuant de cette façon, on passera une seconde fois, sera le point 0; en d'autres termes, c'est au point 0 que la ligne brisée, décrite de cette façon, se fet^me.

Si a est premier à 6, les restes successifs seront, dans un certain ordre, les nombres 0, i, 2, ..., 6 — 1 ; 0 sera le premier de ces restes; avant de retrouver le reste 0, il faudra avoir trouvé les restes 1, 2, ..., b — 1 ; on passera donc par tous les points marqués avant de fermer la ligne brisée ; quand elle se fermera, elle aura b côtés.

Au contraire, si a n'est pas premier à 6, les restes successifs seront, dans

lin certain ordre, les nombres 0, d, 2ii, ..., 6 — c/, il y en aura -| de différents ; le premier sera 0 et on retombera sur le reste 0 ou sur le point iijarqué 0, dès que Ton aura passé par tous les points 0, d, 2rf, ..., 6 — d ;

la ligne brisée, quand elle se fermera, aura -^ côtés.

Les ligures fermées que l'on forme ainsi sont étudiées, en Géométrie, sous le nom de polygones réguliers (convexes ou concaves) : on forme celles qui ont 6 côtés en divisant la circonférence du cercle en 6 parties égales ot en joignant les points de division de a en a, a étant un nombre premier à h et inférieur h b; il est clair qu'on obtient la même figure en joignant les points de division de a en a ou de 6 — a en 6 — a ; d'ailleurs, si a est premier à 6, il en est de même de 6 — a et inversement ; le nombre des

figures distinctes que Ton pourra former ainsi est donc la moitié du nombre de nombres premiers à 6 et inférieurs à b,

514. Théorème de Fermât. — Soit p un nombre premier absolu et a mi entier non divbiblepar/),a sera premier à p; par conséquent, les nombres a, 2a, ..., (p — 0« seront, dans leur ensemble, congrus (mod. p) aux nombres 1, 2, ..., p — 1 ; donc, relativement au même module, le produit

aX2aX3aX... X(p — l)a

est congru au produit iX2X3X... X(p — i); la différence entre ces deux nombres, c'est-à-dire

a'-'Xl.2.3...(p-l)-1.2.3...(p-l) = (a^-'-l)Xi.2.3...(p-i),

est divisible par p, mais le nombre premier p est premier avec chacun des. facteurs «, 2, 3, ..., P — 1 et, devant diviser le produit de ces nombres par a** ~ * — 1, doit diviser ce dernier facteur ; donc :

Si p est un nombre premier et a un entier non divisible par p, a**" '— 1 est divisible par p; en d'autres termes encore, on a

a^-^^i=0 (mod.p).

Par exemple, 2** — 4 = 4095 est divisible par 13 ; le quotient est 315. Cette proposition, qui est capitale dans la théorie des nombres, est due à. Fermât.

On peut l'énoncer un peu autrement ; la congruence

a^^-*— 1 =-0 (mod.p),

qui a lieu pourvu que a ne soit pas divisible par le nombre premier p, entraîne la suivante :

a'' — a — 0 (mod.p).

Off-celle-ci est vraie quand a est divisible par p; elle est donc vraie quel que soit l'entier a.

515. Généralisation. — Euler a généralisé le théorème de Fermât; la démonstration de la proposition à laquelle il est parvenu est toute pareille à la précédente.

Supposons a et 6 premiers entre eux. Si « est un entier quelconque, on sait que le plus grand commun diviseur de ouz et de 6 est le même que colui de b et du reste de «a par rapport au module 6. C'est aussi le même (n" i42) que le plus grand commun diviseur de * et de 6; par conséquent, le reste de «a, par rapport au module 6, sera premier à 6 si « est premier à 6 et réciproquement.

Désignons pour un instant par k le nombre de ceux des termes de la suite 1,2,..., b — 1 qui sont premiers à 6 et désignons ces termes par Tir ï'a» '"r >*•