CALCUL DES RACLNES PRIMITIVES

On aura

9 Ind X ^ 189 (mod. 198) Ind a: ^ 31 (mod. 22)

d'où pour Ind x les valeurs

21, 43, 65, 87, 109, i3i, i53, 175, 197 et pour X les valeurs :

12. Calcul d'une racine primitive d'un nombre premier. — Pour effectuer ces calculs il faut avoir une table d'indices. Pour construire une telle table il suffit d'obtenir une racine primitive et de former la période des restes de ses puissances.

Pour cela on essaye successivem*HJes entiers

(-f- I n'est jamais racine primitive et — i ne l'est que dans le cas de/) = 2). Pour essayer l'un de ces entiers on forme les restes (mod. p) de ses puissances successives et l'on en détermine la période. L'entier essayé est une racine primitive si la période a p — I termes. Le calcul se simplifiera par les remarques suivantes :

i<> D'abord il convient évidemment d'essayer les entiers en question dans l'ordre où ils sont rangés plus haut, c'est-à-dire par ordre de valeurs absolues croissantes.

2° Si on a essayé un entier a et que ce nest pas une racine primitive, il sera inutile d'essayer aucun des entiers qui font partie de la série des restes obtenus, car les exposants de ces restes étant diviseurs de celui d« a (n° 5), ces restes ne peuvent non plus être racines primitives.

3° La période des restes obtenus pour un entier a, donne immédiatement celle relative à — a, il suffit de changer les signes de deux en deux.

4° Le calcul des puissances successives se fait, bien entendu, seulement au module p près.

Pour la construction d'un tableau d'indices, il suffit d'une racine primitive. On peut cependant remarquer que lorsqu'on en

22 THEOHIE DES NOMBRES

a trouvé une, on les a toutes en prenant dans la série des restes des puissances de cette racine ceux qui correspondent à des exposants premiers avec p — i .

Exemple. — Trouver une racine primitive de 7. Essayons 2. La période est :

Elle n'a que trois termes dont a n'est pas racine primitive.

Le nombre — 2 n'est pas compris dans les restes précédents. Essayons-le, il donne :

I — 2 3 I 3 3. Donc — 3 est racine primitive.

13. Méthode de Poinsot. — Poinsot a indiqué une autre méthode (*) qui donne en même temps toutes les racines primitives. Elle s'appuie sur la remarque suivante : Tout entier a qui n est pas une racine. primitive d'un nombre premier p est un reste de puissance ç*"*, q étant un facteur premier de p — i, et réciproquement.

Car on a

a^ g^ Cmod. p)

g étant une racine primitive et i n'étant pas premier à p — 1 . Soit alors q un facteur premier commun à i et à /) — i . On peut écrire

Donc a est un reste de puissance q^"^*.

La réciproque est évidente.

Ceci posé cherchons les facteurs premiers de p — i , soient q, q, ... Puis élevons chacun des entiers

aux puissances ç^'"*^ ^'^«"«8, ,.., (au module p près) on aura ainsi tous les entiers qui ne sont pas racines primitives, d'où l'on déduira immédiatement ceux qui le sont.

(^) PoiifsoT. — J. d. m. p. a., t. 10, p. 78.