Racines communes à deux congruences

Les racines communes à deux congruences sont les racines du plus grand commun diviseur de leurs premiers membres.

138. Corollaire. — Soit o(x) le plus grand commun diviseur (mod p) d' un polynôme f(x) et du polynôme xP — x.

i° La congruence rf(x)=o (mod/>) a autant de racines nu il y a d'unités dans son degré; :" ces racines sont ton 1rs les racines de /(x) = o (mod p).

< Il \P. III. — IH s i.iiNMtl EM I S.

En effet,

i cpi /■ «la nt n ii diviseur de xp -x, el ta congruence xp — x=o (mod/?) ajanl autan! de racines qu'il \ a d'unités dans son degré, il en esl de même il<' la congruence œ(a:) = o (mod/?) (nu 135);

' Tout nombre étant racine de xP — x = o (mod/?), toutes les racines de f(x) h^ <> | mod /' I sont racines communes à celte congruence <•! à la précédente, donc elles sont racines de o(x) = o.

Ce t béorème permel donc de voir combien une congruence a de racines.

139. Remarque. — Si la congruence /(x) = o (mod p) est de degré supérieur à// — i. la première opération à faire dans la recherche du plus grand commun diviseur (mod/?) de /"(x) et de xP — x consiste dans la division de /(x) par xP — x. Pour trouver simplement le reste de celle division, il suffi t de remplacer dans y( x) xP par ./•. de façon à rabaisser tous les exposants au-dessous de p.

Exemple.

Soit la congruence

xil — >.r10 — x'-' + \).rs — li./': — ./■•

-1-/1 x'* — i xz — i o a?2 -t- \bx — 6 = o

(mod 7).

Je commence par réduire les exposants supérieurs à (>; pour cela je remplace l'exposant i i par l'exposant 5, l'exposant io par l'exposant /j5 etc., et j'obtiens la nouvelle congruence

x'* — l.i ■ r- | ()./■ Ci ii i mod 7).

Cette congruence n'ayant évidemment pas zéro pour racine, au lieu de chercher le plus grand commun diviseur (mod p) du premier membre avec x1 — x, il revient au même de le chercher avec x° — 1 , ce qui donne les opérations suivantes :

x--h 3 x -t- 3 — 3a?3 — xi+ix 6

">.r — 1 3<r^-}-3.r! — 2.rn-3

ùx"- — i a —

«kr^-f- x^—ix'*-- 1

2X''+0X3— Gx8-l

5x*— ar-4-3 .r-3

aar3-+- 3a;2— 6jt-*-4

ta?*— '2a: -t- 3

CONGRUENCES IilNÙ.MES. 77

Le plus grand commun diviseur est 6x- — f\X — 2. On vérifie facilement que la congruence

bx- — 4 3" — 2 = 0 (mod;) a deux racines x = 1 et x = 2.

§ V. — Congruences binômes. Restes des puissances successives. Racines primitives. Indices.