Exemple. — Trouver une racine primitive du nombre i5t

Nous essayons 2, nous trouvons la période suivante :

io3

1 JG

Le calcul est ici simplifié par !<• fai'l que le vingt-sixième reste est 1 56 qui est congru à — 1 (mod 1^7). Le reste suivant sera donc congru à — 2, le suivant à — \, etc.; on retrouvera les restes précédents changés de signe, jusqu'au 5.>.r qui sera congru à 1 .

Ainsi 2 appartient à l'exposant 52.

Le nombre 3 n'est pas contenu dans les restes précédents. Essayons-le. Nous trouvons la période

ir»3

ir>6

Le calcul se simplifie pour la même raison que le précédent; '> appartient à l'exposant 78.

Or on a

52 — -.»- • il.

Le plus petit multiple commun de 52 el 78 est 1 56 = 2- x 3 x 1 3, qu'on peut décomposer de la façon suivante en deux facteurs premiers entre eux et respectivemenl dn iseurs de 52 et 78 :

Les nombres 218 el 3- appartiennent donc respectivement aux exposants ^ el — > el leur produit ?.nx.r appartient à l'exposant 1 56, c'esi-à-dire que c'esl une racine primitive.

D'ailleurs les calculs précédents ont montré que 2,3=28 mod iSy).

On obtient donc la racine primitive

■>S x 9 = n» 55 (mod 1 >7 |.

Maintenant que nous avons la racine primitive 55, si nous l'élevons successivement aux puissances 1,2, ..., i56 et que nous remplacions les restes obtenus par leurs restes (mod i5y) nous obtenons les résultats suivants :

xposanta

Exposants

Indices.

indices.

Indices.

indices.

indices

indices.

io5

1 tu

IJS

loi

ioi

l'iO

Les

ion

ibres de

gai

iche soi

•s indic

es nom

ires

de dit

île.

1(32. D'autres simplifications que celles qu'on vient de voir se présentent quelquefois dans le calcul.

()'l m M', lll. — DBS COIfGRI BH< i S.

En voici par exemple ane, reposât» I sur le théorème suivant :

Théorème. — Si le nombre premier p est de la forme \h — i, et que le nombre a appartienne, relativement à />. à l'exposant /; — > le nombre | n \ est racine primitive.

En effet, soit s l'exposant auquel appartient le nombre — a.

Ona

C — a)*= i i mod /' I, d'où

et par suite

( )r a appartient a 1 exposant '—— ■

Donc 2S est un m 11 1 1 i pic de-

Mais — - =-2 li — i csl impair. Donc s est aussi un multiple

i P — i de

Donc l'exposant 5 est égal à - — ou à /> — 1 . Mais s n'est pas égal à — — ■> car si l'on avait

( — a) '- = 1 ( mod />).

on en déduirai 1

a » ==(-1) ^ =(,)ïa-i ->,

de sorte que a n appartiendrait pas a 1 exposant — ■ — •

\)t>nv s = p — 1 , ce qu'il fallait démontrer,

Exemple, Soil à chercher une racine primitive tlu

nombre toi. essayons •■>.. nous obtenons la suite des restes :

2 i s [6 '■> i>j 128 65 1 3<» Cxi [38 85 170

I lu 107 a3 46 92 184 177 i63 i3i» 79 1 58 1 ■> '1 5g

I I s jj 90 180 169 1 17 ki> i) 3<> 60 i"' (g 98 ') 10 >.o [0 80 160 129 67 i3<j 77 1 »î 117 [3

m i 17 34 68 i36 Xi [62 \'<> ■> [5o i<><) 27 >,

iii(S ■x'j ioo 9 18 36 72 \\\ 97 3 (> 12 ■]

2 appartient à L'exposant o,5, c'est-à-dire à l'exposant — •

Or 191 est de la forme \h — 1. Donc ( — 2) ou 189 est racine primitive ( ').

163. Résolution effective d'une congruence binôme. -- La considération des indices, qui nous a servi à trouver la condition pour qu'une congruence binôme

./" = a (mod /> )

soit possible, sertaussi à résoudre effectivement cette congruence. Il faut pour, cela, posséder une Table des indices des nombres 1,2, . . . , p — 1 par rapport au module p et à une certaine racine primitive de ce module.

On trouvera à la fin du \olume une telle Table pour tous les modules inférieurs à 200.

Exemple. — Soi/ à résoudre la congruence

.> "'- = 4a ( mod 181 ).

Cette congruence donne

i2lnd.r=36 (mod 180).

congruence du premier degré qui peut s'écrire

I m !./• = 3 ( mod 1 5 1.

On en déduit pour Ind x les valeurs sui\ an tes (au mod 1 80 près I : J 18 33 4^ 63 7S ()') io8 [23 [38 i3i i(iS qui donnent pour x les valeurs

9") [22 i3o ') 35 64 86 5g Ji 17G 1 4<*> 117.

I()i. Plus généralement un résout immédiatement par la considération des indices la congruence

tu" zjb b. ( mod p I.

D'ailleurs cette congruence devient immédiatement une congruence binôme en divisant (mod//) les deux membres par -/.

(') Voir la Noie I).

(,b CHU1. III. DES ( ONGBUENCBS.

D'une façon générale, on peut toujours, dans une congruence i|uelconque, supposer que le premier coefficient esl réduit à i .

Il -nllii de diviser unod />) toute la congruence par ce coefficient.

Pour n = i , la congruence précédente de\ient la congruence du premier deg vè'.

Exemple. — Soil la congruence

■if)x = J7 i mod 1 99 ).

Elle donne, successivement :

[ndagH- Ind.r — IikIj- (mod 198),

Ind27 = Ind37 — I1UI29 (mod 198),

linl./'i. 121 — iî8 = i6i (mod 19S >. x == |5 ( mod 199).

S VI. — Des congruences à modules non premiers.

[in). Les résultats précédents ne s'appliquent qu'en partie aux modules non premiers.

En particulier, nous avons déjà vu (n° 108) qu'une congruence du premier degré à module non premier peut avoir plus d'une solution, ou être impossible, sans que le coefficient de x soit congru à zéro. Autrement dit, on ne peut définir d'une façon générale le quotient (mod n) d'un nombre A par un nombre lî. On ne peut p;is faire une théorie de la division algébrique (mod // | com parable à celle de la division algébrique ordinaire, et par suite, l'analogie avec les équations et avec les congruences à module premier se trouve rompue dès le début.

166. La résolution d'une congruence à module non premier se ramène à l<i résolution de congruences à modules premiers.

En effet, soit la congruence

I a6) / /• ) = O ( mod // 1.

Supposons // décomposé en un produit «le nombres premiers

entre eux deux à deux