Soit
une fonction entière de a? à coefficients entiers. Soient a, 6,... les restes respectifs de la division de A, B,... par/?; il est clair qu'on aura identiquement
\x^ + Bor^-'H-. ..^aj:*H- 6jc*-'-+-. . . (mod. p).
La fonction simplifiée oxf^^ 6a;^"*-h... aura par définition tous ses coefficients positifs et inférieurs à p.
DES œNGRUENCES. 5
5. Théorème. - Soient F(a?) = Air"''*^-hBa;^-^''-*-f-...-+-Ka?*^*-h... et /{x) = ax^ -h baf"^* -h . . . deux /onctions de degré m-^n et m, on pourra toujours déterminer^ et d'une seule manière^ deux fonctions simplifiées
ç(a?) = aa?"-h/3a;^-*-h... et v^^r) =Ra;^-' -h Sa?^-*-h .. ., telles que l'on ait identiquement
F{x)=f{x)(f{x)'h^{x) imoû.p).
En e(Tet, les coefficients de (p{x) et de ^{x) étant supposés indéterminés, cherchons à vérifier cette congruence. On aura les congruences suivantes du premier degré :
A ^aa
(mod. p), K^fonct. (a> 6,. . . , a, {3,. . .)-+- 1^
qui déterminent sans ambiguïté oc, puis p,..., puis R, etc.
Les fonctions (p{x) et ^(o?) pourront être appelées respectivement le quotient et le reste de ¥{oo) par /(a?). Si ^{x) est nul, on dira que /{oo) est un diviseur de F(a*).
6. Remarque. — Les diverses fonctions qui s'obtiennent en multipliant une même fonction Y[x) par divers entiers constants ^, ^i , . . . , ont toutes les mêmes diviseurs.
Soit, en effet, f{x) un diviseur quelconque de eY[x)\ on aura
el^(x)=f(x)<^{x).
Soit j une racine de la congruence ey^e^\ on aura
en désignant par (f^[x) la fonction simplifiée congrue à ^^9(0?).
La fonction eY[x) est évidemment divisible : i*^ par l'entier e; 2*^ par ellemême. La fonction ¥{oo) ayant les mêmes diviseurs, on voit qu'elle sera nécessairement divisible : i^ par un entier arbitraire e\ 2^ par un quelconque de ses multiples eY{x). Si ces diviseurs sont les seuls que possède la fonction, nous dirons qu'elle est irréductible. Dans le cas contraire, on pourra la mettre sous la forme d'un produit de fonctions irréductibles.
7. Il est clair que si deux fonctions F (a?) et /(a?) ont un diviseur com-
(i rW UVRE PREMIER.
mun, il^^wWft't^^^ de leur division ^(^)» et réciproquement. On pourra donc,^itp|^9 àtVf i'algëbre ordinaire, chercher le plus grand commun diviseur de (toux fonctions en opérant des divisions successives, et démontrer : . I® que si une fonction irréductible /(a?) divise un produit de fonctions F(a?), F|(a7),..., elle divise nécessairement l'un des facteurs; 2^ que de quelque manière que l'on s'y prenne pour décomposer une fonction en facteurs irré- , ductibles, on obtiendra toujours les mêmes facteurs, à des coefficients constants près.
8. Théorème. — Une congruence F(it?) ^o de degré m admet précisément autant de racines égales ou inégales^ comprises entre o e/ /? — 1 , que son premier membre^ décomposé en facteurs irréductibles, contient de facteurs du premier degré.
Soit, en effet,
f{x)f /i(ir),... étant des facteurs du premier degré, et 9(0?),.,. des facteurs de degrés supérieurs. Pour que F(^) soit divisible par/>, il faudra qu'un de ses facteurs le soit : Tune des congruences f{x)^o, f{x)^o^..., (p{x)^o... devra donc être satisfaite.
Or la congruence /(a?) ^o admet, comme on l'a vu, une seule racine a comprise entre o et/? — i;f{x) en admet également une seule «i, etc.
Les autres congruences telles que (f{x)^o n'en admettent aucune : car, s'il v 6n avait une, 6, on aurait
9(6)^0; d'où 9(ar)^9(x) — 9(6)^M(^ — 6),
M étant la fonction simplifiée de la fonction entière ^ ? ; (p{x) serait donc divisible par x — b, et ne serait pas irréductible, comme on le suppose.
9. Dans le cas le plus favorable, où tous les facteurs de F(x) sont du premier degré, leur nombre sera précisément égal à m, et l'on aura
k étant un coefficient constant.
Soit
Comparant cette expression à la précédente, il viendra
Xr- •
DES œNGRUENCES. - ' 7
Les fonctions symétriques des racines de la congruence s'Mpriment donc au moyen des coefficients de la mémo manière que dant la théorie ordinaire des équations.
Ces propriétés importantes cessent d'avQÎr lieu, si l'on considère les congruence» dont le premier membre contient des facteurs irréductibles d'un degré supérieur au premier. Un inconvénient analogue s'était présenté dans la théorie ordinaire des équations, lorsque celles-ci n'ont pas toutes leurs racines réelles; on v a remédié en introduisant dans le calcul la notion des imaginaires, qui permet de rendre aux énoncés des théorèmes toute leur généralité. Par un procédé analogue, on peut obtenir ici le même avantage, ainsi que Galois Ta montré le premier. Mais, avant d'exposer sa méthode, il convient de nous arrêter un instant sur une congruence importante dont toutes les racines sont réelles et inégales.
§ II. — Des congruences binômes. — Des résidus de puissances.
Des congruences binômes.
10. THÉORir.ME de Fermât. — Tout nombre entier A non divisible par le nombre premier p est racine de la congruence x^^* ^ i (mod./>).
En eflet, les entiers non divisibles par p peuvent être répartis en // — i classes, en groupant ensemble dans une même classe tous ceux qui sont congrus entre eux suivant le module p. Cela posé, formons la suite i , A, A'\ A', — Les premiers termes de cette suite pourront appartenir à des classes différentes; mais comme leur nombre est illimité, on finira nécessairement par en trouver un qui soit congru à quelqu'un des précédents. Soit A" le premier terme qui jouisse de cette propriété; il sera congru à i, car s'il l'était à A*", on aurait
A'"(A"r*"— i) = A"~ A*^o (mod./>),
et comme A*" est premier à /?, A""*" — i ^o (mod./?). Donc A"""* serait congru à i. A" ne serait donc pas, comme on le suppose, le premier terme qui fût congru à l'un des précédents.
Soit donc A^^i, d'où A""^* ^ A,.... Les entiers i. A,..., A""*, étant incongrus entre eux, appartiennent à n classes différentes; puis on retrouvera périodiquement les mêmes classes en formant les puissances suivantes
An An+i y XX y . . . .
s LIVRE PREMIER.
Le nombre n est ud diviseur de p — i, nombre total des classes. Cela est évident si p — i = n. S\ p — i est > /i, soit B un entier appartenant k une classe différente de celles que nous venons de déterminer : les entiers B, BA,..., BA""' appartiennent à ,/i nouvelles classes, distinctes des précédentes et distinctes les unes des autres; car si l'on avait» par exemple, BA ^ A*, on aurait
(B-A)A = o; d'où (B-A) = o,
et B appartiendrait à la même classe que A, contre l'hypothèse; et si l'on avait BA'^^BA', on aurait A'^^A', r et 5 étant moindres que n, ce qui est impossible.
Donc/?— I est au moins égal à 2/1. S'il est plus grand, soit C un entier appartenant à une classe quelconque autre que celles que l'on vient de trouver: les entiers C, CA,..., CA""' appartiendront à n classes nouvelles distinctes des précédentes, et/? — i sera au moins égal à 3/i. On peut poursuivre ainsi jusqu'à ce qu'on ait épuisé le nombre des classes.
Soit doncp—-i=nd: la congruence A"^!, élevée à la puissance rf, donnera A''""' ^ i , ce qu'il fallait démontrer.
Remarque. — Le théorème de Fermât a été généralisé par Gauss ainsi qu'il suit :
Tout nombre A premier à un nombre quelconque m satisfait à la congruence
^?(«)^i (mod.m,,
ç (m) étant le nombre des entiers premiers à m et inférieurs à hu.
Car les nombres premiers à m peuvent être répartis en (p{m} classes en groupant ensemble ceux qui sont congrus suivant le module m. Cela posé, la démonstration se fera absolument comme tout à l'heure, en remplaçant p et /? — I par /n et ç (m).
Faisons en particulier m=^p'^, p étant premier, on aura
et A satisfera à la congruence
xf ^f ^1 (mod./?*<.
11. Corollaire.— Soit â un diviseur quelconque de p— 1 : la congruence a?^ — I == o a (^ racines distinctes comprises entre o et p — \,
Car la congrueDce a?'^' — i ^ o a, comme od vient de le voir, p — i racines distinctes comprises entre ces limites, a savoir i, 3,..., p—^- Son premier membre est le produit de x^ — i par un facteur M de degré /> — I — (^ et ne peut être divisible par p que si l'on a a?^ — i e:= o ou M ^ o. La première de ces congruences a tout au plus d racines distinctes; la seconde en a tout au plus p — \ —^\ elles en ont ensemble p — i\ donc elles ont précisément â et p— i — ^ racines distinctes.
Soient A une racine quelconque de la congruence ^^— i ^^o, A" la première des puissances successives de A qui soit congrue à l'unité; celles des puissances de A qui sont congrues à l'unité seront, d'après ce que nous avons vu (10), les suivantes A", A*", A'",.... Mais A^ est congru à i; donc n est un diviseur de â.
Si Ton a précisément n = ^, on dira que A est une racine primitive de la congruence a?^— i^^o. Dans ce cas, les c? quantités A, A^,..., A^ seront toutes incongrues entre elles, et les restes qu'on obtient en les divisant par/> seront les â racines de la congruence donnée; car soient A"* l'une d'elles, p le reste correspondant, on aura js^eeh A*"^^: i.
12. Théorème. — La congruence x^ — i^E=io (mod.yy), où c? est un diviseur de p — i^ a toujours des racines primitives.
i*" Supposons d'abord c? = y*, g étant premier. Les racines non primitives de la congruence donnée satisfont à la suivante
et sont en nombre ûf*'*ijes autres, en nombreux" ( i— -), seront primitives.
2"" Soit nmnitàê|if^k■ w^ q, r,.,. étant premiers. Soient res-
pectivement A, R,... "icfe^ racines quelconques des congruences x'^'' — 1 =0,
x^ —1^0, — Le produit AB. . . sera une racine de la congruence proposée, dont réciproquement toutes les racines seront de cette /orme ; et Pon obtiendra ses racines primitives en prenant successivement pour A, B,.,. les diverses racines primitives des congruences correspondantes.
En effet, des relations A^ ^ i, B'^ ^^^ i,..., on déduit évidemment
(AB...)î"'-^--=i;
donc AB... est une racine de la proposée. D'ailleurs les produits de la forme AB... sont en nombre y"r^.. et tous incongrus; car si l'on avait
10 LIVRE PREfiflEB.
AB. . . ^ A'B'. . . sans avoir A=h=A', B^B', ..., soit par exemple A ^ A' (mo(l./>), on aurait
AA'-' = BB'-.,.; d'où (AA'-)'^— = (B' B-. . .f^ •= i,
ce qui est absurde; car AA'"* satisfaisante la congruence
les exposants de celles de ses puissances qui sont congrues à l'unité sont des multiples du moindre d'entre eux, lequel étant > i (puisque A^A') et divisant q^ sera divisible par q\ or r^... n'est pas divisible par q. Donc les q^r^... produits AB... sont tous incongrus et égaux aux diverses racines de la congruence proposée.
Enfin si A, B,... sont des racines primitives des congruences correspondantes, AB... sera une racine primitive de la proposée; car, s'il en était autrement, elle satisferait à l'une des congruences
ce qui ne peut avoir lieu, car on a
( AH . . . )f = Af— •^^- • Bï*"' '**••• . . . = Af— '^^- -,
expression qui ne peut être congrue à i, y*~'rP... n'éUml pas divisible par y*.
Au contraire, si A n'était pas une racine primitive, il est manifeste que
(AB.../' se réduirait à i (mod.^). -> i
Les congruences
ayant respectivement y* (i — -J» r^fi — -K-- racines primitives, la proposée en aura
Ainsi toute congruence de la forme
j;*^ I (mod./?;.
DES CONGRUENCES. il
et eD particulier la suivante
j;/»-ir=| (mod./?), a nécessairement des racines primitives.
