Racines communes à deux congruenres

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

138. Corollaire. — Soit ^{x) le plus grand commun diviseur (mod p) d* un polynôme /(x) et du polynôme xP — x,

i" La congruence (p(^)^o (mod/?) a autant de racines quil y a d^ unités dans son degré; li" ces racines sont toutes les racines de f{x) ^ o (mod />).

CIIAP. III.

DES C()NriRrEN<:ES.

En effet,

i" ç(^) étant un diviseur de xP — jr, et lacongruence xP — x^u (inod/>) ayant autant de racines qu'il y a d'unités dans son degré, il en est de même de la congruence «p(j?)^o (mod/>) (nM35);

2** Tout nombre étant racine de xP — x z^o (mod/?), toutes les racines Ag f{x) ^ o (mod p) sont racines communes à cette congruence et à la précédente, donc elles sont racines de o{x) ^ o.

Ce théorème permet donc de voir combien une congruence a de racines.

139. Remarque, — Si la congruence /(.r) e^ 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 celte division, il suffit de remplacer dans f{x) xP par x, de façon a rabaisser tous les exposants au-dessous de/>.

Exemple. — Soit la congruence

'^ \x^ — "xx"^— \ox^-\-\^x — () ^o (mod 7).

Je commence par réduire les exposants supérieurs à 6; pour cela je remplace l'exposant 1 1 par l'exposant 5, l'exposant 10 par l'exposant 4) etc., et j'obtiens la nouvelle congruence

x^ — 3j' - ./---h y.r - (> - o (mod 7).

Cette congruence n'ajant évidemment pas zéro pour racine, au lieu de chercher le plus grand commun diviseur (mod/>) du premier membre avec x'' — jc, il revient au même de le chercher avec x^ — i , ce qui donne les opérations suivantes :

ir^-^ X'^-^IX^^ÙX-

;kf^-h x3 -h^x—\