La congruence

(i) jrP-^^ ïL—o (mod./?)

peut se mettre sous la forme

\x * —i) \x * -4-iy=no (mod.j[>), et chacune des deux congruences

(2) * — I :=:: o (mod. />),

(3j j:*-f-iL::0 (mod./?),

dans lesquelles elle se décompose, a racines. En

ontre, d'après le théorème du n^'SlO, chaque racine de la congruence (a) est un résidu de carré, ou un résidu quadratique ;diU contraire f aucune des racines de Téqualion (3) ne peut être le résidu d'un carré, et ces racines sont dites non-résidus quadratiques^ ou simplement nonrésidus.

Le nombre a sera donc résidu ou non-résidu quadratique, relativement au module premier p, suivant qu'il satisfera à la congruence (a) ou à la congruence (3),

c'est-à-dire suivant que la division de a ' par p donnera le reste -f- 1 ou le reste — i . Legendre a proposé

de représenter ce reste par le symbole ( - j > en sorte que l'on a

■fâ=

-hi

quand a est résidu quadratique, et

quand a est non-résidu.

Il est évident que, si p est de la forme 4* -H i , les deux nombres a et — a sont en même temps résidus ou nonrésidus. Au contraire, si p est de la forme 4* -H 3, l'un des deux nombres a, — a est résidu, tandis que l'autre est non-résidu.

Si les nombres a et b sont tous deux résidus ou tous deux non-résidus, on a

a^=±\, b^=±i, d'où (fl^)'=-hi (mod./?);

par conséquent, le produit ab est résidu. Si, au contraire,

68 COURS d'algèbre SUPëEICUEB.

TuD des nombres aetb est résidu, et que l'autre soit nonrésidu, on a

p-i p—i jp-t

<i'-r:z=i, 6*iz=z=i, d'où (a6)"i=— X (mod ^) :

le produit ab est donc non-résidu.

On exprime ce résultat par la formule

et il est évident qu'on aura généralement

On trouvera plus loin un beau théorème de Legendre qui permet de déterminer très-facilement le signe des

expressions 1-1*

Recherche des racines primitives d'un nombre premier .

312. Le théorème du n" 310 fournit un moyen de trouver les racines primitives d'un nombre premier.

Soient ^ un nombre premier ; a, //, r, ..., 5 les facteurs premiers inégaux de p — i, et écrivons les p — i nombres

si Ton enlève de celle suite tous les résidus de carrés, de puissances q, de puissances r, etc., il ne restera plus que les racines primitives de p.

Au moyen des carrés, on exclut d'abord la moitié des nombres; au moyen des puissances//, on exclura la y**** partie de ceux qui restent, et ainsi de suite.

Supposons, par exemple, qu'il s'agisse de trouver les racines primitives de 3i.

Écrivons les trente nombres

11, 2, 3, 4i ^j ^' 7» S' 9» *^' II, 12, i3, i4» i5, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 3o ;

comme les facteurs premiers de 3o sont 2, 3 ejr 5, il suffira d'enlever de la suite (1) les résidus des carrés, des cubes et des cinquièmes puissances.

Pour exclure les carrés, nous élèverons les nombres (i) au carré ; les carrés des quinze premiers sont

i, 4i 9« >6« 2^1 36, 49i 64, 81, looy 121, i44t i^t >9^t ^^Sf et ils ont pour résidus

les carrés des quinze derniers nombres de la suite (i) donneraient les mêmes racines, car on a

(3i-A)«=A« (mod. 3i).

Otant ces quinze nombres (2) de la suite (i), il restera les quinze que voici :

(3) 3,6, II, 12, i3, i5, 17, 21, 22, 23, 24, 26, 27, 29, 3o,

dont il faut maintenant supprimer les cubes et les cinquièmes puissances. Chaque nombre déjà supprimé (2) satisfait à la congruence

x^'^n^i (mod. 3i);

donc sa puissance troisième et sa puissance cinquième y satisfont aussi, et, par conséquent, font partie des nombres déjà supprimés. D'après cela, les nombres de la suite (3) qu'il reste à rejeter sont des résidus de puissances troisième et cinquième de ces mômes nombres (3). Pour avoir les résidus des cubes de la suite (3), il suffît de multiplier les premières puissances par les résidus

70 couas d'algèbre supériecbe.

quadratiques que la suite (a) fait connaître et qui sont

9, 5, 18, 20, 14, 8, 10, 7, 19, 2, 18, 25, 16, 4» n on aura ainsi les résidus cubiques suivants : 27, 3o, 3o8, 240, 182, 120, 170, 147, 4*8, 46, 4^2, 65o, 432, ï 16, 3o,

dont les résidus minima sont (4) 27» 3o, 29, 23, 27, 27, i5, 23, i5, i5, 29, 3o, 29, 23, 3o

Il n*y en a que cinq de différents, comme nous le savions d'avance ; ce sont

et en ôtant ces nombres de la suite (3), il ne restera plus que les dix suivants :

(6) 3, 6, II, 12, i3, 17, 21 1 22| 24» 26,

dont il n'y a plus à rejeter que ceux qui sont des cinquièmes puissances. Chacun des nombres déjà exclus satisfait à Tune des congrucnces

jr^îz^i (mod. 3i , x*°:.3i (mod. 3i).

Il en est donc de môme de sa cinquième puissance, qui, par conséquent, fait partie des nombres exclus : un nombre de la suite (6) ne peut donc être la cinquième puissance que d'un nombre de la môme suite. Pour avoir les résidus des cinquièmes puissances des nombres (6), il suffit de multiplier les résidus cubiques déjà formés par les résidus quadratiques correspondants, et de prendre les résidus minima des produits. Les résidus cubiques sont

les quadratiques

SBCTIOir III. — CHÂPITltB II. 7I

les produits sont

et l'on trouve pour résidus des cinquièmes puissances

II n'y a ainsi, dans la suite (6), que deux cinquièmes puissances, comme nous le savions déjà, savoir :

en supprimant ces deux nombres, il ne restera plus que les huit racines primitives de 3i, savoir:

3, II, 12, i3, 17, 21, 22, 24.

313. La recherche des racines primitives ne peut guère s'eflectuer que par tâtonnements ; le procédé que nous venonsd'indiquer est presque impraticable dès que le module est un peu considérable ; aussi croyons-nous utile de faire connaître une autre méthode due à Gauss, et par laquelle on peut obtenir assez facilement une racine primitive ; les autres racines primitives pourront être déterminées ensuite, comme nous l'avons indiqué précédemment (n*> 306).

On prendra arbitrairement un nombre a dans la suite

2,3, "-f{p — i), 2 par exemple, et Ton déterminera sa

période, c'est-à-dire la période des restes fournis par les

puissances

iiy a^y û', ....

Si cette période a p — i termes, a sera une racine primitive; mais, si la période a moins de p — i termes, on prendra un autre point b qui ne soit pas compris parmi les restes de la suite (i), et Ton cherchera de même la période deb. Si cette période de b a.p — i termes, b sera racine primitive ; mais supposons qu'il n'en soit pas

7^ COURS d'alGEBBE SUPéniEURB.

ainsi. Désignons par/2 Texposant auquel a appartient^ et par m celui auquel appartient b\ comme les restes de la suite ( I ) comprennent tous les nombres qui appartiennent à Texposant/Zy et, pour la même raison, ceux qui appai^ tiennent à un exposant sous-multiple de/i, le nombre m ne sera pas un diviseur de n. Mais il peut être un multiple de Jiy et, quand ce cas se présente, la connaissance de & aura avancé la solution de la question, car ce nombre appartient à un exposant plus élevé que celui auquel a se rapporte. Supposons que m ne soit égal ni k p — i ni à un multiple den; désignons par 5 le plus petit commun multiple de n et m, et décomposons ce nombre s en deux facteurs premiers entre eux rij m', qui divisent respectivement les nombres n et m. Voici comment cette décomposition peut être eficctuée : on décomposera les nombres 72 et m en leurs facteurs premiers ; soit c Tun de ces facteurs premiers destiné à entrer dans j avec l'exposant y. Si c^ est diviseur de n seul, on fera figurer c^ dans //; si cT est diviseur de m seul, on introduira au contraire c^ dans m'; enfin, si c^ est diviseur commun de m et de n, on introduira c^ à volonté, soit dans m', soit dans nt\ on agira de même à Tégarddes autres facteurs premiers dei. On aura ainsi s = n'nîj avec n-=vl e^ Tn=z rrlfy e et / étant des entiers. Cela posé, je dis que le nombre à* appartient à l'exposant /i', relativement au diviseur^; en effet, la puissance /i'»*™« de a^ est a", et elle donne en conséquence le reste i; il n'y a pas d'ailleurs d'exposant v inférieur à w' tel que (rt^)* ou a'*^ donne le reste i, puisque ve est inférieur à n et que a appartient à l'exposant n. On ferait voir de même que &/ appartient à l'exposant m\ et il en résulte (n**307) que le produit a^, bf ou le résidu de ce produit appartient à l'exposant nJn'=.s.

La méthode que nous venons d'exposer conduit, dans tous les cas, à un nombre qui appartient à un exposant

plus élevé que celui auquel appartient le nombre a duquel on est parti. En poursuivant la même marche, on arrivera donc certainement à un nombre appartenant à l'exposant p — I ; ce nombre sera une racine primitive de p. Mais, dans la plupart des cas, il se présente des circonstances particulières qui permettent de simplifier Tapplication de la méthode.

314. Premier exemple. — On demande une racine primitive du nombre premier y i .

Prenons le nombre 2 et cherchons sa. période. A cet effet, on formera la série des puissances de a ; chacune d'elles s'obtient en multipliant la puissance précédente par a; mais, avant de faire cette multiplication, il faut avoir soin de retrancher 71 de la puissance qui sert de multiplicande, lorsque celle-ci est supérieure à 71. On trouve que la période de a a 35 termes qui sont

Le nombre 2 n'est donc pas racine primitive de 7 1 , et il appartient à l'exposant 35 ; mais il est facile de voir que le complément de 2 à 71, c'est-à-dire 69^ est racine primitive. En effet, de l'identité

on tire

(mod. 71],

d'où il résulte que la suite des restes fournis par les puissances de 69 pourra se déduire de la suite des restes des

y 4 COURS d'algèbre supérieure.

puissances de a; il suffira effectivement de remplacer, dans cette dernière suite, les restes de rang impair par leurs compléments à 71, sans rien changer aux restes de rang pair. Dans la suite des restes fournis par les puissances de (2) et dont la première période est Tensemble des nombres (i), le reste i occupe les rangs 35,7©, ...; ce reste 1 n'apparaîtra donc qu'au 70* rang, dans la période de (ip, et en conséquence 69 est racine primitive. Formons la période de 69 en suivant la marche que nous venons d'indiquer, c'est-à-dire en prenant deux fois la période (1) du nombre 2 et en remplaçant les termes de rang impair par leurs compléments à 71, on trouvera:

43, 56, 3o, II, 49. 44» 54,

et ceux des nombres du tableau (2) dont les rangs sont marqués par des nombres premiers à 70 seront les racines primitives de 71. Les 24 racines primitives de 71, dans l'ordre où elles se présentent comme restes de puissances de 6i), sont ainsi