I . 2 . 3 ... (/) — i) = — I (mod.p
donc le théorème est démontré.
190. Des comjruences en général. Les congruences proprement dites renferment, comme les équations, une ou plusieurs inconnues. Soit x une inconnue; il y a lieu d'étudier les congruences de différents degrés par rapport à a?, telles que
ax-\-h=:0^ (mod. w), ax^ -\-hx-\-c^:Oj (mod. w), et, en général,
F(a?) = ftû^" -\- «lic""' 4" • •• -j- Cin-\x -|- »n = o (mod. w),
les coefficients étant des nombres entiers.
On dit qu'un nombre entier iCi est racine de la congruence
F(a?) ^o (mod. w),
lorsque le résultat correspondant F(a?i) est divisible par le module. Ainsi, la
congruence
3a? — 1=0 (mod. 5)
admet la racine x = 2, et la congruence du second degré
x"^ -\- $x — 3 = 0 (mod. 7)
est satisfaite pour a? = 3.
Supposons que X{ soit racine de
F(â?) = o (mod.w); il viendra
F(i(?i) = o (mod. m).
Or, quel que soit l'entier A, on aura aussi
F {Xi '\- km) = o (mod. m) ; car. si on développe le premier membre, on trouve
Y[x^-\-km)==Y(xy)-\-kmY'(x,)-\ F''(a?,)+...
Comme le module m est facteur dans tous les termes à partir du second, si F(iCi) est divisible par m, il en sera de même de F(a?i +A7?i). Donc, étant
donnée une racine de la congruence, on en déduit une infinité d'autres par la formule
X = Xi -\-km
où A' est un entier quelconque. On peut toujours déterminer k de manière que la valeur de x soit comprise entre o et m, et c'est celle-ci que l'on considère seulement; on fait abstraction de toutes les autres valeurs qu'on regarde comme équivalentes à la première.
D'après cette remarque, on regarde comme racines d'une congruence
F(a?) = o (mod. m)
les valeurs de x inférieures au module pour lesquelles F(^)cst divisible par m.
Il importe de faire remarquer immédiatement qu'il est toujours possible
de transformer une congruence de manière que ses coefficients soient compris
entre o et m ou bien encore, entre et -1 — «En effet, on peut remplacer
la congruence
«oic'* -|- aia?""' -{- '•'-\-an^o (mod. m) par
«oa?** -|- «lit?""' + \- Œn — m ibox"" + hiX'^~^ -f- [- 6„) = o (mod. w),
ou bien
[ao — m&o)a?'*-|- {ct'ï — mbi)x*'~^ -|- ••• + an — mbn = o (mod. w),
et les coefficients bm 6i ••• sont quelconques. Désignons par qo, Qi •••, ?'o, ?'i, •• les quotients et les restes des coefficients ao, at, «2, ••• divisés par m et remplaçons les coefficients b par les quantités q; on aura
[ao — mgo)^** -}- (^i — mgi)a?"~* -|- • • • -f- f*n — mqn = o (mod. w),
c'est-à-dire
rox'' -{-rix^~^ -\- *" -{-Tn^o (mod. m).
Les quantités r sont comprises entre o et m ou entre > -4 — en
employant les restes négatifs. Comme exemples de cette transformation,
soient les congruences
1237a? — 4096 = 0 (mod. 27), I yx^ -j- ï 20?^ -j- 2557^ -|- 200? -[- 49 = o (mod. 1 2).
En divisant les coefficients d'un côté par 27 et de l'autre par 12, les restes permettent de les ramener aux deux suivantes :
— 50; -]- 8 ~ o (mod. 27), 5x^-{-x* — 4a; 4-1=0 (mod. 12).
Remarquons encore qu'une congruence
ttox"" -}- «ia?"~* 4" 1- «H = o (mod . m)
est satisfaite, quel que soit a?, lorsque tous les coefficients sont divisibles par m; on dit, dans ce cas, qu'elle est identique. Au contraire, si tous les coefficients excepté le dernier «„ sont divisibles parle module, la congruence est impossible.
Une congruence peut être impossible dans d'autres circonstances. On a
F(a? + w) ~ V(x) = mr{x) -] r'{x) -\ ;
la différence du premier membre est donc divisible par m et
¥{x -\- m) = F (a?) (mod. w).
Les restes de F(ic -f- m) et de F(a7) pour le module m seront identiques; il en sera de même pour ^{x '\- i -\- m) ç^i ^ {x ■\- i), ainsi de suite. Il résulte de là qu'en donnant, dans la congruence
F (a?) = 0 (mod. m)
à X toutes les valeurs entières possibles, les restes des résultats correspondants pour le module devront faire partie de la suite
et revenir périodiquement de m à m. Or, en général, ces restes ne reproduiront pas nécessairement tous les termes de cette suite, et, par conséquent, il ne sera pas toujours possible de résoudre en nombres entiers une congruence donnée. Par exemple, pour la congruence
x^ — 23? + 3 = 0 (™od. 5),
si on substitue les entiers o, i, 2, 3, 4 dans le premier membre, on trouve les résultats
dont les restes pour le module 5 sont :
- ûOG —
Pour tous les entiers positifs ou négatifs substitués à a?, les restes seront toujours ceux qui précèdent; la congruence proposée est donc impossible puisqu'aucun résultat n'est divisible par le modale.
Au contraire, la congruence
x^ — iix-}-30 = o (mod. 4)
admet les racines i et 2. Les résultats des substitutions o, i, 2, 3 étant
il Tient pour les résidus relativement au module 4,
Les restes des divisions des coefiBcients par 4 étant i, — i, 2, on peut remplacer la congruence donnée par x- -f- x -j- 2 = o et on arriye encore plus facilement au même résultat.
191. Des congruences de module premier. Soit p on nombre premier;
la congruence linéaire
ax = 6 (mod. yj
n'admet qu'une seule racine. En effet, on peut toujours supposer que a et b
sont inférieurs au module, et, dans ce cas, on sait que les nombres de la
suite
a, 2a. 3a, ..., (p — i)ff
ont pour résidus relativement à p
Il n'existe qu'un seul nombre xa de la première suite qui soit congru au nombre b de la seconde; donc, la congruence proposée ne possède qu'une racine. Il en est encorejainjiLJorsque p n'étant pas premier, a est premier avec p.
Considérons, maintenant, la congruence de Tordre n
(i) 'F{x) = a.x'^ -\-a,x*-^ -^ '" -\-a^,^o (mod.p),
p étant un ni)mbre premier; elle ne peut admettre plus de 71 racines. Supposons,, en effet, qu'elle ait 7i -\- i racines savoir :
«1» ^-7. y-it •■ , ^-f-i»
et soit :/.\ la plus petite. Posons •
(a) x = yJ^y,^.
La transformée en y aura pour terme indépendant F(ai) qui est congru au module; en le supprimant, la congruence en y sera de la forme
y{h^if-' -l-/;,7/»-2] [-/^„,) = o (mod.;)).
Elle admet autant de racines que la proposée; d'après la relation (a), ces racines sont :
aa - a,, «s — a,
iS'-n-f I ÛC| .
Le premier membre de (2) est donc divisible par /?, si on remplace y par l'un des nombres
a.2 — ai, «5 — «1,
or, ils sont premiers à p, et c'est le polynôme entre parenthèses qui doit être divisible par />; en d'autres termes, ces nombres sont les racines de la congruence
^02/""' +^1^'*"^ + h ^«-1 ^o (mod. 2^).
Donc, si la congruence du degré n possède plus de n racines, on peut en déduire une autre du degré n — i ayant plus de n — i racines. Par une transformation analogue, on trouvera une congruence du degré n — 2 ayant plus ée n — 2 racines; ainsi de suite. On arriverait de cette manière à une congruence du premier degré qui aurait plus d'une racine; ce qui est impossible. Donc, toute congruence de module premier ne peut avoir plus de racines qu'il n'y a d'unités dtuis son degré.
Une congruence remarquable de module premier est la congruence binôme
ajP"' — 1=0 (mod. ;;).
En vertu du théorème de Fermât, elle est satisfaite par tous les nombres de la suite
Cette propriété fournit une nouvelle preuve du théorème de Wilson, Considérons, en effet, la congruence
[x — i)[x — 2) ...[x — (p — i)] — {x^-^ — i) =0 (mod. 7?);
la puisssance xp~^ disparraissant par la soustraction, elle est du degré jo — 2; mais elle est satisfaite par les jo — i nombres
et elle doit être identique ; les coefficients des diverses puissances de x sont divisibles par p ainsi que le terme indépendant; on a donc
i.2.^...{p — i)-l-i=o (mod.p).
C'est le théorème de Wilson.
Lorsque le premier membre d'une congruence
F(a?) = o (mod./))
de degré inférieur à p est un diviseur de l'expression
x^-' ^ i-\-pf(x),
où f(x) est aussi d'un degré inférieur à p, elle admet toujours autant de racines qu'il y a d'unités dans so?i degré ; car, dans cette hypothèse, on peut poser
içP-l — I ^pf^x) = ¥{x) . (i)(x).
Le premier membre de cette égalité est divisible par p lorsqu'on remplace x successivement par les entiers
il en résulte que le congruence de degré p — i
'B(x) . 9(ic} = o (mod, p)
admet j9 — i racines. Si la congruence proposée
F(a?)=o (mod.p)
avait moins de racines que d'unités dans son degré, la congruence
9(a;) = o (mod.jo)
en aurait un nombre supérieur à son degré ; ce qui est impossible. Considérons encore les congruences de module premier
F(a?) = o (mod.p,) f(x)^o (mod. jo),
et soit D(x] le plus grand commun diviseur des premiers membres; les racines communes des congruences seront données par
D(£i?) = o (mod.jo).
Divisons, en effet, F(a:) par f{x) ; appelons Q le quotient et R le reste;
on aura
FM = Q/-(a:) + R;
mais, pour chaque racine commune, F(a;) et f{x) sont divisibles par p\ J
donc R doit l'ctre aussi. Les congruences proposées admettront les mêmes racines que les suivantes :
f{x)^o (mod.jo), R = o (mod. /)).
Par la continuation de ce raisonnement, on arrive évidemment à la proposition énoncée.
Remarquons, en terminant, que les racines d'une congruence
F(a?) = o (mod. 7?)
sont inférieures à p; elles appartiennent donc aussi à la congruence binôme
a;P~' — i=o (mod.p).
Par conséquent, pour la résoudre, on déterminera le plus grand commun diviseur D entre r(^) et xp~^ — i ; la congruence
D = o (mod.p)
admettra autant de racines qu'il y a d'unités dans son degré, puisque D est diviseur de œP~* — i ; ces racines appartiendront à la congruence proposée. 1918. Congruences du premier degré à une inconnue. Une congruence de cette espèce peut se ramener à la forme
ax = b (mod. m).
Nous avons vu que, dans l'hypothèse où a est premier avec m, elle ne p^ossède qu'une racine. En désignant par y un nombre entier, on peut remplacer la congruence par l'égalité
ax =^h -\- my ; s'il existe un facteur d commun entre a et m, on aurait :
et cette équation ne peut pas avoir lieu à moins que d ne divise h.
Supposons donc que le plus grand commun diviseur ^ de a et de m divise b; la congruence réduite
ax b
admettra une seule racine Xi ; les autres valeurs qui satisfont à la congruence proposée seront fournies par la formule
(mod.|^)
X^Xi +-T^
en attribuant à k les valeurs i, 2, 3, ... (5 — i ; ce qui donne d racines inférieures au module, savoir
à' ^' ' à Soit, par exemple, la congruence
9^ = 6 (mod. 15).
Le plus grand commun diviseur 3 de g et de 15 divise 6. On a d'abord
la congruence réduite
3^ = 2 (mod. 5)
dont la racine est 4. Les racines de la première seront donc 4» 4 + 5 = 9» 4 + 10=14.
Laissons ces cas particuliers, et cherchons une méthode de résolution de la
congruence
ax = b (mod. m).
lorsque a et m sont premiers entre eax^ Elle peut être résolue de plusieurs
manières. Développons, d'abord, — en fraction continue ; appelons -l'avant
a dernière réduite, la dernière ayant pour valeur — • On a la relation entre
deux réduites consécutives
d'où on tire
Donc, il vient
aq — pm = ( — i)**; aq — {~ i)n
nombre entier.
aq = ( — i)" (mod. m), ( — i)"ag = I (mod. m),
et en multipliant par 6,
«•( — iybq~b (mod. m).
En comparant avec la congruence proposée, on en déduit :
X = ( — lyhq^ c*est-à-dire, x =■ Iq^ si le rang n de la dernière réduite, est pair, et x= — hq^ si n est impair.
- /*oi -
Soit à résoudre la congrucnce
31a? E£ 2 (mod. 13).
On trouve
et^ pour les réduites,
par suite, g = 5 et, comme n est impair, a? = — 2 . 5 = — 10. La formule de résolution sera donc
Si on pose /c == i, il vient a?= 3 qui sera l'unique racine positive plus petite que le module.
Soit encore la congruence
17a? = 3 (mod. 39).
On a
d'où on tire pour les réduites
par suite, œ= — 3X 16= — 48. Il vient ainsi pour la formule de résolution
La valeur k = 2 donne a? = 30 qui est la racine positive plus petite que le module.
Lorsque le module de la congruence n'est pas considérable, on cherche directement les résidus des nombres
ft, 2(1 y 3a, 4^, (m — i)a.
Si ucL est celui qui donne pour reste &, on aura évidemment x = (x. Ainsi, pour la congruence
170? = 5 (mod. 9)
on trouve que le nombre 4 X ^7 admet pour reste 5; donc, a? = 4 sera la
racine.
De même, lorsque le coefficient de x n'est pas un nombre très grand, on résoud la congruence en la remplaçant par Féquation
ax = b zt my;
d'oii
b ± my
On attribue à y les valeurs i, 2, 3,4, ... jusqu'à ce que le numérateur soit divisible par a. Par exemple, la congruence
50? — 8=0 (mod. 27)
revient à d'où
En posant y=\, on arrive au but et l'on trouve a; = 7. Pour la congruence
il faut prendre
70?= 100 (mod. Il) 100 — iiy
Les valeurs i, 2, 3 pour y ne conviennent pas; mais en posant ?/ = 4, on trouve ic = 8.
De même, si l'on veut résoudre la congruence
380; = 541 (mod. 17)
011 les coefficients sont considérables, on la simplifie d'abord en les remplaçant parleurs résidus pour le module 17; ce qui donne
4^= 14 (mod. 17),
et en divisant par 2 qui est premier avec 17,
2^ = 7 (mod. 17).
On en déduit la formule
ou bien c'est-à-dire
et, pour t/ = I , il vient a? = 1 2 .
Enfin, il arrive parfois que, par de simples transformations sur une congruence, on trouve la racine. Soit à résoudre
35a? = 78 (raod. 97).
Le résidu négatif de 35 est — 62, et on peut écrire
— 620? EE 78 (mod. 97), ou bien
— 31a? = 39 (mod. 97).
Ajoutons celte congruence à la proposée; on trouve
4a? = 117 (mod. 97)
4X = 20 (mod. 97)
a? =5 (mod. 97); y
donc, :r = 5. ^
ld3. Congruences du premier degré à plusieurs inconnues. Soit à résoudre le système suivant :
. ^ (mod. 12).
Si on retranche membre à membre, il vient
Sy = — 5 (mod. 12);
de sorte que l'on peut remplacer le système proposé par le suivant :
(mod. 12).
La dernière congruence a pour racine — i ou 11. Par la substitution de —- i k y dans la première, il vient
4^1? = 8 (mod. 12).
Or, dans celle-ci, il existe un plus grand commun diviseur 4 entre le coefficient de x et le module, et puisque 4 divise 8, il y aura quatre racines. En divisant par 4, on trouve la congruence réduite
0? = 2 (mod. 3);
< donc, a: = 2, et les racines de la première seront :
Il faut y ajouter la valeur y == — i. En second lieu, considérons le système
5x-\- il/ — 32r = 2, (mod. 14).
iT - 41/ — z= I, La troisième donne
x^i-\-^y-\-z (mod. 14).
En substituant cette valeur dans les deux autres, on trouve
i^y-\- nz= i . . .
, (mod. 14),
ou bien
, ^ (mod. 14).
La première peut s'écrire
2/ = — I —32: (mod. 14),
et, en vertu de celle-ci, la seconde devient
52= — 4 (mod. 14).
On substituera au système proposé le suivant :
1/ = — I — 3Z, (mod. 14).
52^ =-4- La dernière revient à
5^=10 (mod. 14), ou z^Q. (mod. 14); par suite, z = 2. La seconde congruence donne ensuite, y = — y ou -f- 7, et la troisième, a? = 3.
194. Résidus des puissances d'un nombre. Etant donné un nombre a, cherchons les restes des différents termes de la suite
(a) a, a%a', a*, ... ft", ft"'^'', ... ^
par rapport à un nombre premier impair/) qui ne se trouve pas dans a. Pour les calculer, il n'esl pas nécessaire de déterminer ces puissances; on sait que,
si r est le résidu de a'", le résidu de »'"+• sera le reste de la division du produit ar par j). D'après cette règle, si on cherche les restes des puissances des nombres 2, 4, 8, g pour /> = 13, on trouve
Puissances :
Résidus :
Puissances :
Résidus :
Puissances :
Résidus :
Puissances :
Résidus :
On s'arrête dans ce tableau à la puissance qui donne l'unité pour reste; nous allons démontrer que, pour les puissances plus élevées, les restes se reproduisent dans le même ordre.
Les divers termes de la série (a) sont premiers avec p et aucun résidu ne sera égal h zéro; mais, on ne peut trouver que p — i restes différents; donc, il y aura nécessairement, dans cette suite indéfinie, deux puissances af^ et «"^^^ qui donneront le même reste et pour lesquelles on peut écrire
a'^'^f^^a^- (mod.p).
Si on divise par af^ qui est premier avec le module, on a
ft" = I [mod.p).
Par conséquent^ il existe toujours une puissance qui admet le reste i pour le module p ; mais il peut y en avoir plusieurs jouissant de la même propriété. Désignons par g le plus petit nombre pour lequel on a
a!^ ^ I (mod. p).
Les puissances
I, a, a"^, ft', a*, .,., a^~*
donneront des résidus tous différents; comme on a :
a'J^i, ft''"^' = a, a3^^z:a^, etc.
les restes des puissances suivantes vont se reproduire dans le même ordre jusqu'à a^3 qui sera aussi congru à l'unité, etc. Les diverses puissances
donnent pour résidu l'unité; or, par le théorème de Fermât, on a :
ftP~' = I (mod.p);
par suite, il faut que p — i soit un multiple de g. Dans l'hypothèse oii g est l'exposant minimum pour lequel a» E5 i (mod. p), on dit que le nombre a appartient à l'exposant g pour le modale p; pour abréger, on dit aussi que g est le gaussien de a pour le module/). D'après la remarque précédente, le gaussien d'un nombre a pour le module p est toujours un diviseur de p — I .
On vérifie cette propriété par le tableau dans lequel, pour le module 13, le gaussien de 2 est 12, celui de 4 est 6, celui de 8 est 4 et celui de g est 3.
Lorsque g est le gaussien de a, on a
a^ = r (mod. p)\ par suite, a est une racine de la congruence binôme.
x^ = I (mod. p).
Il en sera de même d'une puissance quelconque de a et de son résidu. En effet, soit k l'un des nombres
si on élève la congruence a^^i (mod. p) à la puissance /t, il vient
a^^'^i (mod.jo), ou {a^y^ii (mod.p);
donc, a^ est racine de la congruence binôme. Désignons par r le résidu de a*; on aura : a'''=:r (mod. p), et en élevant à la puissance g
r3 E^i (mod. p)^
et r est aussi racine de la même congruence.
Il en résulte que les racines de la congruence binôme
x^^lI (mod. p)
seront les différents termes de la suite
ou les résidus de ces puissances.
Par exemple, on prend pour les racines de
x^^=. I (mod. 13),
tous les restes depuis i jusqu'à 12 inclusivement, et pour la congruence
x^ = I (mod. 13), les nombres
car 12 est le gaussien de 2 et 4 le gaussien de 8.
Lorsque le degré ti d'une congrucnce binôme
x"" = j (mod. p)
est premier avec p — ly il n'existe aucun nombre différent de l'unité appartenant à l'exposant n pour le module /?, et celle congruence n'a pas d'autre racine que l'unité. Dans l'étude des congruences binômes, il suffit de considérer celles dont le degré divise p — i.
Désignons donc par g un diviseur de p — i, et soit a un nombre qui a g pour gaussien relativement au module ;;. Les puissances
représenteront les racines de la congruence
ic^ = I (mod. p).
S'il existe un autre nombre apparlenant à l'exposant g, il doit être congru à l'une de ces puissances. Parmi celles-ci, il n'y a en réalité que les puissances dont l'exposant est premier avec g qui appartiennent à l'exposant g; les autres appartiennent à un exposant moins élevé. En effet, soit k un nombre premier avec g\ dans ce cas, on peut déterminer un nombre m de manière à satisfaire à la congruence du premier degré
km = I (mod. g)^ et, pour cette valeur de m, on aura
^fcm = ^ (mod. jo).
Si a* appartenait à un exposant e plus petit que g, on aurait (ctJ'Y^i (mod./)), et «♦"**=! (mod. jo); mais, a"'* = a (mod./)); par suite, il viendrait
a* = I (mod. p) :
ce qui est contraire à l'hypothèse que g est le gaussien de a ; il faut que e^ g. Lorsqu'il existe un facteur commun p entre k et g, la congruence
{mod, p) est identique à la suivante
(a'')P=ï (mod.»),
et la puissance a*, au lieu d'appartenir à l'exposant g, appartiendrait à
g l'exposant - pour le module p.
Par conséquent, parmi les puissances
il faut seulement prendre celles dont l'exposant est premier avec g pour avoir les nombres qui appartiennent au diviseur g àQ p — i ; il y en aura en tout (^ig), cpig) élant le nombre des entiers premiers avec g et non supérieurs à g.
195. Racines prbnitives. Prenons, pour diviseur de yj — i, ce nombre lui-même ; il y aura (^{p — i ) entiers ayant pour gaussien p — i , c'est-à-dire qu'il existe (pfp — i) nombres tels que leur {p — i)»^»»* puissance est congrue à l'unité pour le module p, tandis que leurs puissances inférieures ne le seront pas; chacun d'eux est une racine primitive du nombre p. Donc, si l est une racine primitive de p, les puissances
/, /^ /^ .... fr-'
donneront des résidus différents qui reproduiront les termes de la suite
Lorsqu'on possède une racine primitive / d'un nombre p, on obtient les autres en formant les puissances de / dont les exposants sont premiers avec p — i: nous avons vu, en effet, que ces puissances appartiennent au même exposant que/. D'après le tableau des restes, pour p= 13, le nombre 2 est une racine primitive de 13 ; ses diverses puissances inférieures à /) — I donnent les résidus
Les autres racines primitives du même nombre seront
puisque S-- 7^ ^ ^ sont les seuls nombres premiers avec 12. Or, on a :
2^ ^6, 2'= II, 2" = 7 (mod. 13),
et ce sont les nombres 2, 6, 7 et 11 que l'on prend pour les racines primitives de 13.
La détermination des racines primitives repose sur la proposition suivante :
Si deux nombres a et b appartiennent respectioe?nent aux exposants m et n, leur produit appartient à l'exposant mn, lorsque les entiers m et n sont premiers entre eux.
Par hypothèse, on a
a"*~i, b^'EEi (mod. p);
a^n^ I, })'""= I (mod. p), et
(ah)'^'' ^ I (mod p).
Il reste à démontrer que l'exposant m}i auquel appartient ah ne peut être plus petit que m?i. Soit k le gaussien de ab; on aura
{ab)''=i et (afe)"»''^! (mod. p), c'est-à-dire,
^mfe^ l)mk= j (mod. p).
Or, ft"**^^ I (mod. jo); il vient donc
^'"*^~ I (mod /)).
Puisque b appartient à l'exposant 7i pour le module 75, l'exposant mk doit être divisible par 71; ce qui exige que k divise ?i, car ?i et ni sont premiers entre eux. On prouve delà même manière que A; doit divisera; donc le gaussien k de ab ne peut être inférieur à mn
Ce principe étant démontré, proposons-nous de trouver une racine primitive d'un nombre premier p. On commence par faire choix d'un nombre a se trouvant dans la suite
Prenons a = 2, par exemple; on forme les résidus des puissances de a jusqu'à ce qu'on trouve un reste égal à l'unité; on détermine ainsi le gaussien A; de a. Si A; = p — i, a est une racine primitive; si A < p — i, on prend un second nombre b qui ne se trouve pas parmi les restes des puissances de a, et on détermine également son gaussien A'. La suite des restes pour le nombre a renferme tous les nombres qui appartiennent à l'exposant k et aussi ceux qui appartiennent à un exposant sous multiple de k 11 en résulte que k' ne sera pas un diviseur de k puisque le nombre b ne fait pas partie de ces restes; mais k' pourrait être un multiple de /c et 6 appartiendrait ainsi à un exposant plus élevé; ce qui est une circonstance favorable; car on cherche un nombre qui appartient au plus grand exposant p — i .
Admettons que k' ne soit pas un multiple de A;, et déterminons le plus petit commun multiple d de A; et k' ; partageons ensuite ô en deux facteurs h et li'
premiers entre eux, et tels que k soit divisible par h et k' par h' ; alors a^
kl k k^
appartiendra à l'exposant li et b^' à l'exposant /i'; par suite, a^ . a^' appartiendra à l'exposant hh' = ^.
En continuant ce procédé qui conduit toujours à un exposant plus élevé, on arrivera finalement à un nombre qui appartiendra à l'exposant p — i, c'est-à dire à une racine primitive du nombre jo.
Comme exemple, cherchons une racine primitive de 103. En choisissant d'abord « = 2, on trouve, pour la suite des résidus des puissances de 2 pour le module 103.
Le gaussien de 2 est 51. Le nombre 3 ne se trouve pas permi ces restes. Prenons donc & = 3 et cherchons les résidus des puissances successives de 3 pour le module 103. On obtient
Le gaussien de 3 est donc 34. On a
51 ==3 X 17 et 34 = 2 X 17; le plus petit commun multiple entre A; et /:' est 3 X 2 X 17= 1 02 =^ 5 1 On peut prendre maintenant
nombres premiers entre eux et qui divisent 51 et 34, Le produit
appartient à l'exposant 51X2= 102, et, par conséquent, c'est une racine primitive de 103. Or, d'après les derniers résidus, on a :
3" = 102 (mod. 103).
La racine primitive est ainsi 2 X 102 = 204 et comme
204^101 (mod. 103),
c'est le nombre joi qu'il faut choisir pour la racine primitive de 103.
i.a méthode pour trouver les racines primitives exige souvent des calculs très laborieux. On a construit des tables qui donnent la plus petite racine primitive des nombres premiers jusqu'à une certaine limite. Nous terminerons ces notions sur la théorie des nombres par un tableau renfermant la plus petite racine primitive des nombres premiers plus petits que 200.
Nombres.
Rac. prim.
Nombres.
Rac. pi'im.
Nombres.
lOI
Rac. prim.
Nombres.
Rac. prim.
Nombres.
Rac. prim.
FIN DR LA THEORIE DES EQUATIONS
I NTRODUCTION
