p — 0^ — ^ (mod. p) p est premier
En effet sip n'était pas premier il aurait un facteur premier qui entrerait dans le produit i. 2 ... (p — i). Ce facteur ne diviserait donc pas i.2...(p — i)+i H"^ P^"* ^"^^^ ^^ pourrait être divisible par p.
Nole.l : Sur le calcul des racines primitives. Pour montrer les simplifications qui se présentent dans la recherche des racines primitives, donnons quelques exemples.
1" Exemple. — p = i3. Essayons 2, nous trouvous la période :
On voit par le calcul de 6 termes que 2 n'appartient pas à un exposant égal ou inférieur à 6. Or 6 est le plus grand diviseur de 12 qui ne soit pas 12 lui-même. Donc 2 est racine primitive.
(1) Ce deuxième théorème a été énoncé par Waring (Meditationes algebricœ^ 3' éd., Cambridge, 1873, p. 38o), qui l'attribue à Wilson. Démontré par La^grange {Nouv. mém. de l'Ac. de Berlin (1771)' ^^•' ^11^' P- ^^5. Œuvres 3, Paris 1869, p. 435) en même temps que le théorème précédent.
D'une façon générale : si aucune des puissances
nesl congrue à i (mod. p), a est racine primitive.
2* Exemple. — p = 3i. Essayons 2, nous trouvons la période :
2 appartient à l'exposant 5. Essayons — 2 qui n'est pas dans les restes des puissances de 2. Il est évident que l'on obtient sa période en changeant les signes des termes de rang impair dans la période relative à 2. On obtient ainsi :
— 2 appartient à l'exposant 10. Essayons 3 qui n'est dans les restes ni des puissances de 2 ni des puissances de — 2.
3, 9, — 4, —12, —5, — i5, — i4, —II, —2, —6...
Nous n'aurons pas besoin de pousser ce calcul jusqu'au bout ('). Car nous trouvons au troisième terme de cette période un terme — 4 déjà trouvé dans la période de — 2. On a donc
33= (—2)7 (mod. 3i).
Soit e l'exposant de 3. Elevons les deux membres de la congruence précédente à la puissance e, il vient :
Donc je est divisible par l'exposant de — 2, c'est-à-dire par 10. Donc e est divisible par 10. Mais, de plus, e est un diviseur de 3o. Donc e = 10 ou 3o. Il suffit alors de pousser la suite des puissances de 3 jusqu'au dixième terme pour constater que l'exposant de 3 n'est pas égal à 10. Donc 3 est racine primitive.
Dans le calcul précédent nous avons fait usage de deux simplifications qui peuvent se généraliser.
i" Simplification relative au calcul des puissances de — 2. — D'une façon générale :
Si a appartient à un exposant impair, — a appartient à l'exposant double (p ;zf 2). On peut généraliser davantage :
(1) Toutes ces simplifications qui seraient négligeables dans les exemples donnés où il s'agit de nomores premiers relativement petits, deviennent très importantes dans le cas contraire.
Si a appartient à l'exposant e et a' à l'exposant e' ; si, de plas, e et e' sont premiers entre eux, alors aa' appartient à l'exposant ee'. (Le cas particulier précédent s'obtient en supposant a' =^ — i et, par suite, e' = 3). En effet, on a :
{aa')"' = (a'Y' {a'*y = 1 (mod. p).
Donc l'exposant E de aa' est un diviseur de ee'. D'autre part, de la congruence (aa'y ^ i, on lire, en élevant les deux membres à la puissance e
Donc E^ est un multiple de e', et, puisque e est premier avec e', cela prouve que E est un multiple de e'. On voit de même que E est un multiple de e. Mais e et e' sont premiers entre eux. Donc E est un multiple de ee'.
E étant à la fois un multiple et un diviseur de ee' est égal à ee'.
a" Simplijîcation résultant de la relation 3* ^ ( — ay. Soient a et a' deux entiers, e et e' leurs exposants. Supposons qu'on ait
/ a* ^ a"* (mod. p).
On en déduit, en élevant les deux membres à la puissance e'
Donc ae' est divisible par e, donc c'est un multiple de a et de e, et l'on a
D(a, e) X étant entier.
Mais de plus e' est un diviseur de p — 1 . Donc X est un diviseur de
le 1 — !L 2 . Soit alors d le plus grand diviseur de ~ —
qui ne soit pas ■ — - — ^ — - lui-même. On voit que si l'on a calculé la suite des restes des puissances de a' jusqu'à celle d'exposant
rT? r d, et si aucun de ces restes n'est 1, il est inutile de continuer,
a' est racine primitive.
3° Exemple : p = [\i. — Essayons 2 nous trouvons la période
la seconde moitié de la période qui n'est pas écrite se déduisant de la première en changeant les signes. On voit que 2 appartient à l'exposant 20. 11 est inutile d'essayer — 2 qui appartient à la période précédente. Essayons 3, la période correspondante est
on voit que 3 appartient à l'exposant 8. Il est facile maintenant de déduire de ce qui précède une racine primitive. Car 2 appartenant à
1 exposant 30, 2* appartient à l'exposant -^ = 5, et comme 3 appartient à l'exposant 8 qui est premier à 5, il s'ensuit, d'après un théorème précédent que 2* X 3 ou 7 appartient à l'exposant 8x5 =4o. Donc 7 est racine primitive.
La marche suivie dans cet exemple peut se généraliser et l'on obtient ainsi une méthode tout à fait générale de recherche des racines primitives. Cette méthode consiste à obtenir des entiers d'exposants croissants jusqu'à ce qu'on arrive à une racine primitive.
On essaye un entier quelconque a (a = 2 par exemple) ; soit e son exposant. Si e = p — 1, l'entier a est une racine primitive. Sinon on essaye un entier a' qui ne soit pas dans la série des restes des puissances de a ; soit e' son exposant. Si e' = p — i l'entier a est une racine primitive. Sinon, remarquons que e' n'est pas un diviseur de «, puisque a' n'est pas dans la série des restes des puissances de a. Il en résulte que le plus petit multiple commun de e et de e' est supérieur à e ; on va trouver un entier d'exposant égal à ce plus petit commun multiple. Si e' est un multiple de e, ce plus petit commun multiple est e', et l'entier cherché est tout simplement a'. Sinon nous allons décomposer M (e, e') en un produit de deux facteurs
de façon que y divise e. que/' divise e' et que, de plus, / et /' soient premiers entre eux. Pour cela, décomposons e et e' en facteurs premiers. Puis, les facteurs premiers qui sont dans e avec un exposant plus grand que dans e' (ce second exposant pouvant être nul), nous les mettrons dans y avec l'exposant qu'ils ont danse; les facteurs premiers qui sont dans e' avec un exposant plus grand que dans e, nous les mettrons dans/' avec l'exposant qu'ils ont dans e' ; enûn les facteurs premiers qui sont dans e et e' avec le même exposant seront mis indifféremment dans f ou J' avec ce même exposant (mais pas dans / et y à la fois). Il est clair que les entiers/ et/' ainsi formés satisfont aux trois conditions imposées.
Ceci posé a-^ appartient à l'exposant /et a'^ appartient à l'exposant /' ; donc
appartient à l'exposant j/', c'est-à-dire à l'exposant M (e, e).
Trouvant ainsi des entiers successifs d'exposants de plus en plus grands, on finit par arriver à une racine primitive. Cette méthode est due à Gauss ('). On peut remarquer qu'elle démontre l'existence d'une racine primitive et peut remplacer la démonstration du n° 7. (Quand on connaît une racine primitive on en déduit (n° 8) les cp (d) entiers appartenant à un exposant d diviseur de p — i).
Nous allons maintenant examiner quelques cas dans lesquels on peut trouver, sans calcul, une racine primitive. Remarquons que, d'après la méthode de Poinsot, la recherche des racines primitives de p est d'autant plus simple que /) — i contient moins de facteurs premiers. Examinons donc le cas où p — i ne contient qu'un facteur premier. Comme d'ailleurs p — i est pair ce facteur ne peut être que 2 . Donc p est de la forme a* -f- i . On peut même remarquer (sans que cela intervienne dans la recherche de la racine primitive) que k est une puissance de 2. On a en effet le théorème suivant :
Un entier de la forme a* -4- i (a >» i, /i \>> i) ne peut être pfemier que si k est une puissance de a et si a est pair. Car si k avait un diviseur impair 2/ -H i, en posant k = {al -h i)m, on aurait
a(2/+l)m f I (gm , i) (ga/m a(2/-l)m f . ^ j).
De plus il faut que a soit pair, car, sinon, a*^ -h i le serait.
En particulier les seuls nombres de la forme 2'' + 1 qui puissent être premiers sont ceux de la forme 2^-4- i. Fermât avait pensé que la réciproque de ce théorème est vraie, c'est-à-dire que tous les entiers de cette forme sont premiers. MaisEuler a démontré l'inexactitude de celte proposition en vérifiant que
2'' -+- I = 6/ir X 6700^17
On a aussi démontré que 2^ -f- i n'est pas premier pour i = 6, 7, 8, 9, 1 1, 12, 18, 28, 36, 38, 78 (Landry, Morehead, Western, Cunniogham, Lucas, Pervouchine,
{^) Disquis. arithm., art. 78.
SeellofT, CuUen). Le dernier de ces résultats, relatif à 2^^"^ -1- i est dû à M. Morehead.
Ceci posé on a le théorème suivant :
Un nombre premier de la forme p = 2'^ ' + 1 (i ;> o) admet 3 comme racine primitive ('). En effet le seul facteur premier de p — i étant 3, tout entier qui n'est pas reste quadratique de p est racine primitive. Or on verra plus tard (n" 1Ô6) que 3 n'est reste quadratique que des nombres premiers ^ ± i (mod. 12), et il est évident qu'on ne peut avoir
2* -+- I ^ rt 1 (mod. 12) {k = 2' > i).
Remarque I. — On démontrerait de la même façon que — 3 est aussi racine primitive. D'ailleurs plus généralement : Si p = i {mod. li) et si g est racine primitive, — g l'est aussi.
Remarque II. — Toutes les racines primitives sont comprises dans la formule 32"+'.
Exemples : 2^ + j = 5, 2* -h i = 17, 2^ -f- i = 267 admettent zh 3 comme racines primitives.
Examinons maintenant le cas où p ^ — 1 contient deux facteurs premiers simples ; comme d'ailleurs p — 1 est pair, on a p — i = aq, q étant premier impair.
Théorème (^). — Tout nombre premier de la forme p = 2q -{- i où q est lui-même premier impair, admet comme racine primitive 2 51" </ ^ t {mod. 4), et — a si q ^ — 1 {mod. 4)-
En effet, dans ce cas, tout entier qui n'est ni reste de puissance ^ème ni reste quadratique est racine primitive. Or les restes de puis-
f — I sances qèmes satisfont à la congruence x ' ^ 1 ou x^ ^ i dont les seules racines sont dz i. Or ni 2 ni — 2 ne sont congrus à riz i fsauf si p = 3, mais dans ce cas le théorème se vérifie directement). De plus si q ^ i (mod. 4) alors p ^ 3 (mod. 8) et 2 n'est pas reste quadratique (n° 195), si g ^ — 1 (mod. 4). alors p ^e — i (mod. 8) et — 2 n'est pas reste quadratique (n° 196).
Exemples : '.
2 est racine primitive de 11, 59, 83, 107, 179, 227, 3/17, etc.
— 2 est racine primitive de 7, 23, 47, 167, Sôg, 384, etc.
(') RicHELOT. — J.f. r. u. a. M., 9(1833) p. 5.
Avant de monlrer que 3 est racine primilive, il est bon de montrer que ±2 ne le sont pas. En eGFet =fc 2 appartiennent à l'exposant a'+*.
(^j TcHEBicHEFF. — Tliéoric des congruances (en russe, iS^g), traduction allemande par Schapira, Berlin (18^9), italienne par M"* Massaroi, Rome, i8g5.
Généralisalion. — On voit qu'on peut, dans ce qui précède, remplacer 2 ou — a par un autre entier a. Pourvu qu'on ait établi la forme des nombres premiers dont a n'est pas reste quadratique, ce qui est facile (n° 201), on aura des nombres premiers dont a est racine primitive. Nous allons appliquer à a = ± lo parce que lorsque -+ou — lo est racine primitive, c'est cette base qu'il convient d'adopter pour le calcul des indices.
Or lo n'est pas reste quadratique des nombres premiers de l'une des formes
4o/i zh 7, it II, ±17, ±19
correspondant pour ç à l'une des formes
ao^ -+- 3, di 9
et — 10 n'est pas reste quadratique des nombres premiers de l'une des formes :
ioh -h 3, -H 17, — I, — 7, — 9, — II, — i3, — 19
correspondant pour q à l'une des formes :
ao/i ±1, — 7.
Donc tout nombre premier de la Jorme 2q -\- i où q est lui-même un nombre preuiicr, admet 10 comme racine primitive si 9 ^ 3, db 9 (mod. 20) et admet — 10 comme racine primitive si q^ ± i, — 7 (mod. 20).
Exemples :
47, 167, admettent 10 comme racine primitive 83, 107 — 10 »
Théorème ('). — Tout nombre premier de la forme liq -\- \ où q est lai-même premier impair admet 2 et — 2 comme racines primitives.
En effet tout entier qui n'est ni reste quadratique ni reste de puissance q^"*^ est racine primitive. Or 2 ni — 2 ne sont restes quadra-tiques parce que p ^ 5 (mod. 8). De plus pour que 2 ou — 2 fût reste de puissance (jf»"»' il faudrait que 2* — 1^0 (mod. p), ce qui est impossible puisque p ]> i3.
Exemples. — i3, ag, 53, i49, 173 admettent 2 et — 2 'comme racines primitives.
Théorème. — Tout nombre entier de la forme p = 2''q -h i où q est
( ') TcHELYCHEFF. LoC, cU.
NOTES ET EXERCICES 3l
un nombre premier impair, k an enlier plus grand que 2, el où
admet 3 comme racine primitive.
3 n'est pas reste quadratique car p n'est pas congru à ±1 1 (mod. 12). (Cela ne pourrait arriver que pour q = 3, mais la condition (20) entraine 9 >» 3),
3 n'est pas non plus reste de puissance q^*^. En effet, cela entraînerait
3' — 1^0 (mod, /))
(3' — 0(3' -+- 1) ^ o (mod./)).
On n'a pas
car cela entraînerait
3^ ^ I (mod. p)
3 ^ ^ I (mod. p)
ce qui n'est pas puisque 3 n'est pas reste quadratique de p. On n'a pas non plus
3' " H- 1 ^ G (mod. p) ou.
3* * -f- I := Ap {h entier >• o).
Car si h était égal à 1, cela entraînerait p ^e i (mod. 3) ce qui n'est pas, et si h étant plus grand que i, cela entraînerait
ce qui est contraire à l'hypothèse.
Exemples. — 89, 137, 233, 4337 admettent 3 comme racine primitive.
II. — Remarque sur les nombres de la forme 2'+ i. La congruence en i
2^ -h 1 ^ o (mod. p) a au plus une solution.
Posons 2' = X. Si la congruence 2* + i ^ o (mod. p) est impossible, la congruence en i l'est aussi. Si la congruence 2^ -H i ^ o (mod. p) est possible sa solution générale est de la forme ar^ (2^ -\- 1),
OÙ a-Q est la plus petite solution et y un entier arbitraire. Or l'égalité
ne peut être satisfaite que pour j = o.
En particulier deux nombres delà formes*' + i, différents entre eux, ne peuvent jamais être divisibles l'un par l'autre.
III. — Nombres premiers de la forme 2* — i. A côté des nombres premiers de la forme a'' -4- 1 considérés plus haut, considérons ceux de la forme a'' — 1 (a >» i A- > 1).
Un entier de la forme a'' — i (/î ;zf 1) ne peut être premier que si a= 2 et si k est premier. En effet si a ;zf 2, l'entier a'' — i a le facteur a — I différent de 1 et de lui-même. D'autre part si A; est divisible par k' {k ;zf k' , k' ^ i), l'entier 2'' — i est divisible par 2''' — i. La réciproque nest pas vraie car 2'' — i n'est pas premier pour A: = 1 1
Ce résultat peut se généraliser. Si k et 2k H- 1 sont premiers, si de plus k ^ — I [mod. 4) ; alors 2'^ — i est divisible par 2k -+■ 1. En effet 2 A 4- I ^ — I (mod. 8). Or on verra plus tard (n° 193) que 2 est reste quadratique de tout nombre premier ^ — i (mod. 8). Donc 2 est reste quadratique de 2A 4- i. Donc
2^^ — 1^0 (mod. 2A + 1).
La congruence
2* — 1^0 (mod. p)
p premier, a une infinité de solutions en A, mais une seule, la plus petite est un nombre premier, car les autres sont des rnultiples de celle-là.
IV. — Nombres parfaits. Les nombres premiers de la forme 2''^ — i interviennent dans la question des nombres parfaits. On appelle ainsi un entier positif égal à la somme de ses diviseurs (autres que lui-même, bien entendu).
Exemples : ^
Recherche des entiers parfaits pairs. Soit n= 2^ . a. (a impair). En exprimant que l'entier n est parfait, on trouve
X(a) étant la somme de tous les diviseui's de l'entier a, y compris luimême. On en déduit
r étant un entier impair. Or il faut que r = i, car si r ;zf i, a admet au moins comme diviseurs les entiers
dont la somme 2''+'(r -h i) est plus grande que a'^+'r. Un' entier parfait pair est donc de la forme
De plus il faut que 2*+' — i soit premier, car sinon on aurait
et
d'où
Ainsi uft nombre parfait est de la forme (')
p étant premier et 2^ — 1 aussi).
Réciproquement, tout entier de cette forme est parfait, on le voit immédiatement.
Pour P = ^ f^ = ï
Pour p = 1 1 on n'obtient pas de nombre parfait parce que 3" — 1 n'est pas premier.
Pour p = i3 n = 3355o336, etc.
On ne sait pas s'il y a une infinité ou non de nombres parfaits pairs.
Nombres parfaits impairs. — En posant n = p'^q^ ..., l'équation qui exprime que n est parfait est
Mais l'on n'a pu ni trouver une seule solution de cette équation, ni démontrer qu'elle n'en a pas. La question des nombres parfaits im-
(}) Euclide, livre IX, prop. 36.
Caher. — Ttéoiie des nombres, t. II, ï
pairs reste donc complètement sans solution. On a démontré les théorèmes suivants :
Pour que l'entier impair n soit parfait, il faut qu'il ait plus de quatre facteurs premiers, (Sylvesler G. R. A. P., t. io6 (1888)), et plus de sept s'il n'est pas divisable par 3.
L'un de ces facteurs doit être ^ i (mod. 4) et son exposant impair. Les exposants des autres facteurs doivent être pairs (remarqué par Frénicle, démontré par Euler, Comm. Arithm., 2,5i4).
Le facteur à exposant impair n'est certainement pas le plus petit (J. Carvallo, théorie des n. parfaits, Paris, i883).
V. — Sur les fonctions symétriques des entiers i, 2, ... p — 1 ; p étant un nombre premier.
Nous avons démontré (n" 15) les congruences :
Si ^ 02 ^ ... ^ S„i ^ o ) -
(mod. p).
Op| = — I )
Sft étant la somme des produits kak des entiers i, 2, ... p — 1. Occupons-nous maintenant des sommes de puissances semblables Sk = l'^ H- 2* + ... -+- (p — 1)*.
On a, en supposant o <^ k <^ p — ila formule
^k — Si 2fc, -+- S, 2,2 — ... -h (- I)*-' S,2 2, = (— i)*-i/.- S,. Si /c < p — I, on a
3l ^ bj ^=. ... ^=. ij/c^i ^B o.
Donc
Si k = p — I , on a
Sp i = — 1.
Donc
Passons au cas de A: > p — i. On a, pour un entier a quelconque, d'après le théorème de Fermât
Faisons a égal successivement à i, 2, ... p — i et ajoutons, nous obtenons
En combinant ces différents résultats, on voit en définitive que ^k ^ o quand k n'est pas divisible par p — 1
^k^ — 1 quand k est divisible par p — 1 .
Occupons-nous enfin de l'expression ^0*6"^ ... / dans laquelle a, h, ... l désignent n des entiers i, 2, ... p — i
a, p, ... X sont des entiers positifs fixes; la sommation s'étend aux différentes façons de choisir a, b, ... l.
L'entier n s'appelle l'ordre de l'expression, et la somme
s'appelle le degré. Pour n = i on retrouve les sommes de puissances semblables
Le théorème que nous vouions démontrer est le suivant : Si le degré de l'expression n'est pas divisible par p — i, la valeur de l'expression est congrue à zéro (mod. p).
Nous allons le démontrer pour les expressions d'ordre n en le supposant vrai pour les expressions d'ordre inférieur. Comme il est vrai pour les expressions d'ordre i qui sont les sommes de puissances semblables il sera établi en général. Or on a :
désignent des expressions symétriques de même degré que
mais d'ordre inférieur, et A, B, ... étant des entiers, à savoir : A est le nombre des exposants a, (2, ... qui sont égaux entre eux et à une certaine valeur, B est le nombre de ces mêmes exposants qui sont égaux entre eux et à une autre valeur, etc. Ces entiers sont tous- inférieurs a p, de sorte que le dénominateur de l'expression (21) ne contient pas le facteur premier/). Quant au numérateur, il est divisible par p. En effet, puisque a -{- P -h ... n'est pas divisible par p — i, les exposants a, S, ... ne sont pas tous divisibles par p — i. Donc le terme
est divisible par p. Il en est de même des termes suivants puisque ce sont des expressions d'ordre inférieur à n. Le théorème est donc démontré. Si le degré de
est divisible par /) — i, la démonstration ne s'applique plus, mais le calcul précédent permettra dans chaque cas d'évaluer le reste (mod. p) de l'expression.
Exercices I. — Déterminer x par les conditions
X ^ — 2 (mod. i4)
ar ^ 3 (mod, 17)
X ^ — 9 (mod. 21)
ar ^ 10 (mod. 22).
.II. — p étant premier a^"" — fef ~ ne peut être divisible par p sans l'être par p" (n entier > o). {Boaniakowski, Mém. Ac, St-Pétersbourg. Se. Mal. Pfiys. et Nat. (6), (i83i) p. 189).
