NOMBRES PREMIERS A UN NOMBRE BONNE
quadratique, et ceux-là seuls. En particulier, les diviseurs premiers impairs de la forme x^ + y* sont les nombres premiers de la forme 4n + 1, les diviseurs premiers impairs de la forme x^ — 3y' sont les nombres premiers de la forme i2n =b 1.
^6. — Sar le nombre de nombres premiers à un nombre
donné et non supérieurs à lui.
527. Nous avons vu au n" 515 comment, dans certaines questions d'Arithmétique, s'introduisait le nombre des nombres premiers à un nombre entier positif a et inférieurs à lui. Ce nombre, si a n'est pas un, se désigne par le symbole 9 (a). Si a est égal à un, 9(a) = 9(1) est par défînition égal à un. C'est pour embrasser le cas de a = I qu*on dit habituellement que ^(a) désigne le nombre de nombres premiers à a et non supérieurs à a. ^(a) est une fonction numérique de a, c'est-à-dire que la valeur de 9 (a) est déterminée quand on se donne le nombre entier positif a.
Le calcul de la valeur de cette fonction repose sur l'important théorème que voici.
Si a, 6, sont des nombres entiers, positifs, premiers entre eux, on a
Cette proposition est évidente quand Tun des nombres a, b est égal à un ;
excluons donc ce cas. Si Ton considère un nombre plus petit que ab, il
pourra se mettre sous la forme ax + y, y étant le reste de ce nombre
(mod. a) et x étant un nombre entier moindre que 6; réciproquement,
tous les nombres plus petits que ab s'obtiennent en remplaçant dans
Vexpression précédente x par 0,1,2, ...,6 — 1 et j^ par 0,1,2,..., a — 1.
Les nombres ax -}- y ainsi formés qui sont premiei'S à ab sont ceux qui
sont premiers à a et à 6; ceux qui sont premiers à a sont ceux pour
lesquels y est premier à a. Donnons à y une des 9(0) valeurs moindres
que a et premières à a, et remplaçons ensuite dans ax + y^ x par les
nombres 0, 1, 2, ..., 6 — 1, on obtiendra ainsi un système complet de
nombres incongrus (mod. 6), puisque b est premier à a; parmi ces
nombres il y en a 9(6) qui sont premiers à b comme dans la suite 0, i ,
2, ..., 6 — 1, car un nombre est premier à 6 en mt^me temps que son reste
(mod. b). Chaque valeur de y première à a fournissant ainsi 9(6) nombres
premiers à a6, il est clair qu'on a
Cette proposition se généralise immédiatement : si a, 6, c, dy par exemple, sont des nombres entiers, positifs, premiers deux à deux, on a
f^(abcd) = 9(a6c)9(d) = ^{ab)^{c)ff{d) s= 9(0) 9(6)9(c)9(d).
528. Supposons maintenant qu'on se donne un nombre A décomposé en facteurs premiers
A = a«6Pc^..,
a, 6, c, ... étant des nombres premiers distincts; on aura
et on est ramené à calculer des quantités telles que ^(a*), a étant premier. Tout d'abord, on a évidemment ç(«) = a — I, puisque les nombres premiers à a et inférieurs à lui sont 1, 2, ..., a — I. Les nombres premii ers à a* et moindres que a* sont ceux des nombres
qui ne sont pas divisibles par a; les multiples de a qui sont contenus dans cette suite sont
leur nombre est a*""* ; le nombre des termes de la suite 1, 2, 3, ..., a* qui ne sont pas divisibles par a est donc a« — a»""* = a^^^ia — I); on a donc
ç(a«) = a^'-^ia — l) et, par conséquent,
ç(A) = a*-*6^-*cT-*...(a - 1){6 — I)(c — I)...
= '(' -iX' -!)('- 9- •
529. Soient 1, d, d', d", ..., A les diviseurs de A, diviseurs que Ton a appris à former au n° 165, on a
égalité que l'on écrit souvent sous la forme symbolique
le signe £ indique que le second membre est une somme de termes analogues à ?(c{}, et il est entendu que d doit être remplacé successivement par chacun des diviseurs de A, y compris 1 et A.
La vérification de ce théorème est très facile en partant de Texpression donnée au n^'lôB pour les diviseurs d'un nombre décomposé en fadeurs premiers, et de l'expression précédente de la valeur de la fonction ç. En voici une démonstration purement arithmétique.
Le plus grand commun diviseur d'un nombre quelconque et de A est un des nombres l,rf,d', ..., A. Séparons les nombres 1,2, 3, ..., A en groupes; dans chaque groupe mettons ceux qui ont avec A un même plus graod
commun diviseur, d par exemple. Tous ces nombres^ si on les divise par
rf, donneront des quotients premiers à -i, et non supérieurs à —,; inver-
sèment tout nombre non supérieur à -i, premier à-i, si on le multiplie
par dy acquiert avec A le plus grand commun diviseur d. Donc, il y a dans
le groupe considéré çf-? ) nombres; donc on a, en employant la notation
précédemment expliquée,
étant entendu que d doit être remplacé successivement par tous les
diviseurs de A ; mais les nombres -? que Ton obtient ainsi ne sont autre
chose, dans leur ensemble, que les diviseurs de A; on peut donc écrire tout aussi bien
§ 7. — Des cong^ruences à une inconnue.
530. On a déjà traité des congruences à une inconnue, dans le cas où ces congruences étaient du premier degré, ou de la forme très spéciale
a?* ^ D (mod. p),
p étant un nombre premier.
Dans le cas général d*une congruence de la forme
f f{x) = Aa?» + Aia? *''"/ + ....+ A ,;ia? + A« ^ 0 (mod. m),
où A, Ai,j^j^;^ij A„ sont des nombres distincts, je me suis borné à définir ce qu'il fallait entendre par racine d'une telle congruence et par racines distinctes (n* 506). Le cas où le module m est un nombre premier offre un intérêt particulier et je vais bientôt m*y arrêter. Mais il convient de dire quelques mots sur la façon dont les autres cas se ramènent à celui-là. Supposons d'abord que le module m soit un produit de nombres entiers premiers deux à deux a, b, c, ..., je vais montrer que Ton saura résoudre la congruence
(1) M^O (mod. wi) si l'on sait résoudre chacune des congruences
f{x) is 0 (mod. a),
(2) f{x) = 0 (mod. 6),
f[x) ^ 0 (mod. c).
Il est bien évident d'abord que chaque racine de lacongruence (1) est une racine des congruences (2) ; car si pour une valeur entière de œ, le nombre f(x) est divisible par m, il sera divisible par a, b, c, ...; réciproquement, je vais montrer comment la connaissance de nombres «, P, y»'** qiii vérifient respectivement les congruences (2) entraîne la connaissance d'une racine de la congruence (1). Pour cela, je résoudrai le problème suivant :
531. Étant donnés les nombres entiers a, 6, c, ... premiers entre eux deux à deux, et les nombres entiers «, p, y^ ■-•' trouver un nombre x qui soit congru à « suivant le module a, à p suivant le module b, ky suivant le module e, etc..
En désignant par i/?, comme plus haut, le produit abc,.., cherchons d'abord des nombres A, B, C,... respectivement divisibles par les nombres
entiers—, -j-, —, ... et congrus au nombre 1, suivant les modules respectifs a, 6, c, ...; il suffira de résoudre par rapport à A', B', C, ... les congruences
(mod. a), (mod. b), (mod. c),
ce qui est possible, puisque— = 6c... est premier à a, que -r- est premier à 6, etc.. ; on prendra ensuite
A=:5ÎA', B = >', C = ^G',...;
le nombre
jPo = A« + Bp + Cf + ...
satisfera aux conditions imposées : en effet, B, C, ... étant divisibles par/7, on a
a?o ^ A« ^ « (mod. a),
etc.. Tout autre nombre x satisfaisant aux mêmes conditions s'obtiendm en ajoutante x^ un multiple de m, puisque la difféi*ence x — Xq doit ôtrc divisible par a, 6, c, ... et, par suite, par m. Cette méthode a cet avantage que le calcul des nombres A, B, G,... ne dépend pas de a, p, y> -..f mais seulement de a, 6, c, ... .
532. Ceci posé, revenons à la pren)ière question : les nombres a, p, y* —
étant respectivement des racines des congruences (2) et le nombre o^q étant pris comine on vient de l'expliquer, on a
/(jPo) ^- r(*) ^ 0 (mod. a),
rW - r(P) ^ 0 (mod. b):
le nombre ^(^o) étant ainsi divisible par a, 6, c, ... est divisible par m: ainsi x^ est une racine de Ja congruence (1). On remarquera que tout nombre x congru respectivement à «, p, y» *** suivant les modules respectifs a, b, c, ..., fournira Jamème racine que .r^, puisque ce nombre sera congru à Xq (mod. m). Inversement toute racine ^Tq de la congruence (i) fournissant un système de solutions (toutes égales hx^) des congruences (2), on voit que le procédé précédent fournira certainement toutes les racines de la conjrruence (1), pourvu qu'on l'applique à tous les systèmes de nombres «> Pi T» ••• ^"^ vérifient respectivement les congruences (2).
On observera que deux systèmes distincts «, p« t, •••» «'i p'* yS -•• ^^ solutions des congruences (2), c'est-à-dire tels qu'on n'ait pas à la fois
« = «' (mod. a),
p ^ P' (mod. 6),
Y ^ y' (mod. c),
conduisent à deux solutions distinctes Xf,, â?o : on a en effet, par exemple,
a?o — Xff=: OL — a' (mod. a) ;
si donc Xq — â?ô était divisible par m, « — «' serait divisible para, de même p — p' serait divisible par 6, etc ...; or nous venons de supposer qu'il n'en était pas ainsi.
On peut donc, en décomposant en facteurs premiers le module m d'une congruence
f{x) =- 0 (mod. m),
où f{x) est un polynôme entier en a? à coefficients entiers, ramener sa résolution à la résolution de congruences de la forme
f{x) ^ 0 (mod. p"),
p étant un nombre premier.
533. Observons que toute racine de cette dernière congruence est une racine de la congruence
f{x) L 0 (mo J. p» - *).
Supposons qu'on sache résoudre cette dernière congruence ; chaque racine de la première congruence devra être congrue (mod.p'*~ *) à quelque
racine de la seconde; si donc on désigne par Xq une de ces dernières racines, on devra poser
y élant un nombre entier que Ton cherchera à cjléterminer par la congruence
AaPo + P" "■ V) ^ 0 (mod. p") ;
le lecteur un peu familier avec TAlgèbre reconnaîtra sans peine que la résolution de cette congruence se ramène en général à la résolution d'une congruence du premier degré.
Si donc on sait résoudre la congruence
f{x) = 0 (mod. p),
on saura résoudre la congruence
f{x) = 0 (mod. p*),
puis la congruence
f{x) H= 0 (mod. p'), etc.
Cette méthode, avec de légères modifications dans le cas où p est égal à 2, s'applique aux congruences de la forme
a?« — D ^ 0 (mod. p"),
eu supposant que p soit un nombre premier qui ne divise pas D. Je me contenterai d'énoncer les résultats.
534. Si p est un nombre premier autre que 2, qui ne divise pas D, la condition nécessaire et suffisante pour que la congruence
0?» — D = 0 (mod. p")
soit possible, est que la congruence
a?2 — . D = 0 (mod. p)
le soit-elle même. On reconnaît d'ailleurs directement que la congruence proposée ne peut avoir que deux racines incongrues (mod.p"). La congruence
a?«— D^O (mod. 2"),
où D est un nombre impair, admet pour solutions tous les nombres impairs, si n est égal à un ou à deux : elle admet donc une solution dans le premier cas, deux dans le second.
La congruence
a?* — D = 0 (mod. 8),
DES CONGRUENCES À UNE INCOxNNUE. 493
OÙ D est un nombre impair, n'admet de solution que si D est congru à un (mod. 8). Si cette dernière condition est vérifiée, la congruence admet quatre racines distinctes, savoir 1, 3, 5, 7. La congruence
a-s — D^O (mod. 2"),
où D est un nombre impair et n un nombre plus grand que 3, n'est possible que si Ton a D = 1 (mod. 8) (*).
Si cette condition est vérifiée, la congruence proposée a quatre racines distinctes.
Diaprés ces résultats partiels, il est aisé de reconnaître si la congruence
jc' = D (mod. m),
où D est un nombre premier à m et où m est de la forme p*<?V'"-» ou 2''p*9^7..., est possible ou non, et de calculer le nombre de ses solutions distinctes : p, q, r, ... désignent des nombres premiers autres que 2.
§ 8. — Des cong^rnences à une tncoiinae. Cas où le module est un nombre premier.
535. Arrivons maintenant aux congruences prises suivant un module premier p. Mais auparavant faisons quelques remarques générales sur les nombres congrus suivant un module premier p.
En généra], quand on considère un module quelconque m premier ou non, les nombres congrus suivant ce module peuvent être regardés comme équivalents, en ce sens qu'ils peuvent se substituer les uns aux autres dans les opérations faites sur des nombres entiers, qui ne comportent que des additions, soustractions et multiplications, à condition, bien entendu, qu*on néglige dans les résultats les multiples de m. Gela revient à dire que les congruences, prises toujours suivant le même module m, peuvent être traitées comme des égalités. En ce sens, les multiples de m doivent être regardés comme équivalents à 0. Toutefois, lorsque m n'est pas premier, il s'introduit une différence capitale avec les théories ordinaires ; c'est que, en eiïét, un produit de facteurs peut être divisible par m sans que Tun des facteurs soit divisible par m. En d'autres termes, un produit peut être congru à 0 (mod. m) sans que Tun de ses facteurs soit congru à 0, tandis qu'un produit de nombres entiers ne peut être nul que si l'un de ses facteurs est nul.
Au contraire, lorsque le module est un nombre premier p, cette analogie
1. Cest dans cd cas qu'il y a lieu de modifier la méthode générale; pour déduire une racine x de la congruence proposée d'une racine xg de la congruence x* = D (mod. 2'*~' v, on posera x = Xf^ -{• t^^^pf et l'on cherchera à déterminer y de manière à satisfaire à la proposée.
Idi LEÇONS D ARITHMÉTIQUE.
subsiste. Si l'on convient de dire, en réservant essentiellement cette façon de parler au cas où le module est premier, d'un nombre congru à O(mod.p), qu'il est nul (*) (mod. p), on peut dire : Un produit de facteurs ne peut ^tre nul (mod. p) sans que Tun de ses facteurs le soit. Dans le même ordre d*idées, en supposant toujours qu'il ne soit question que de congruences prises suivant le module premier p, il serait naturel de remplacer Fexpression congrus (mod. p) par Texpression égaux (mod. p). Je conserverai toutefois le mode de langage habituel. En ce sens il n*y aurait que p nombres distincts, savoir 0, 1, 2, ...,p — 1, tous les autres étant congrus (mod. p) à ceux-IiL
536. Étant donnés deux nombres a, b dont le second n'est pas nul (mod. p), il y a un nombre et un seul, si Ton néglige toujours les multiples de p, qui vérifie la congruence
6a? ^ a (mod. p).
Il serait naturel, ainsi que Gauss Va. proposé, de regarder ce nombre comme
le quotient (mod. p) de a par b et de le représenter par le symbole -7 (mod. p).
Seule, la division par le nombre 0 demeure impossible. Ces fractîoRS symboliques T (mod. p), qui représentent en réalité des nombres entiers,
pourraient être soumises à des règles de calcul pareilles à celles des fractions ordinaires : on pourrait multiplier leurs deux termes par un même nombre non nul (mod. p), etc..
537. Dans le même ordre d'idées, il est naturel d'appeler identiquement vongru à zéro (mod. p) un polynôme dont les coefficients sont nuls (mod. p), c'est-à-dire tout polynôme qui peut être mis sous la forme p^ic)^ if(x) étant un polynôme entierenaBàcoefficients entiers. Deux polynômes à coefficients entiers seront identiquement congrus (mod. p) si leur différence est un polynôme identiquement congru à zéro. On reconnaît de suite que, si on fait des opérations d*addition, de soustraction, de multiplication sur divers polynômes à coefficients entiers, on peut remplacer dans ces opérations ces polynômes par d'autres polynômes qui leur soient identiquement congrus (mod. p). Les deux séries d'opérations fourniront deux polynômes identiquement congrus (mod. p). Si dans un polynôme entier en x, à coefficients entiers, on appelle terme du plus haut degré le terme du plus haut degré dans ce polynôme dont le coefficient ne soit pas nul (ra6d. p), si Ton définit de même le terme du plus bas degré, on reconn(&U de suite que dans le produit de deux polynômes entiers en x, à coefficients entiers, les coefficients des termes de plus haut degré et de plus bas degré sont respectivement congrus (mod, p] aux produits des coefficients des termes du plus haut degré d'une part, et des termes du plus bas degré de l'autre, en sorte que
t. Je dois à M. Borel cette exproMioD, ainsi qae la forme donnée à quelques-anes des idées qai sont exposées ici.
Je produit ne sera certainement pas identiquement congru à zéro, si Tun des deux facteurs n'est pas lai-méme identiquement congru à zéro. Ce théorème s'étend immédiatement au produit d'autant de polynômes qu'on voudra. On voit aussi qu'en appelant degré d'un polynôme le degré du terme le plus élevé défini comme plus baut, on peut dire que le degré du produit de deux polynômes entiers en x est égal à la somme des degrés des deux facteurs. Enfin étant donnés deux polynômes entiers en a?, f(x) et^» (aï), on dira que f{x) est divisible (mod. p) par t(a?) s'il existe un polynôme Q{x) entier en x, tel que le polynôme f{x) soit identiquement congru au produit des polynômes ^(x)^ Q(x). Le lecteur qui connaît la théorie du plus grand commun diviseur algébrique reconnaîtra sans peine que cette théorie s'étend, aiusi que ses conséquences les plus importantes, à la divisibilité (mod. p). Je laisserai de côté ce sujet, malgré son importance, pour m'arréter sur quelques résultats d'ordre plus élémentaire.
538. Si un polynôme f(x) entier en x devient nul (mod. p) quand on y remplace x par le nombre entier a, c'est-à-dire si f{a) est divisible par p, le polynôme f{x) est divisible (mod. p) par a? — a.
En effet f[x) — f{a) est algébriquement divisible par {x — a) et le quotient est un polynôme à coefficients entiers '^{x); on a donc identiquement
/Tœ) = (a? — a)if{x) + f{a) ;
mais, f(a) étant, par hypothèse, un nombre divisible par p, la proposition est évidente.
Réciproquement, il est clair que, si le polynôme f{x) est divisible (mod. p) par X — a, a étant un nombre entier, le résultat de la substitution de a à X dans f{x) est nul (mod. p).
539. Si, a, b, c, ... étant des nombres entiers dont deux quelconques ne sont pas congrus (mod. p), le polynôme f(x)i entier en x, est divisible [mod. p) par x — a, par x — 6, par x — c, ..., il est divisible (mod. p) par le produit {x — a){x — b)(x — c)... .
En effet f{x) étant divisible (mod. p) par x — a, on peut écrire identiquement
f[x) = [x — a)f^{x) -r pA^,
A, étant un nombre entier et fi{x) un polynôme entier en a; à coefficients entiers; en remplaçant dans le résultat x par 6, on obtient, puisque f{b) est divisible parp^
(6-ay,(6)--0 (mod.p);
puisque h — a n'est pas nul (mod. p), on a donc
f^{b) ^ 0 (mod. p) :
on en conclut que fi(x) est divisible (mod. p) par x — 6, de même par» — c, etc.; on peut donc écrire identiquement
fii^) = (« — CL)fi{^) + i^Aj,
A2 élanl encore un nombre entier et f^ix) un polynôme entier en x, à coefficients entiers; en remplaçant dans {x — «{/;(«) + Mi» fM V^^ cette valeur, on en conclut qu'on peut écrire identiquement
f{x) = (œ — a)(a? — b)f^(x) + p1fi{x),
'^i(x) étant un polynôme entier en x du premier degré, à coefficients entiers. En remplaçant dans cette identité x par c, on en conclut, puisque . f{c) est divisible par p,
0 = (c — a)(c — by^ic) (mod. p);
comme aucun des nombres c — a, c — h n'est nul (mod. p), on en conclut que fiic) est nul (mod. p), ou, si Ton veut, que f^{x) est divisible (mod. pj par X — c. Le raisonnement se continue; on pourra, dans Tidentité
f{x) =i (oî — a)(aj — 6)/i(aî) + p^x),
remplacer fj^x) par un polynôme de la forme [x — c)f2{x) + pAj, fjix) ayant encore ses coefficients entiers et A3 étant un nombre entier; on obtiendra une identité de la forme
f{x) = [x — o)(aî — 6) [x — cy^ix) + p^i(x),
où 4'2(^) <ist un polynôme entier en x, à coefficients entiers, du second degré, et cette identité montre bien que le polynôme f(x) est divisible (mod.p) par [x — a){x — b)(x — c). En général s'il y a r nombres a, 6, c, ... , on mettra f (x) sous la forme.
fj^x) étant un polynôme entier en a?, dont le degré est n — r si le degré du polynôme f{x) est n, et dans lequel le coefficient de la plus haute puissance de x est le même que dans f{x), ainsi qu'il résulte de la théorie de la division algébrique. Quand à 1f^i(x), c'est un polynôme entier en x de degré r — 1.
540. Il résulte de là qu'un polynôme du degré n ne peut pas s'annaler (mod. p) pour plus de n valeurs de la variable, incongrues deux à deux (mod. p).
Si, en effet, dans l'identité précédente, on suppose que les nombres a, 6, c, ..., /, incongrus deux à deux, soient en tiombre n, on peut écrire identiquement, en désignant par K le coefficient de x^ dans f{x)
f[x) = K(a? — a){x — b)(x — c),..{x — l) +Ptn-i(«)>
4'n 1 étant un polynôme à coefficients entiers : si f{x) pouvait s'annuler
;mod. p) pour un nombre entier o^o incongru (mod. p) à a, 6, ..., /, on voit, en faisant a? = j?o ^^ins l'identité précédente, qu'on aurait
K (a?o — a) (a?o — 6) (xq — c) ... {x^ — 0 ~ 0 (mod. p),
ce qui est impossible.
Ainsi, une congruence du degré n à une inconnue
f(x) -^ 0 (mod. p)y
c'est-à-dire une congruence dans laquelle lé premier membre f(x) est un polynôme entier en x de degré égal à n, ne peut avoir plus de n racines distinctes. Si elle admet n racines distinctes et que Ton connaisse ces n racines, on pourra mettre le premier membre sous une foime spéciale, cognme on Ta vu au numéro précédent.
541. II est clair qu*on obtient une congruence équivalente à la proposée en remplaçant son premier membre par un polynôme qui lui soit identiquement congru (mod. p). Supposons en particulier que ce premier membre soit identiquement congru (mod. p) au produit de deux polynômes ^(x), 0(a;) entiers en ,r, on aura, quel que soit le nombre entier 'x\
f{x') = ^[x') 6(ar') (mod. p) ;
d'ailleurs, pour que le nombre entier f[x') soit nul (mod. p), il faut et il suffit que Tun des nombres entiers ^{x'), ^[x') soit nul (mod. p); on en conclut que les racines de la congruence
(!) A-ï?) ^ 0 (mod.p)
sont les mêmes que les racines, prises dans leur ensemble, des congruences
^{x) = 0 (mod. p),
^ ' 6(.r) ^- p (mod. p).
Si, en particulier, f[x) est de degré égal à n et si la congruence (1) a n racines distinctes, la somme des degrés des polynômes {«(a:), 6(.r) sera égale a n ; donc chacune des congruences (2) aura exactement autant de racines distinctes qu'il y a d'unités dans sou degré.
Par exemple, la congruence
x^-^ — i^O (mod.p)
a p — 1 racines distinctes, diaprés le théorème de Fermât, à savoir les nombres 1, 2, ..., p — 1 ; on a d^ailleurs identiquement, en supposant P>2,
x^-*— 1= [x * — 4)(.r * +0; donc les congruences
X ^ — I sr- 0 (mod. p), p-i a; * + 1 =^ 0 (mod. p)
Tannkry. 32
498 LEÇONS D'AUITHMÉTIQUE.
ont chacune^— ^ — racines distinctes; c'est ce qu'on savait déjà; les ^~
racines de la première sont les restes quadratiques de j), les —^ — racines
de la seconde sont les non-restes.
Donnons maintenant une application du théorème du n" 539. La congruence de degré p — 1
ac^"*— i =0 (mod. p)
admet p — 1 racines distinctes, par exemple les nombres f ^ 2, ..., p — i; il en résulte que le polynôme x''"'* — i est divisible (mod. p) par le produit
{x — i){x — 2). ..(a? — p + 1), et comme le coefficient de la plus haute puissance de x est un, on peut écrire identiquement
aJ'-* — 1 = (a? — 0(« — 2)...(a? — p-f- 1) -{- p^(xh 4> (x) étant un polynôme entier en x, à coefficients entiers ; il en résulte que tous les coefficients du polynôme
ap^-"*— i — (a;— l)(a; — 2) ... (a?— p+ 1)
sont divisibles par p; en d'autres termes, si Ton veut, ce polynôme est identiquement congru à zéro (mod. p). Le terme indépendant de x, en particulier, est — 1 — 1.2. ..(p — i]; on a donc
i.2.3...(p — 1) + 1 ^0 (mod. p),
en sorte qu'on voit là un lien entre le théorème de Fermât et celui de Wilson. On voit en outre que dans le développement du produit
(a? — i){x — 2)...(a? — p + 1) tous les coefficients, sauf le premier et le dernier, sont divisibles par p.
§ 9. — Restes de paissances. Racines primitives. Tliéorie des indices. Congraences binômes.
542. En désignant par a et m deux nombres entiers premiers entre eux, dont le dernier est positif, considérons la suite indéfinie
et les restes de ses termes (mod. m). Ces restes ne peuvent être tous distincts, puisqu'ils sont au plus en nombre m — 1 ; aucun d'eux en effet ne peut être nul : supposons que a" et 0** + ^ donnent le même reste, on aura
a^'-^^^a'' (mod. m)
ou
a'»(a*— l)sO (mod. m);
a" étant premier avec m, â^ — 1 est divisible par m. Il y a donc, dans la
RESTES DE PUISSÂxVCES. 499
suite, des termes, autres que le premier, dont le reste (mod. m) est égal à un. C'est ce qu'on savait déjà par le théorème de Fermât généralisé, puisque l'on a, en désignant par ? (m) le nombre de nombres premiers et inféiieurs à m,
fl?(«)— 1 = 0 (mod. m).
Quoi qu'il en soit, désignons par k le plus petit nombre entier positif pour lequel on a
a* — 1 =s 0 (mod. m);
il est clair que deux termes de la suite (1) seront congrus ou non (mod. m), suivant que la différence de leurs exposants sera ou non divisible par h. Les restes se reproduiront donc périodiquement de k en k; k termes consécutifs fourniront k restes différents, qui seront dans leur ensemble les restes fournis par les k premiers termes. En particulier, les restes égaux
à 1 se reproduiront de k en k, et comme a^*"^ donne le reste 1, on voit que k est nécessairement un diviseur de 9(m).
Ces remarques trouveraient des applications faciles dans la théorie des fractions décimales périodiques, en supposant a = 10 ; en effet, quand on
réduit en fraction décimale une fraction de la forme — > où A et m désignent
des nombres entiers premiers entre eux et où Ton suppose (pour nous
borner à ce cas) que m est premier avec 10, on est amené à chercher les
restes (mod. m) des nombres.
et c'est la périodicité de ces restes qui règle la périodicité des chiffres de la fraction décimale périodique ; or on aperçoit que celte périodicité est la même pour la suite qu'on vient d'écrire et la suite
On est donc bien dans le cas considéré.
543. Sans m'arrèter à ces applications, qui sont faciles, je supposerai que le module m, que je désignerai désormais par p, soit un nombre premier. Alors f^{fn) ss ^ (p) est égal à p — 1 ; si d est le plus petit nombre entier positif tel que l'on ait
a** s 1 (mod. p),
d est un diviseur de p — 1 ; on dit alors que a appartient à l'exposant d. 11 est à peine utile de faire observer que les nombres congrus (mod. p) appartiennent au même exposant. La question suivante se pose immédia* tement : étant donné un nombre d di viseur de p — i,y a-t-ii des nombres
a qui appartienneut à Texposant d, c'est-à-dire des nombres dont la c/'^""' puissance soit congrue à \ (mod. p), les puissances d'ordre inférieur à d n'étant pas congrues à i (mod. p)? S'il y a un tel nombre a, il est facile de voir qu'il y en a exactement 7 {d) qui sont incongrus (mod. p).
Observons d'abord que tout nombre qui appartient à l'exposant d est une racine de la congruence
aj**— 1 =0 (mod.p),
qui ne peut avoir, d'après la théorie générale (n* 540), que d racines distinctes.
Si maintenant a appartient à l'exposant d, toute puissance a" de a sera une racine de la congruence ; on a en effet
(a"r'=a'»*'^ 1 (mod.p),
puisque nd est divisible par d. Parmi les puissances de a, il y en ad qui sont incongrues (mod. p), savoir :
ce seront donc là les d racines distinctes de la congruence, et les nombres qui appartiennent à l'exposant d doivent être cherchés parmi ces nombres. Soit a'M'un deux, la suite des puissances de a" sera
elles sont congrues aux nombres
a^, aTiy a"*, a'», ...,
en désignant par 0, i\, r^, r,, ... les restes (mod. d) des exposants 0, n, 2», 3n, ...; deux termes de cette dernière suite qui ont des exposants différents sont incongrus (mod. p), les seuls termes pour lesquels le reste (mod. p) soit un sont ceux dont l'exposant est nul ; or, la suite 0, t\, r.),
d rj, ... est périodique (n- 503); la période contient rr termes différents, en
désignant par fi le plus grand commun diviseur de n et de d; les termes nuls se reproduisent de - en -; il résulte clairement de là que a'* appartient à l'exposant -• Si donc on veut que a'^ appartienne à l'exposant d, il
faut et il suffit que n soit premier avec d; il y aura donc autant de nombres incongrus (mod. p) qui appartiennent à l'exposant d, diviseur de p — 1, qu'il y a de nombres premiers à c2 et non supérieurs à d, à condi* tion qu'il y ait un nombre qui appartienne à l'exposant d. Si donc on
