D'après le théorème de Fermât généralisé, la
congruence
A't'")=i (mod. M)
admet pour racines les y (M) nombres premiers et non supérieurs à M. Ceux de ces nombres qui appartiennent, suivant le module M, à l'exposant ç (M) sont dits racines primitii^es de la précédente congruence, ou simplement racines primitives, relativement au module M.
Ainsi le nombre a, premier à M, sera racine primitive si, pour toutes les valeurs de n inférieures à cp(M), a'' est incongrue à l'unité, suivant le module M. Dans ce cas, la série des résidus des puissances
I, a, fl*, . . ., iiîî*'-*
SECTIOn m. CHAPITRE II. 5l
embrasse les 9 ( M ) nombres premiers à M et non supérieurs à M.
On peut établir de suite qu'il n'existe de racines primitives que dans des cas peu étendus.
Le module M étant décomposé en facteurs premiers, soit
Pf qy r, ... étant des nombres premiers inégaux. Tout nombre a, premier à M, sera premier avec chacun des facteurs p% q^j f^, .... et l'on aura, par le théorème de Fermât généralisé,
a?(^*)==i (mod./7»), à^y^)^! (mod. 7«*;, af(''^)EZ=i (mod.r^).
Si S désigne le plus petit des nombres divisibles par chacun des suivants :
on aura aussi
11*^1 (mod./?*), fl*^i (mod.^»*), a^^i (mod. /^), ....
La différence o^ — i étant ainsi divisible par chacun des nombres p', 9"*, r^, • . . , elle le sera par le produit M des mêmes nombres, et l'on aura
a^=^i (mod. M).
Or, ^{p") est un nombre pair, sauf le seul cas où Fou
52 COtIRS d'algèbre SUPÉaiEURB.
a j9 = 2, V = I ; de même (f{g^) est pair, à moins que ^ = 2, ^ = I, et ainsi de saite. Donc, si M renferme plus d'un facteur premier impair^ ou si, ne contenant qu'un seul facteur premier impair, il renferme le facteur 2 à une puissance supérieure à la première, deux au moins des nombres
auront un diviseur commun, et, par conséquent, le plus petit commun multiple de ces nombres sera inférieur à leur produit. Ainsi Ton aura
et le nombre ^i, pour lequel on a a®^i(mod. M),, ne sera pas racine primitive relativement au module M.
II reste à examiner le cas où M ne renferme aucun facteur premier impair ; on a alors
et je dis qu'il ny a point de racines primitives, si y est
supérieur à 2.
En effet, tout nombre impair a peut être représenté
par la formule
a =:ziii -h a'X,
et, par des élévations au carré successives, on en déduit
«** = ! 4- 2»/,, ..., fl*^' = I-h2*/V-i,
Ati, A"a, . . . , /r, étant des nombres entiers. La dernière de CCS égalités peut s'écrire
a*^ ^1 (mod.M),
SECTTON III. — CHAPITKE II. 53
si y est ]> a, et en conséquence a n'est pas racine primitive.
Il résulte de là qu*il ne peut exister de racines primitives que dans les trois cas suivants :
1^ Si le module M est un nombre premier impair ou une puissance d'un nombre premier impair;
2* Si le module M est égal au double d'une puissance d*un nombre premier impair;
3^ Si le module M est égal à 4-
Dans le cas de M := 4, on a cp(M) = 2, et le nombre — I ou 3 satisfait évidemment à la définition des racines primitives. Le cas où M est une puissance de 2 supérieure à 4 mérite une attention particulière , bien qu'il n'y ait point de racines primitives , dans le sens que nou^ attachons à ce terme*
Des racines primitives, dans le cas oii le module est un nombre premier impair.
306. Lorsque le module M se réduit à un nombre premier impair p, on a cp(M) = p — i. Dans ce cas, il existe toujours des racines primitives et il est facile d'en déterminer le nombre par le théorème suivant, dont nous empruntons la démonstration à Gauss :
Tbéouème. — Si le nombre p est premier, et que n désigne un dii^iseur quelconque de p — i , iljr a précisément <^(n) nombres qui appartiennent à l'exposant n; le symbole <f{n) exprimant combien il y a de nombres premiers et non supérieurs à n.
Supposons qu'il existe un nombre a appartenant à l'exposant n, suivant le module p ; les résidus des puissances
seront distincts et chacun d'eux sera la racine de la congruence
(a) 3c^ — i^o (mod./yj;
car l'hypothèse
a^^x (mod./?) entraîne
(3) fl*»*^! (mod./?), ou («*)'* — isiso (mod./?)» e étant Tun quelconque des nombres
donc, d'après le théorème du n^ 298, la congruence (2) n'a pas d'autres racines que les résidus des puissances contenues dans la suite (i). Par conséquent, s'il existe des nombres, autres que a, qui appartiennent à l'exposant /z, chacun d'eux doit être congru, suivant le module Pj à une puissance telle que a^.
Désignons par m l'exposant auquel appartient a^\ d'après la congruence (3), /z sera un multiple de m; on a d'ailleurs
(4) (fl*)'"^i (mod.p) ou a^^^x (mod./?),
et comme a appartient à l'exposant /{, il en résulte que me est un multiple de n. Cela exige que m soit un multiple de /{, quand e est premier à n ; les nombres m et n étant alors divisibles l'un par l'autre , ils sont égaux entre eux. Donc a^ appartient à l'exposant n, si e est premier avec n\ mais, si les nombres e et n ont un diviseur commun 0 supérieur à i , la congruence
(mod./?) peut s'écrire
(a*)^^i (mod. /ij.
ce qui montre que a^ appartient à un exposant moindre que n.
On peut conclure de là que, s*il existe un nombre appartenant à l'exposant n^ suivant le module p^ il y a précisément ^(/i) nombres qui appartiennent à cet exposant.
Cela posé y l'exposant auquel appartient l'un quelconque des nombres
relativement au module pj est, comme on sait, égal à l'un des diviseurs
(6) d, d!, d", dT, ...
du nombre p — i. Si l'on emploie le symbole ^K^) pour exprimer combien il y a^ dans la suite (5), de nombres qui appartiennent à l'exposant dy on aura, d'après ce qui précède,
^[d) = f^[d) ou ^[d]z=zO.
Pareillement, (p(rf'), (|i (ci''), ... exprimeront combien il y a, dans la suite (5), de nombres qui appartiennent aux exposants d\ d", . • • respectivement. L'unité fait partie de la suite des diviseurs (6), et comme i est évidemment le seul nombre qui appartient à l'exposant i , on a
Enfin le nombre des termes de la suite (5) étant p — i , et chacun d'eux appartenant à l'un des exposants contenus dans la suite (6), on a Tidentité
Mais on a aussi (n^ 286)
ff[d) -+-y[c^) H-y(rf'')-h... = p — i:
donc
Ô6* COURS d'algèbre SmPÉTlIEURE.
Dans le premier membre de cette égalité, ceux des termes qui ne sont pas nuls sont respectivement égaux, d'après ce qui précède, aux termes qui occupent les mêmes rangs, dans le second membre ; on peut donc supprimer de part et d'autre ces termes égaux. Mais, après cette suppression, il reste zéro dans le premier membre de l'égalité ( 7 ) ; donc il ne doit rien rester dans le second membre. D'où il suit que la suppression a porté sur tous les termes, et que l'on a
quel que soit le diviseur d.
Corollaire. — Il y ^ ^{p — i) nombres qui appartiennent à l'exposant p — i , relati\fement au module premier p; en d'autres termes, il y a, relativement à ce module, cp (p — i ) racines primitives.
Remarque. — Les nombres qui appartiennent, suivant le module premier /?, à un exposant n égal à un diviseur quelconque de p — i, sont dits quelquefois racines pri^ mitives pour la congruence x'^^=i (mod.p). Alors, d'après ce qui précède, cette congruence a n racines, parmi lesquelles il y en a ^(/i) qui sont primitives.
307. Nous établirons encore ici une proposition fort importante qui trouvera plus loin son application,
THéoEÈME. — «Si deux nombres aetb appartiennent, relativement au module premier p^ à deux exposants m et n premiers entre eux, le produit ab appartient à l'exposant mn.
En effet, soit s un exposant tel que
on aura, par l'élévation à la puissance m,
a'"'ô'"*=l (mod.yj;
SECTlOn III. — CHÀPITEE H. 5^
mais, a appartenant à l'exposant m, on a
a'^'esi (mod.p):
donc
et, par conséquent, ms est un multiple de l'exposant n auquel b appartient. D'ailleurs mein sont premiers entre eux; donc s est un multiple de n. On ferait voir de même que 5 est un multiple de m, et il en résulte que 5 est divisible par le produit mn. Or on a, par hypothèse,
a'"^i, ô"e=i [mod.p), d'où
donc le produit mn est bien l'exposant auquel ab appartient.
CoROLLÂiUE I. — Si les nombres a^ b, c^ ... appartiennent respecti\fement, par rapport au module p, aux exposants mf n, r^ . , .^ premiers entre eux deux à deux, le produit abc. appartient à r exposant mnr..,.
CoROLLÀiRB II. — Si le nombre p — i est égal au produit 2^q^r^, . . . , ^, r, ... étant des nombres premiers impairs inégaux, et si a^ b, c, ... désignent des nombres qui appartiennent respectii^ement aux exposants a*, 9^, r**, . . . , le produit abc. . . ou son résidu appartient à l'exposant p — i , et il est en conséquence racine primitive, relativement au module p,
jiutre manière de présenter les résultats qui précèdent.
308. Les propriétés que nous venons d'établir, à l'égard des modules premiers, peuvent encore être démontrées, comme nous allons le faire voir, par une méthode identique à celle dont nous avons fait usage dans le Cha-
pitre V de la Section I, en nous occupant des racines des équations binâmes ; il y a quelque avantage à faire ressortir le lien qui existe entre les deux théories.
Théorème I. — Les racines communes à deux coti^ gruences binômes de module premier p^
x'^==i (mod./?), x^~Bi (mod. p),
sont également racines de la congruence
x^^mi (mod.p)y
Q étant le plus grand commun diviseur de m et de n.
x^ — I est, en effet, le plus grand commun diviseur de x^ — I et de x" — i. Ce théorème est, par suite, une conséquence du corollaire démontré au n^ 300.
Il est évident que, réciproquement, chaque racine de la congruence x^ — i == i satisfait aux deux proposées.
Corollaire. — Si 0 désigne le plus grand commun diviseur des nombres metp — i , la congruence binôme du module premier ,
x^=^i (mod./?),
aura 6 racines qui appartiendront à la congruence
^•==1 (mod.p).
En eflct, les racines de la congruence proposée ap« partiennent aussi à la congruence
«!»-•— isso (mod.p)j
D'ailleurs, la congruence
x^ — i = o [mod.p]
a 0 racines (n^* 299), puisque son premier membre est un diviseur de x'*"^ — i ; la proposée a donc elle-même 0 racines.
SECTION III. CHAPITBE II. 5g
Si m est premier avec p — i, onaô = i,et dans ce cas la congruence x^ ^ i n'a pas d'autre racine que l'unité.
D'après ce qui précède, on peut borner l'étude des congruences binômes de la forme
ar'^^i (mod. p)
h celles dont le degré m est un diviseur de p — i .
Théoreke n. — Si a désigne une racine quelconque de la congruence de module premier
x'^E=\ (mod./?),
dont le degré m est un diifiseur dep — i , toute puissance de a ou son résidu minimum est également racine,
La congruence
a'^^i (mod./?)
entraine en eifet
^mAr^l ou («*)'"== l,
et si b désigne le résidu minimum de a^j par rapport kp^
on a
aJ^'E^hy d'où h"^^\\
par conséquent, tous les termes de la série
rt, a', «*, . . .,
ou leurs résidus minima, sont racines de la même congruence. Or, à cause de a'^^ i , on a aussi
La série précédente contient donc au plus m, termes ayant des résidus différents, et ces résidus se reproduisent périodiquement de m en /n. Si les m premiers termes
-a, a*, a', ..., a"»—*, a^ ou i
6o couBS d'algèbre srpéiicutE.
sont incongrus suivant le module p, leurs résidus sont les m racines de la congruence proposée. Dans le cas contraire, si Ton a, par exemple,
a étant premier avec p, il vient, en divisant par a"',
a*»^! (mod./y);
par conséquent, a est racine d'une congruence binAme
dr*==i (mod./>^
de degré n inférieur à m. De là résulte cette proposition :
Théorème III. — «5* a est une racine de la congruence x'^^=3 1 (mod. p)^ qui n'appartienne à aucune congruence de degré moindre x"==i (mod. p), les m racines de ta proposée seront les résidus des m puissances de a
L'analogie de la théorie que nous exposons avec celle des équations binômes conduit naturellement à appliquer la dénomination de racines primitii^cs d'une congruence binôme
x^^ni (mod./?),
dont le degré m divise p — i , à celles des racines de cette congruence qui n'appartiennent à aucune congruence de même forme et de degré moindre. Comme dans le cas des équations binômes, chaque racine primitive jotiit de la propriété de donner toutes les autres racines par ses diverses puissances.
Il faut remarquer que, chaque racine non primitive de la congruence jr^rr^i (mod. />) appartenant à une congruence de même forme et de degré moindre, eiieap-
SECTION III. — GHÀPITHE II. 6l
partient aussi à une troisième congruence de même forme, et dont le degré divise celui de la proposée.
309. Voici maintenant comment on peut établir Texistence des racines primitives.
Considérons la congruence
(i) ar'^Eisi [mod./7J,
et supposons d'abord que m ne contienne qu'un seul facteur premier 9, que Ton ait
toute racine non primitive de
(2) x^^^i (mod.p)
appartient à une congruence
x*^i [mod.p),
dont le degré 0 est un diviseur de q^ et même de q^^^ ; et, par conséquent, cette racine appartient aussi à la congruence
(3) x^^^'~i [mod.p).
D'ailleurs les racines de (3) sont aussi racines de (2); leur nombre est 7"^*, par conséquent celui des racines primitives de la proposée est
7»*— 7»^* ou <7«* (i— -)• Supposons maintenant m quelconque, et soit
q, r, . . . , J désignant des facteurs premiers inégaux. Considérons les congruences
(4) x^^^i [mod.p), x''^^i (mod./?j,..., ar* ^i [mod.p]^
62 COURS d'algèbue supérievbe.
et désignons par a une racine primitive de la première,
par b une de la deuxième, etc., par /une de la dernière.
11 résuite du théorème démontré au n^ 307 que le résidu
du produit
ab, . .1
est une racine primitive de la proposée (5} a:^'*'-^...*^^, (mod./7).
Mais on peut aussi établir ce point de la manière suivante : il est d^abord évident que ab. . ,1, ou son résidu, est racine ; car on a
ai^=Bi, b'^*=i, /'^=i (mod./j),
et, par suite,
(ab. . .1)^^''"' • -'^=1 (mod./?).
Maintenant, si ce produit n'est pas une racine primitive de la proposée, il sera racine d'une congruence
a^^i (mod. />],
dont le degré 0 sera un diviseur de m, et il y aura au moins un facteur premier de m, qui entrera dans d moins de fois que dans m. Admettons que le facteur ^ soit dans ce cas; alors 0 divisera r/**^* /•* . . .5^, et, par suite, ab.^A sera racine de la congruence
x^'^"*'"** • •' ^i (mod.^); on aura donc
[ab, . .Z)'/'^''^*- • •'"*=i (mud.77):
fl
mais on a aussi
SECTIOlf III. CnAPITRB II. 63
et, par la division.
On voit par là que a est racine des deux congruences
et, par suite, de
x^^^^^i (mod./)),
puisque q^^^ est le plus grand commun divîseur entre les degrés des précédentes ; a n'est donc pas, comme on l'a
supposé, une racine primitive de x^^^zbi (mod. p).
Il est ainsi démontré que, si a, i, . . . , c désignent des racines primitives respectivement de la première, de la deuxième, etc., de la dernière des congruences (4)> le produit ab. • ,c, ou son résidu, est une racine primitive de la congruence proposée (5). En outre, en répétant ici le raisonnement dont nous avons fait usage au n^ 104, à Toccasion de Téquation binôme, on prouvera que toutes les racines, tant primitives que non primitives, de la congruence (5), sont représentées par la formule
€ib . . . /,
où l'on doit prendre pour a, i, . . . , / toutes les racines respectivement de la première des congruences (4), de la deuxième, etc., de la dernière; et que la même formule donne toutes les racines primitives, en prenant pour a, b, . . . , / les diverses racines primitives des congruences auxquelles elles appartiennent. Comme le nombre des
racines primitives a est ^'^ ( i j > que celui des racines
A est rM I )»•••» celui des racines /, ^^ ( i U on
en conclura que le nombre des racines primitives de la proposée est
ce qui est le résultat déjà obtenu.
Théorème relatif aux résidus des puissances dont le degré est un div^iseur de p — i .
310. Théorème. — Le module p étant supposé pre^ mier et 0 étant un div^iseur de p — i , soient x% et Ç deux nombres compris entre zéro et p ; si l'on a
^•=5 (mod./?), on a aussi
Ç • ==i (mod./?); et, réciproquement, si Von a
Ç • =21 (mod./?),
la congruetïce
«•eisÇ (mod./?)
a 0 racines.
La première partie du théorème est évidente ; car, s!
Ton a
x*==5 (mod.p),
en élevant les deux membres à la puissance ^—z — 9 on a
j:^-*=:Ç • (mod./>),
et, à cause du théorème de Fermât,
p-J Ç • =Li (mod./?).
Réciproquement, supposons que Ton ait ^ ==^1, ou
retranchant chaque membre de cette égalité de xP^* — i ,
il vient
x/»-»— i-pQ = a-P-»-Ç • ={x^) • — Ç • .
Or le second membre admet pour diviseur x^ — Ç ; il en est donc de même du premier membre xP"* — i — pQy et par conséquent , en vertu du théorème démontré au n^ 299, la congruence
«• — Ç E= o ( mod. p )
a 0 racines. Ce qull fallait démontrer.
Corollaire. — Si p est un nombre premier, et qu'en décomposant p — i en facteurs premiers on ait trouvé
les racines non primitives de la congruence
xP—^ — iE=:o (mod./?),
racines qui appartiennent toutes à l'une au moins des congruences
Ri± Pzl Pzl P.-1
X =11:1, j?'z=:i, X -iHzsi, ,.,, x iisi,
sont des résidus de carrés, ou de puissances q y ou de puissances r , etc. , ou de puissances s ; et, réciproquement, tout nombre résidu d'un carré, ou d'une puissance q, ou etc., est racine de l'une des congruences précédentes et n'est pas racine primitiv^e du nombre premier p.
Ce corollaire résulte immédiatement du théorème qui
s. — Alg, sup,, u. . S
66 COURS d'algèbre supériburb.
précède; on peut ajouter que, parmi les nombres
il y en a la moitié qui sont des carrés (résidus de carrés ), la ^**"* partie qui sont des puissances y, la r'*"* partie des puissances r,..., la 5**"* partie des puissances s\ et, plus généralement, si Ton ne considère parmi ces nombres que ceux qui sont à la fois des puissances 2, ^ , r, ..., la 5**™* partie de ces derniers sera en même temps des puissances s. En efTet, les nombres qui sont à la fois des résidus de carrés, de puissances ^, de puissances r, ..., satisfont aux congruences
X £131, x^=^i, x'^si^i, ... (mod. /?j et, par conséquent, sont racines de
x*^'"e£zi (mod. pj:
leur nombre est donc -^ ; pareillement, le nombre
de ceux qui sont en même temps des puissances s — : il est donc la 5**"* partie du nremicr.
