RESTES DES PUISSANCES II
OU
(i4) a'^= I (mod. p).
Puisque a appartient à l'exposant d, la condition nécessaire est suffisante pour que la condition (i4) soit satisfaite est que i& soit un multiple de c?. Comme d'ailleurs ir) est un multiple de /, le plus petit entier positif c? satisfaisant à la condition (i/i) est donné par
(M(/, d) et D(i, d) désignant comme à l'ordinaire, respectivement le plus petit commun multiple et le plus grand commun diviseur de i et d). On en déduit
Cela étant, on voit que la condition nécessaire et suffisante pour que a' appartienne à l'exposant (/ est que r) = d, c'est-à-dire que D (/, d) = j , c'est-à-dire enfin que i soit premier avec d. Ainsi : Connaissant un entier appartenant à l'exposant d, on obtient tous les entiers appartenant au mémç exposant en élevant celui-là à des puissances dont l'exposant est un entier positif premier à d (exposant qu'on peut d'ailleurs supposer plus petit que p — i). Quant aux autres termes de la suite (i3) ce sont les entiers dont l'exposant est un diviseur de (/.
Corollaire. — S'il y a un entier appartenant à F exposant (/, il y en a f[d).
6, Théorème. — Il y d toujours © (d) entiers appartenant à l'exposant d.
Il résulte de ce qui précède qu'en appelant 'lu le nombre d'entiers appartenant à l'exposant d, on a 'b,i = 0 ou 'iid = o {d}. Appliquons ce résultat à tous les diviseurs i, d, ... p — i, de p — i.
^1 = o ou 0(1) 1];^ = o ou o [d)
i|>p i = o ou <p(p i).
Mais (j>j -I- .|^ 4- . . . 4- ,i^^, = p — I ^ parce qu'il y a en tout p — I entiers ^ o (mod. p) ; et d'autre part
propriété démontrée (I. 4io). Donc
Les (p étant tous positifs, et un ^ ne pouvant être que nul ou égal au cp correspondant, ceci exige évidemment que chaque ^ soit égal au cp correspondant (').
7. Autre méthode pour déterminer (|»^. — La nouvelle que nous allons donner a l'avantage de se généraliser pour les modules non premiers (n" 24). iNous supposons acquis les résultats précédents jusqu'au n° 4 inclus. Ainsi on sait que la congruence
x^ ^ 1 (mod. p)
où d est un diviseur de p — i a d solutions. Ces solutions sont les entiers appartenant à l'exposant d ou à un exposant diviseur de d. Si donc l'on appelle 'i>^ le nombre des entiers appartenant à l'exposant c? on a (2)
Cette condition détermine t}»5. En effet, soient
I di di ... di ... p. — I
les diviseurs de p — i par ordre de grandeur croissante. Ecrivons la condition en question en l'appliquant successivement à i, di,
(^) Cette proposition a été énoncée par Lambert [Acta eruditorum 1769), mais non démontrée. Euler en a donné une démonstration insuffisante (Gomm. nov. Act. Petrop., t. 18, p. 85). La première démonstration rigoureuse est de Gauss (Disp. arithm., art. 54 = Werke, t. 1). C'est celle que nous avons reproduite.
(2) La notation 6/d veut dire : 8 divisant d. La notation 2, ^®"' ^'''® '
S/d somme étendue à tous les entiers 0 diviseurs de d.
RACINES PRIMITIVES l3
</2, ... p — I . Nous obtenons
^i + H-'Vp-a =P— 1-
Ces équations déterminent d/i, 'j/cf,, ... 'i>p,. En efîet la première détermine 61, la seconde '|jj, ... la (/ -h 1)® détermine 'bdi car elle ne contient, outre 'i>(f. que des 6 d'indices inférieurs à di, déjà déterminés par les équations précédentes.
Puisque ces équations déterminent les 'i>, si l'on trouve a priori des valeurs qui y satisfassent, ce seront les valeurs des 'b. Or d'après la propriété de l'indicateur (I. 4 10) ces équations sont satisfaites pour 'j^rf, = <p(c?,). On a donc bien ^j^^ :=z o{d).
8. Racines primitives. — En particulier on voit qu'il y a (f){p — i) entiers appartenant à l'exposant/} — i "^ar rapport au module premier p. On les appelle racines primitives de p. Leur propriété fondamentale est la sui\ante : Soit g une racine primitive de p, les p — I entiers :
• s'^ 9\ -M gp-*
sont congrus [mod. p) aux p — i entiers
(sans que, bien entendu, les termes congrus occupent, en général la même place dans les deux suites).
Exemples :
p = 2 II y a (3(1) = I racine primitive, laquelle est g = i-
p ^ 3 II y a ç(2) =r I racine primitive, laquelle est g = — i.Ona :
p == b II y a ç (4) = a racines primitives, lesquelles sont + a. On a :
p = 19 II y a «p(i8) = 6 racines primitives, lesquelles sont 2, 3,
— 4, — 5, — 6, — 9. On a, pour la première par
exemple :
l4 THÉORIE DES (SOMBRES
Problème. — Connaissant une racine primitive, les obtenir toutes. Ce n'est qu'un cas particulier du problème du n° 5. On voit que : ayant une racine primitive, on obtient toutes les autres en élevant celle-là à des puissances d'exposant premier avec p — i . Comme deux exposants congrus (mod. p — i) donnent le même résultat (mod. p), il suffît d'élever aux puissances dont les exposants sont les (p(p — i) entiers positifs, plus petits que l'entier p — I, et premier avec lui.
Problicme. — (Généralisation du précédent). Connaissant une racine primitive g, obtenir tous les entiers appartenant à un exposant donné (/, diviseur de p — i .
p— ' On en obtient immédiatement un, à savoir g ^ . Les autres
s'obtiennent (n" 5) en élevant celui-là aux puissances dont les exposants sont les çi(</) entiers positifs plus petits que (/ et premiers avec lui.
Exemple : pour p := 19, connaissant la racine primitive 2, toutes les racines primitives sont
Cherchons les entiers d'exposant 6. On a un qui est 2 ^ 8 ;
tous les entiers d'exposant 6 sont
9. Indices. — Soit g une racine primitive d'un nombre premier p. Soit a un entier premier a p. On appelle indice de a par rapport au nombre premier p et à la base g, lexposant de la puissance à laquelle il faut élever g pour reproduire a (au module pprh).
Cet exposant existe et il est déterminé (au module p — i près) d'après la propriété fondamentale des racines primitives (n° 8),
On le désignera par Ind^g a, ou plus simplement par Indg a, ou même par /nf/. a, quand il n'y aura pas de confusion à craindre.
