Cas parlicuiîcr. -* Si n ^^ a les nombres tels que k

cungnience

,^-=,a (mûd/>)

soît possible s'appellent restes quadraitffues relalivemenL au

module p.

Si p ^ a, p — I est pair, donc 5 esl égal à a. Donc il y a ^.^' restes c|uadratiqueâ; ce sont tes nombres o tels que

cï ' ^= î { riotl p ) cl il riarîl Fiin de ces restes, la congru ence

a deux racines î néon grues.

Ces restes quadratiques peuvent d'ailleurs élre représentés par

159» Calcul des racines p ri m iltves cl des indiees^ — La considération des indices qui nous a servi à trouver la condition pourqu^une congruence binôme soit possible sert aussi à résoudri" rircclivcment cette congrrience,

M faut, pour cela y posséder une Table des indices des nombres

I, i p — I par rapport au nombre premier /> et a une

cerlainc racine primitive fie ce module.

La première chose a la ire est donc de calculer nne racine primitive du nombre /î. D'ailleurs quand on en aune on les a toutes, d'après la conséquence du tliéorème du n" 151.

100. liechercke d'une racine primitii'e du nombre p, — \^ méthode consiste à elierclier des nombres successifs, appartenant iV des exposants de plus en plus grands, jusqu'à ce qn^on arrive » lin nombre d'exposant p — i .

On essaye m\ nombre % plus grand que i et plus pelti que p. Pour cela on forme la suite des puissances de a, en réduisant cbaeune, pour plus de sim[>licilf', au reste de sa division par^ ou k son reste nniiîmum; et Ton voit quel est le premier reste égal à i» Soit 3 le rang de ce resle^ 5 est Te^cposant auquel appartient ot.

Si 5 =/? — I, a est racine primitive et le problème est résolu.

Si 8 n'est pas égal à p — '1 , a n'est pas racine primitive. Aucun des restes obtenus ne l'est non plus, car ces restes étant congrus aux puissances de a constituent avec a toutes les racines de la congruence x^ — 1^0. Ils sont donc d'un exposant au plus égal à 0.

Choisissons donc un nombre ^ qui ne soit égal à aucun des restes précédents, et essayons-le de la même manière que a. Si [4 est racine primitive, le problème est résolu. Sinon, supposons qu'il appartienne à l'exposant 3'. Le nombre 0' n'est certainement pas un diviseur de 8, car alors p serait racine de la congruence afi — I ^ o, et par suite serait l'un des restes fournis par les puissances de a, ce qui n'est pas.

Mais 3' peut être un multiple de S. S'il en est ainsi, nous avons trouvé un nombre appartenant à un exposant supérieur au précédent.

Supposons enfin que 3' ne soit pas un multiple de 3. Soit m le plus petit commun multiple de 3' et 8; ce nombre m n'est pas égal à 8, puisque 8' n'est pas un diviseur de 3 : il est donc plus grand que 8. Nous allons trouver un nombre d'exposant égal à m. A ceteflel, décomposons m en deux facteurs qui soient respectivement des diviseurs de 3 et 8' et qui soient premiers entre eux. Soit

- et -7 étant premiers entre eux.

Pour réaliser une telle décomposition de m, on décomposera 3 et 8' en facteurs premiers, puis on supprimera dans 3 les facteurs premiers communs à 3 et 8' qui se trouvent dans 3 avec un plus petit exposant que dans 3'; et dans 3' les facteurs premiers communs à 3 et 8' qui se trouvent dans 3' avec un plus petit exposant que dans S. Si un facteur premier se trouve dans 8 et 3' avec le même exposant, on le supprime dans celui de ces deux nombres que l'on veut.

Ceci posé, considérons les nombres a^ et ^^'(ou les restes de leurs

divisions par /?). Ils appartiennent respectivement aux exposants -

. ^' et -7 premiers entre eux.

fi3 mhv* m. — lïBs congruiïccrs.

Donc leur produit ot^jî^' (on le reste de sa division par/?) lïpparliem à un exposrtrit égal ô leur prodinl, c'est-à-dire égal à m. Le problème peut donc êlre considéré comme résolii.

161 • Exemple* — Trouver une racine primilive du nombre i Sy. Nous essajons a, nous trouvons la période suivante :

rTi

ii'-t

ro3

Le calcul est îcî simplifié par le fait qite le vingt-sixième reste est 1 56 qui est congru à — 1 (mod t5^). Le reste suivant sera donc congru à — ^, le suivant à — 4* etc.; on retrouvera les rester» précédent!? changés de signe, jusqu^au 5'^" qui sera congru à t<

Ainsi .4 appaiiient à l'exposant 5q,

Le nombre 3 n'est pas contenu dans les restes précédents, Es?ayons-Ie* Nous trouvons lu période

tQl

iî4

i3js

lia

lïO

too

ïi3

laa

Le calcul se sîmpliJie pour ta même raison que le précédent; 3 appartient à FexposanL 78.

Or on a

Le plus pelîl rnutlSple commun Je 5u et 78 est i 56 ^2- x3x i3» qu'on peut décomposer de la façon suivante en deux facteurs premiers entre eux ci respectivement diviseurs de Sa et 78 !

a*xiî 'ix3xi3 ja 78 i3 '1 iJ 3

Les nombres 2*^ et 3^ appartiennent donc respectivement aun exposants ^ et ^, et leur produit 2^* x 3* appartient à l'exposani i56j c'est-à-dire que c'est une racine primitive.

INDICES. gZ

D*ailleurs les calculs précédents ont montré que 2'5=28 mod iS^).

On obtient donc la racine primitive

28x9 = 2r2=E55 (mod 1 57).

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

Exposant»

iadiees.

«9 ai

EipotanU

Expovanls

Expo«anU

Exposant*

Exposants

Indicu.

indices.

Indices.

Indices

indices.

io5

ii^i

ii(i

IOt>

ii3

3Ci

ii5

at(

io5

Mti,

li:

ii.J

lOI

io3

loi

.4îl

Les nombres de gauche sont les indices des nombres de droile.

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

cBir- tif. — urs

roîci par

cxem

pie une, reposant sur le théo

rèijie suiv

aot ^

ijfièMr, —

S île

nombre premier p est de ta

forme ih

le nombre a

appartienne.

relativement à p.

a l'expo- V

^— t le nombt '1

e (—a) est racine primât ii-e.

elTelj soil $ resposanl auquel appariienl le

nombre

If.

^iiit€

^^^^^^M appartient ù

'cxpo^ianl ^^

^^^^^H Donc us est un mulliptc de^-^

Ah^

» esl impair.

Donc s esl aussi tin mul

liple J

^^^^^H iJotic Paip0»afiL s est égal à ^ — -

- ou à p — 1 .

^^^^^H Mai§ s îiVst pa§ égal à ^-^^ , c-^v

si l'on a va il

^^^^^^m an

iJrJnirail

= 1 (mo<l/>),

** que a n

'ajqrH

r lie nd rail pas

à Fexposanl —

J, Cl

qu'il faîlail d

éïnoDïrcr,

mplcn —

- Soil à clierclier une racine

primilivt

• du J

^^^^^H nom lire 19t. Es

iajoui '^, nous obtenons la suîLe ùi

es resles :

3a (j1 iï«