On appelle conguence de degré r une congruence de
la forme
f{x).*'.o (mod/i),
/{x) étant un polynôme entier en x^ à coefficients entiers et de degré /•.
Remarquons d'abord que si une telle congruence admet une racine x^j elle admet aussi comme racines tous les nombres congrus à Xq (mod n) (d'après le théorème du n° 100); mais nous ne considérerons pas ces racines comme distinctes, et quand nous parlerons d'une racine Xo, nous voudrons parler de x^ ou de tout . nombre congru à Xq (mod n).
Étudions d'abord les congruences à module premier.
124. On dit qu'une congruence (à module premier p) est identiquey ou que son premier rpembre est identiquement congru à zéro, lorsque lous ses coefficients sont congrus à zéro, c'est-à-dire divisibles par/?.
On dit que deux polynômes en x sont identiquement congrus (mod p) lorsque leur difierence est identiquement congrue à zéro.
Il faut remarquer ici une différence essentielle entre les congruences et les équations ordinaires de l'Algèbre. En Algèbre, on dit qu'un polynôme est identiquement nul, lorsque tous ses coef- (icients sont nuls; mais il revient au même de dire qu'un polynôme est identiquement nul lorsqu'il prend une valeur nulle pour n'importe quelle valeur de x. Au contraire, on ne peut pas dire qu'un polynôme est identiquement congru a zéro (mod p) lorsqu'il prend une valeur congrue à zéro, quel que soit x.
70 CIIAP. m. — DES CONGRUENCES.
Considérons en effet le polynôme
tp — X.
D'après le théorème de Fermai, ce polynôme prend une valeur congrue à zéro (mod p) pour toute valeur de :r; et cependant ce polynôme n'a pas tous ses coefficients congrus à zéro.
Nous indiquerons une congruence identique par le signe =.
Remarquons que si deux polynômes sont identiques algébri- (fuemerity ils sont identiquement congrus (mod />).
125. Division (mod/>). — Diviser un polynôme f{x) pai' un polynôme o{x) (suivant le modale p ou plus simplement modp)^ c^est trouver un polynôme Q{x) et un polynôme R(-^)? R(j^) étant de degré inférieur à «p (^), tels que :
(Il ne s'agit, bien entendu, que de polynômes à coefficients entiers.)
Pour démontrer Texislence de Q(^) et de R(.r) et, en même temps, pour les calculer, il suffit de faire sur f{jo) et o{x) les mêmes raisonnements el calculs que Ton fait en Algèbre pour la division algébrique ordinaire. On peut, dans le courant du calcul, remplacer tout coefficient par un autre qui lui soil congru (mod/>), ce qui peut servir, par exemple, à abaisser la valeur absolue des coefficients au-dessous de /y.
Le quotient d'un terme A^'" par un terme h! x"^' est B.r'"'" , B étant le quotient de A par A' entendu au sens du n" 103. Le module/^ étant premier, ce quotient existe toujours pourvu que V^ o (mod p).
En particulier, on dit que le polynôme /(^) est divisible (mod />) par le polynôme o{x) lorsque R(^) est identiquement congru à /.éro (mod p). On a alors
/(.r)^o(j') Q(a7) ( mod /> I.
Exemple, — Soit à diviser 5x^ — 3.r*-f- ix^ — 5x--l- lijr-h-i par Zx^ -{- X' — v)X — 'à (mod 7).
CONGRUEXCES DE DEGRÉ QUELCONQUE A MODULE PREMIER. Jl
On peut disposer Topéralion de la façon suivante :
— 4 T* -h 20x5-+- sar^
— (kï^-4- :r5-+- 3x»H-2r
-h 2T^ — IOT'— 4^
Pour diviser un coefficient A par un coefficient A', il suffit de multiplier A par l'inverse de A' (mod p) (voir n" 105). Voici, pour faciliter le calcul, le Tableau des nombres inverses deux à deux (mod 7) :
( mod 7).
Remarquons qu'un polynôme est toujours divisible (modp) par un facteur numérique ^ o.
126. Plus grand commun diviseur (mod/?) de deux poljnômes. — On peut maintenant établir une tbéorie du plus grand commun diviseur (mod p) absolument analogue à celle de l'Algèbre. Le plus grand commun diviseur (mod/>) de deux polynômes s'obtient en divisant le premier par le second, puis le second par le reste et ainsi de suite. Nous laissons au lecteur le soin de voir que tous les raisonnements qu'on a fails en Algèbre à ce sujet peuvent se répéter ici.
De cette théorie du plus grand commun diviseur (mod />), on déduit d'ailleurs les mêmes conséquences que de celle du plus grand commun diviseur ordinaire. Nous nous contenterons d'énoncer celles dont nous allons avoir besoin.
127. I** Tout diviseur commun (mod p) de deux polynômes est un diviseur (mod p) de leur plus grand commun diviseur (mod/>);
72 CIIAP. III. — DES COKGRIEXCES.
'jl"" Quand on multiplie deux polynômes par un troisième, leur plus grand commun diviseur {mod p) est multiplié par ce troisième;
3° Quand on di\>ise deux polynômes par un di{>iseur commun (mod/i), leur plus grand commun diviseur (mod/>) est divisé (moôp) par ce troisième;
4** Quand on divise (niod p) deux polynômes par leur plus grand commun diviseur (mod />), les quotients obtenus ont pour plus grand commun diviseur un nombre. On dil qu'ils sont premiers entre eux (mod //);
5** Quand un polynôme divise {mod p) le produit de deux autres, et qu^ilest premier (mod p) avec l'un d^eux^ il divise r autre (mod />);
6® Quand un polynôme est premier (mod/?) avec plusieurs autresy il est premier avec leur produit ;
7*" Quand deux polynômes sont premiers entre eux (mod />), deux puissances quelconques de ces polynômes sont premières entre elles;
8" Quand un polynôme est divisible (mod p) par plusieurs autres polynômes premiers entre eux deux à deux (mod/?), il est divisible par leur produit ,
La déinonslration de ces théorèmes esl idenlique à celle qu'on donne dans la théorie de la divisibilllé ordinaire des polynômes, ou dans celle des nombres entiers (').
