Cas particulier. — Si // a les nombres t«l s que la

congruence

i n i mod p i

soil possible s'appellent restes quadratiques relativement au

module p.

Si i> ■ '. p — i esl pair, donc 8 esl égal à a. Donc il y a —t restes quadratiques : ce sonl les nombres a tels que

a i i mod /< i

el a étani l'un de ces restes, la congruence

./•'- a i' mod // 1 ;■ deux racines incongrues.

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

159. Calcul des racines primitives et des indices. — La considération des indices qui nous a servi à trouver la condition pour qu'une congruence binôme soil possible sert aussi à résoudre effectivement celte congruence.

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

i. 2 p — i par rapport au nombre premier j> et à une

certaine racine primitive de ce module.

La première chose à faire est donc de calculer une racine primitive du nombre /;. D'ailleurs quand on en a une on les a loules, d'après la conséquence du théorème du n° 151.

160. Recherche d'une racine primitive du nombre p. — La méthode consiste \\ chercher des nombres successifs, appartenant à des exposants de plus en plus grands, jusqu'à ce qu <>n arrive à un nombre d'exposant p — i .

< >n essaye un nombre a plus grand que i et plus petit que p. Pour cela on forme la suite d<> puissances de a, en réduisant chacune, pour plus de simplicité, <m reste de sa division par p ou à son reste minimum; el l'on voit quel esl le premier reste égal à i • Soil o le rang de ce reste, 8 esl l'exposanl auquel appartient oc.

Sio=/> — 1, a est racine primitive elle problème est résolu.

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

Choisissons donc un nombre [3 qui ne soit égal à aucun des restes précédents, et essavons-le de la même manière que a. Si jï est racine primitive, le problème est résolu. Sinon, supposons qu'il apparl ienne à l'exposant 0'. Le nombre 8' n'est certainemeni pas un diviseur de 0, car alors [3 serait racine de la congruence .rfj — 1 = o, et par suite serait l'un des restes fournis par les puissances de a, ce qui n'est pas.

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

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

Soit

- et — étant premiers entre eux.

Pour réaliser une telle décomposition de m, on décomposera 0 et 0' en facteurs premiers, puis on supprimera dans 0 les facteurs premiers communs à 0 et 0' qui se trouvent dans 0 avec un plus petit exposant que dans S'; et dans 0' les facteurs premiers communs à 0 cl S' qui se trouvent dans 0' avec un plus petit exposant que dans 0. Si un facteur premier se trouve dans 0 et 0' 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 p1' (ou les restes de leurdivisions par p). Ils appartiennent respectivement aux exposants 7

et -; premiers entre eux.

9 I (MAI1, lll. — DBS C0NGR1 i:m i s.

Donc leur produit v~- y ( Ou le reste de sa division par p) appartient à un exposant égal à leur produit, c'est-à-dire égal ;'■ m. Le problème peu! donc être considéré comme résolu.