Résolution de la congruence
(il) x'" ^ I (mod. n).
Nombre de solutions. — On voit immédiatement que les indices i,j, ... d'une solution doivent satisfaire aux congruences :
( mi ^o (mod. I) (12) < ny ^ o (mod J)
On sait résoudre ces congruences On sait aussi (l. 33o) qu'elles ont respectivement D(m, I), D(m, J), ... solutions. Donc le nombre de solutions de la congruence (11) est
Nous poserons ce nombre égal à F„(w), ou simplement à F (m) s'il n'y a pas besoin de mettre n en évidence.
En particulier si m est premier à chacun des entiers I, J, ... il y a une seule solution, laquelle est évidemment a* = i .
Remarque. — Les racines de x"' — 1^0 {mod. n) sont les mêmes que celles de xï^('".z'")) — 1^0 mod. (n). (Généralisation du théorème du n» 10). Car on voit facilement que toute solution d'une des congruences (12) satisfait aussi à la congruence obtenue en remplaçant m par D(w, /(n)).
Cas particulier. — La congruence
x^ ^ I (mod. n)
a 2' racines, s étant le nombre des facteurs premiers de n si n est impair ou simplement pair, ce nombre augmenté de i si n est doublement pair ; ce nombre augmenté de 2 si n est plus que doublement pair.
24. Chercher le nombre des entiers qui appartiennent à un exposant donné e. — Désignons ce nombre par 'i>(e). Nous pouvons remarquer tout de suite que '^(é) = o quand e n'est pas diviseur de X(ai), mais nous ne nous servirons pas de cette remarque dans ce qui va suivre.
Les F (m) solutions de la congruence (11) sont les entiers qui
appartiennent à des exposants diviseurs de m. On a donc
(i4) 2^(rf) = F(m)
djm
m étant un entier quelconque, et la sommation s'étendent à tous les diviseurs d de cet entier.
A partir de maintenant nous ne supposerons pas que F (m) soit la fonction (i3), ce sera une fonction quelconque et nous chercherons à déterminer 'b{d) par la relation (i4). Ce problème a été résolu en même temps par Dedekind et Liouville(').
D'abord la relation (i/J) détermine la fonction 'J>, car en l'écrivant successivement pour m = i, 2, 3, ... on obtient des équations dont la première donne 'y'(ï)' la seconde 'i'(2), etc. Mais d'ailleurs pour déterminer 'b (n) il suffit de considérer les relations obtenues en faisant dans (i^), m successivement égal à tous diviseurs de 11.
On voit de celle façon que la valeur de 'j» (n) est de la forme :
(,5) ^{n) = .iF(0 + ^,/,F(c/.) 4- ... + a„F(n)
Cf-i, OLdi, ... oin étant des coefficients indépendants de la fonction F. Or lorsque F(m) se réduit à m on sait que 6 se réduit à l'indicateur ^. On a denc dans ce cas
;), q, ... étant les facteurs premiers de n, le premier signe 2^ s'étendant à ces différents facteurs premiers, le second à leurs combinaisons deux à deux, etc. Gomme tous les entiers
sont des diviseurs de n, cela nous donne à supposer (^) que la for-
(1) Dedekind, J. r. a. M., 54 (1857), p. 21.
LiouviLLE, J. m. p. a. (2) 2 (1857), p. iio. {-) Gela n'est pas une preuve parce qu'une expression peut se mettre de plusieurs façons sous la forme (i5). Par exemple
74 THÉoniE DES NOMURES
mule (i5) doit être
(,6) «")=i-(e)-2:F(;)+2"-(pî)-
Il reste à montrer que cette expression de '\) satisfait effectivement à la condition (i4).
En effet si dans le premier membre on remplace les '}((/), par leurs valeurs (i5), le terme en F (m) ne provient que de 'i^{tn) et sera F (m).
Calculons maintenant les termes en F(ô^), r) étant un diviseur de m. Ils ne proviendront que des termes '}^{r)k) du premier membre, les différentes valeurs de k n'étant composées que de facteurs premiers de m qui entrent dans m avec un exposant supérieur à celui qu'ils ont dans r), et ne contenant d'ailleurs ces facteurs qu'à l'exposant i. Soient /)i, p.2, ... jh ces facteurs premiers, F((?) se trouvera avec le coefficient + i dans l'expression de '\>{o') ; avec le coefficient — i dans les expressions de
'!'(5/'.),4'(¥i). •.•'>(5/>r); avec le coefficient -+- i dans les expressions de
'^(^PiPi), '^{^'PiP^) ... •^{^Pr-iPr):
etc.
Il en résulte que le coefficient de F (c?}. sera
C; désignant le nombre des combinaisons de /' objets / à /. Or cette somme est nulle. On le voit en faisant x = i dans la formule
(i — rr)- = 1 — C> + Clx' — ... + (- I)X:x^
La formule (i6) est donc démontrée. En particulier
Le nombre 'il [e) des entiers qui, par rapport à un module n^ appartiennent à un exposant e est
.(e)=FW-VF(0.2F(^^)...
p, q, ... étant les facteurs premiers de e et F étant défini par
GÉNÉRALISATION POUR LES MODULES NON PREMIERS yS
Exemples. I. — n = 36o := 2^ . 3^ . 5.
Alors
Soit e = 6 ; on a
F(6) = D(6, 2) D(6, 2) D(6, 6) D(6, 4) = 48 F(3) = D(3, 2) D(3, 3) D(3, 6) D(3, 4) = 3 F(2) = D(2, 2) D(2, 2) D(2, 6) D(2, 4) = 16 F(i) = D(i, 2) D(i, 2) D(i. 6) D(i, Ix) = I et
Il y a donc 48 solutions de x*^ — 1^0 (mod. 36o) dont 3o appartiennent à l'exposant 6.
II. — Soit encore n = 36o et e =: 18 qui n'est pas diviseur de y (n). On a :
ce qui était évident a priori.
25. Résolution de la congruence x'" ^ a (mod. n), a étant premier à. n. — Soient i[,ji, ... les indices connus de a et i, /, ... les indices inconnus de x, on détermine i, j, ... par les congruences
mi ^ 1*1 (mod. I) mj=ji{mod.})
Les conditions de possibilité sont que D(m, I) divise/,, que D(m, J) divise 4» etc. Si elles sont remplies, la première congruenceen/à D (m, I) solutions, la congruence enjen aD (m, J)..., donc la congruence proposée à D(m, I) D(w, J) ... solutions.
76 TliÉURIE DES NOMBRES
On démontrera facilement que toutes ces solutions se déduisent de l'une d'elles en la multipliant successivement par toutes les solutions de x'" ^ i (mod. n).
AppUcalions. I. — Nombre de solutions de la congruence
x" ^ I (mod. p*)
a étant un diviseur de p — i, p étant un nombre premier impair (').
Ici il n'y a qu'un exposant I qui est égal à p'— ' (p — i). On a D (a, I) = a. Donc la congruence a a solutions.
