SECTION TROISIÈME

Des Késidus des Puissances,

45. Ihéorème. Dans toute progression géométrique . . . . i , a% a^ etc. , outre le premier terme i , il y en ^ encore un autre a' congru à l'unité suii^ant le module p premier ai^ec a , Vex* posant t étant < p.

Puisque le module /7 est premier avec a, et parconséquent avec une puissance quelconque de a, aucun terme de la progression ne sera ^o ( mod. /? ), mais chacun d'eux sera congru à quelqu'un des nombres i, 2, 3, 4'--yP — i» Comme le nombre de ces derniers est p — I y il est évident que si l'on considère plus de;?^i , termes de la progression , ils ne pourront pas avoir tous des résidus minima difFérens. Ainsi parmi les nombres \ ^ a" , a^ . . .a^~^ , on en trouvera au moins deux congrus. Soit donc a'^^a" etm^/z , on aura, en divisant par rt" (n'^a2), a"^""^'!-^ oà m — 7z<;?et>o.

Exemple. Dans la progression i, 2^, 4> ^ f ^tc. le premier terme qui est congru avecl'uuité suivant le module i3, se trouve être 2"=4o96, mais suivant Iç module 23 , on a dans la même progi'ession /2"=2o48=i ; (^e même 5^= i5625^ i ( mod. 7 ) 3 et 5^ ^ 5i25^ I ( mod. i l'j.^'Ainsi dans^quelques cas la puissance de ^congrue av&c l'unité y est plus pétiïb cjue'û'^^V^tdi^ns d'autres, il Fatatt remonter jusqu'à la puissaùce^^)D^-v-'i^^ëlle-raême.

46. Quand la progression est coi^tinuée au delà du terme jqui est congru à l'unité , on reti*6uvéra les mêmes résidus cju^on avait Aip€H-tir du conïmenrcement, Aifï&i > is^t a'^ ï , on atiraa'^^'^a, :«^"*''^3flt^!, «te, ^ jusqu'à ee qii'bn pa^t^iennôaii terme «^S dont le résidu minimum sera de nouveau ^ i j -tt^tt péri'ûd^ i^i résidus

recommencera. On aura ainsi une période de t résidus qui se répétera continuellement, et l'on ne pourra trouver un seul résidu qui ne fasse partie de cette période. On aura en général «""^i et a™'*'"^a" j ce qui peut se présenter ainsi suivant notre notation : si

r ^ p ( mod. / ) , on aura a^^a ( mod. p ),

47. Ce théorème fournit le mojen de trouver facilement les résidusdes puissances, quelle que soit la grandeur de l'exposant dont elles sont affectées , en même temps qu'on découvrira la puissance congrue à l'unité. Si, par exemple, on demande le reste de la division de 5'°°° par i3, comme 3^^i (mod. i3) , on a / = 3 , et comme d'ailleurs 1000^ i (mod. 3), on trouvera 3'"°° ^5 (modi 3),

48. Si a' est la plus petite puissance congrue à l'unité, (en exceptant «"= i , cas que nous ne considérons pas ) , les / restes qui composent la période seront tous différons, comme on le voit sans difficulté par la démonstration du n° /^S, Alors la proposition du n" 4^ psut être renversée. Savoir, si a'^^a'' {moà. p) , on aura m^n (mod./) : car si w et tz étaient incongrus suivant/,

leurs résidus minima fi et v seraient différens. Mais a ^ «"• ,

a ^"j donc a ^a , c'est-à-dire, que toutes les puissances au dessous de a' ne seraient pas incongrues, ce qui est contre l'hy» pothèse.

Si donc a^^i (moà.p), on aura ^^o (mod./), c'est-à-dire que k sera divisible par /.

Nous avons parlé jusqu'ici de modules quelconques, pourvu qu'ils fussent premiers avec a, A présent examinons à part les modules qui sont des nombres premiers absolus, et établissons sur ce fondement des recherches plus générales.

49. Théorème. Si p est un nombre premier qui ne divise pas a^ et que a} soit la plu^s petite puissance de a congrue à r unité » l'exposant t sera =p — i , ou une partie aliquote de p — i.

Voyez pour des exemples le n*" 4^»

Comme nous avons déjà prouvé que / est c=: ;t7 -** i ou <^pr-^ir^ il reste à faire voir que dans le dernier cas il est toujours une partie aliquote de/?-^— i. ')7ijon ;:>j hvjî \\\\i\\\\\^\M ubiè^i

ARITHMETIQUES. 55

I*. Rassemblons les résidus minima positifs de tous les termes, I, «, a% a'. . .a'"', et désignons-les par et, a', a.\ etc. desorte qu'on ait cL^ i , ot! ^ a y ai ^ a" f etc. il est visible qu'ils seront tous difFérens ; car si deux termes a"", a" donnaient les mêmes résidus , on aurait ^-"'~" = i (en supposant m'^n et m — n<:it)', ce qui est absurde , puisque a* est la plus petite puissance de a congrue à l'unité. Au reste tous les nombres a , a , a" , etc. sont compris

dans la série 1,2, 5, 4 p — i, série qu'ils n'épuisent pas

lorsque t<,p — I. Nous désignerons par (^) la somme de tous ces résidus, et {A) comprendra un nombre t de termes.

2'. Prenons un nombre quelconque /3 , parmi ceux de la série I, 2, 5. . ./? — I qui manquent dans {A), Multiplions /3 par a, a, a.', etc. et nommons /3, /S', /S", etc. les résidus minima qui en proviendront , et qui seront aussi en nombre t. Ces résidus seront différensentr'eux , et différeront des nombres a, a,', cl", etc. En effet, si la première assertion était fausse, onaurait^û'"^/3«",d'oii l'on tire, en divisant par /3, a'"^a": ce qui est contre ce que nous venons de démontrer : si la dernière l'était, on aurait /2û'"^û"j d'où, quand 7z>77z, /S^û"""*, c'est-à-dire que /3 serait congru à quelqu'un des nombres et, a', a.", etc. : ce qui est contre l'hjpotbèse ; mais si n<^m, on aura, enmultipliant par a'~'", /3^'^ «'"*'""'", ou, comme a'^i, /3^<2'~<^'"~"5, d'où résulte la même absurdité. Désignons par {B) la somme des nombres /3, /3', ff, etc. qui sont en nombre /; on aura déjà 2t nombres parmi ceux-ci i, 2, Z..,.p — i» Donc

si {A) et (jB) épuisent cette série, on aura tz=. ^ — .

3\ Mais s'il en manque quelques-uns , soit y un de ceux-là. Multiplions a, af, ce", etc. par y , et soient y, y' y y y etc. les résidus minima de ces produits , dont nous désignerons l'ensemble par (C); (C) comprendra ^nombre pris dans la série 1,2, ^,..p — i qui seront tous différens entr'eux et non-compris dans {A) et {B). Les deux premières assertions se démontrent comme cidessus (2°)-, quant à la troisième, si l'on avait ya'^^jea", on en tirerait ^^/Sa"""*, ou ^^/3a'~<^'"~"^, suivant que m <« ou >7z. Dans l'un ou l'autre cas y serait congru à quelqu'un des nombres qui composent {B) -, ce qui serait contre l'hypothèse. On aura ainsi 5^

nombres pris dans la série 1,2, 3...yo — i,et s'il n'en reste plus ,

f =:^^^, conforme m -Mit au théorème.

4°. Mais s'il en reste encore quelques-uns , on arrivera de mêm^ à une quatrième somme de nombres (D) , etc. j et comme I4 série i ,2 ,5 , etc. p- — i est finie, on voit que l'on parviendra nécessairement à l'épuiser, et p — i sera un multiple de ^ j donc t sera une partie aliquote de p — i.

5o. Puisque ^^ est un nombre entier , il suit qu*en élevant

chaque membre de la congruence «'^i (mod.;;) à la puissance ^^ ,

on aura a''~'^ i (mod.p)', c'est-à-dire, que af~^ — i sera touJQur^ divisible par p quand p est premier et qu'il ne diuise pas a.

Ce théorème remarquable , tant par son élégance que par sa grande utilité, s'appelle ordinairement théorème de Fermât, du nom de V inventeur. (F ermatii opera Mat h, Tolosœ iG'j^.FoLp, i63.) Fermât n'en a pas donné la démonstration, bien qu'il ait assuré qu'il l'avait trouvée. Euler en a le premier publié une dans la Dissertation intitulée : Démonstration de quelques théorèmes relatifs aux nombres premiers. ( Comra, Ac. Pétrop. T. viii) (*); elle est tirée du développement de (a-|-i)% qui fait voir par la forme des coefficiens, que (a-f-iy — a^ — i est toujours divisible par p, et que parconséquent («-|-i)^ — (^a-\'\') le sera si a^ — a l'est. ^Of comme i''— • i est divisible par/7, 2P — 2 le sera donc, et partant S'' — 3, et généralement a^-^a. Donc si p ne divise pas a, on aura aussi a^"' — i divisible par p. Ce que nous venons de dire suffit pour faire connaître l'esprit de la démonstration.

(*) Antérieurement (Comm. Petr. T. VI. p. 106) ce grand homme n'était pas parvenu encore au but. Dans la fameuse discussion entre Maupertuis et Konig , *ur le principe de la moindre action , discussion qui les fêta dans des digressions étrangères , Konig assura q.u'il avait entre les mains un manuscrit autographe de Leibnitz, qui contenait une démonstration de ce théorème conforme à celle d'Euler {Appel au Public, p. 106). Quoique nous ne ypulioijis pas refuser de croire à ce témoignage, il est sûr cependant que Leibnitz n'a jamais pujslié s» démonstration. {Voyez Hist, de l'Acad. de Berlin. 1750. p. 53o).

Lambert en a donné une semblable, { Acta eruditorwn, 1769, p. 109. ). Mais comme le développement de la puissance d'un binôme semble étranger à la théorie des nombres , Euler (Comm. nov. Petrop. T. viii, p. 70.) donna une autre démonstration qui est conforme à celle que nous venons d'exposer. Dans la suite il s'en présentera encore d'autres : ici nous nous contenterons d*en donner encore une déduite du même principe que celle d'Euler. La proposition suivante , dont le théorème en question n'est qu^iu cas particulier, nous sera utile pour d'autres recherches.

5i. 5/ p est un nombre premier , la puissance p du -polynôme' a-{- b -j- e-f- etc, e^^ ^ aP -j- bp^- cp + etc, suivant le module p.

On sait que (a-f-Z'-j-^+etc.)'' est composé de termes de la

forme Pa^b c^ etc. où l'on a a-f-/3 + ^+ etc. =;r7 , /^ étant le nombre de permutations de p choses, dont a, /S, y, etc. sont respectivement égales à a, b, c , etc. Mais nous avons fait voir (n° 40 que ce nombre était toujours divisible par p, à moins que toutes les lettres ne fussent égales entr'elles 5 c'est-à-dire, à moins que l'un des nombres a, /S, y, etc. ne fût égal kp, et les autres égaux à zéro j d'où il suit que tous les termes du développement , excepté flP, b^ , etc. sont divisibles par p , et que parconséquent (a -f- ^ 4- c -4- etc. y ^ a^ -{- b^ -\- cP -{- etc. ( mod. p).

Si toutes les quantités a, b , c , etc. sont supposées =r i, et que leur nombre soit X: , on aura kf^k, comme dans le n'* précédent.

52. Comme les nombres qui sont diviseurs de ;? — i sont les seuls qui puissent servir d'exposans aux plus petites puissances congrues avec l'unité , on est porté à chercher si tous les diviseurs âe p — I jouissent de cette propriété ; et , quand on classe tous les nombres non divisibles par ;; suivant l'exposant de leur plus petite puissance congrue à l'unité , combien il j en a pour chaque exposant. Nous observerons d'abord qu'il suffit de considérer les nombres positifs depuis i jusqu'à p — i : il est évident en effet que les nombres congrus doivent être élevés à la même puissance pour devenir congrus à l'unité , et que parconséquent un nombre quelconque doit être rapporté au même exposant que son résidu ininimum

positif; ainsi nous avons à rechercher comment les nombres

1,2,5 p — I, doivent être distribués sous ce point de vue,

relativement aux facteurs de p-^ i. Pour abréger, si d est un des facteurs deyO — i, entre lesquels on doit compter i et ;; — i, nous représenterons par %[/f/ la multitude des nombres positifs plus petits que p , dont la puissance d est la plus petite qui soit congrue à l'unité.

53. Pour nous faire entendre plus facilement, nous présenterons d'abord un exemple. Soit p=ig, les nombres i , 2, 5. . . i8 peuvent se distribuer de la manière suivante relativement aux diviseurs de 18 :

Ainsi dans cas 41 = 1, 42=1, 43 = 2, 46=2, 4.9=6,: 4.18 = 6. Avec une légère attention on voit qu'il j en a, relativement à chaque exposant, autant qu'il j a de nombres premiers avec cet exposant et non plus grands que lui , ou bien , en reprenant le signe du n° 40 , que ^d= çd. Mais on peut démontrer généralement cette observation de la manière suivante :

1°. S'il J a un nombre a appartenant à l'exposant d, c'est-à-dire dont la puissance d soit congrue à l'unité , et les puissances inférieures incongrues , toutes les puissances de ce nombre , savoir a, a% a^, a^ a"^^ ou leurs résidus minima, auront leur puissance d congrue avec l'unité ; et comme cela peut s'exprimer en disant que les résidus minima des nombres a, a% a^, ... a^ qui sont tous différens sont les racines de la congruence jc'' = i , qui ne peut avoir plus de d racines différentes , il est évident qull n^j a pas de nombres autres que les résidus minima de a, a"" a% . . . a^ dont les puissances d soient congrues à l'unité ; d'où il suit que les nombres appartenans à l'exposant d se trouvent tous entre les résidus minima des nombres a , a\ a% , . . a\ On déterminera comme il suit quels ils sont et quel est leur nombre. Si k est un nombre premier avec d, toutes les puissances de a', dont les exposans sont ^d, ne seront pas congrues à l'unité. Soit en cffet^(mod. û?} = w (vojez n* 3i); on aura a"^~a) donc si la

puissances de fl'^ était congrue à l'unité, et que Ton eûts <«?, on aurait aussi ^^'"' ^ I , et parconséquent a'^ijCe qui est contre l'hjpothèse. Il est évident , d'après cela , que le résidu minimum de a' appartiendra à d; mais si â: a un commun diviseur é' avec d , le résidu minimum de a" n'appartiendra pas à l'exposant d.

Car ^ est divisible par d, ou bien y = o ( mod. d) -, parconsé-

kd d

quent a '^ = I ; c'est-à-dire (a'/= i. Nous conclurons de là qu'il y a autant de nombres appartenans à l'exposant d , qu'il j a de nombres premiers avec d dans la série i , i, Z. ..d. Mais il faut se souvenir que cette conclusion suppose qu'il existe déjà un nombre a appartenant à l'exposant d) parconséquent il reste douteux s'il ne pourrait pas se faire qu'aucun nombre n'appartînt à un exposant donné, et la conclusion se réduit à 'vj/r/=o^ ou ;=(^d,

54. 2% Soient d, d' , d", etc. les diviseurs de ;? — i ; comme tous les nombres 1,2, Z.,.p — i doivent être distribués entre ces diviseurs, on aura '\>d'\-'^d' -{--^d" -{-eic.z^p — 1. Mais (n° 40) nous avons démontré que <pd-{'(pd' -{-(pd" -^ etc. :=^p — i, et du n' précédent il suit que •\^d=oo}xz=(pd-j et parconséquent que -^^d ne peut pas être > (p^ j ce qui s'étend à -nJ/^/ et (pd', etc. Si donc un ou plusieurs des nombres -^d, -^d' , etc. étaient plus petits que son correspondant parmi les nombres (pd , (pd', etc. , la somme des premiers ne pourrait être égale à la somme des derniers. D'où nous concluons enfin que dans tous lés cas, '\^d=.<pd , et que parconséquent -^d viQ dépend point de la grandeur de p — 1.

55. Il j a un cas particulier de la proposition précédente qui mérite de fixer notre attention j le voici : // existe toujours des nombres dont aucune puissance plus petite que p — 1 n'est congrue à V unité \ il y en a même autant entre i et /7— i , qu'il y a audessous de jp — 1 de nombres qui lui soient premiers. Comme il s'en faut bien que la démonstration de ce théorème soit aussi évidente qu'elle le paraît d'abord , nous eu donnerons une un peu différente de celle qui précède, d'autant plus que la diversité des méthodes aide beaucoup à jeter du jour sur les points les plus obscurs.

f8 RECHERCHES

Oh décomposera p — i en facteurs premiers, de manière qu'oit

ft Q. K

ait p — i==a b c^ etc. a, b, c, etc. étant des nombres premiers inégaux. Alors nous composerons la démonstration des

deux propositions suivantes :

i". On peut toujours trouver un nombre A, ou plusieurs appartenans à l'exposant af' , et de même des nombres B , C, etc. appartenans aux exposans b , c^, etc.

2". Le produit des nombres A, B , C, etc. ou le résidu minimum de ce produit appartiendra à l'exposant /? — 1 5 ce qui se démontre ainsi qu'il suit,

i". Soit^ un des nombres i, 2, 3. . .;?— 1 qui ne satisfasse pas

Lri à la congruence a; * ^ i ( mod. p ) ; car tous les nombres ne

peuvent pas satisfaire à cette congruence , dont le degré est

<Cp — I. Alors je dis que si l'on fait g»* ^h , h ou son résidu minimum appartiendra à l'exposant a*«

et et— I P— "

En effet il est évident que /z^ ^^p-'^i j mais /z" ^=:g " , et parconséquent sera incongru à l'unité , et à plus forte raison les

puissances h^ , h^ le seront aussi. Or l'exposant de la plus petite puissance de h congrue à l'unité, c'est-à-dire l'exposant

auquel h appartient, doit être un diviseur de a^ (n° 48) j et comme a n'est divisible que par lui-même , ou par les puissances inférieures de a , il s'ensuit nécessairement que a sera l'exposant auquel b appartient. On démontrera de la même manière, qu'on

peut trouver des nombres appartenans aux exposans b , c^, etc.

2°. Si nous supposons que le produit de tous les nombres A , B , Ci etc. n'appartienne pas à l'exposant p—'i , etc., mais à un exposant t plus petit , t devra être un des diviseurs de/? — i (n° 4^) , ou

^— T — sera un entier > i . Il suit de là que ce quotient sera un

âes nombres premiers a, b, c, etc. , ou du moins qu^ii sera .divisible par quelqu'un d'eux (n° 17) , par a, par exemple, car le r^ison-

nement est le même pour les antres, t divisera ainsi ^—^-j donc

le produit ABC etc. serait encore congru à rimitç,.^.^; l'élevant

à Ja puissance ^ ~^ ^ ( n° 4^). Mais il est évident ^ue loué les

nombres, B , C, D, etc. (excepté A) deviennent congrus àruuité,

$i on les élève à la puissance ^"" ^ , puisque les exposans auxquels

ils appartiennent b , c^, etc. divisent^ — — . Donc y^ " . B t*

Is'jJifl'iii

C " . etc. =-^ " —l'y donc a^ doit diviser ^^=^ (n^ 48), c'està-dire que ^^\ doit être entier, ce qui est absurde (u° i5). Donc

a enfin notre supposition ne peut subsister, c'est-à-dire que le produit-^^SC etc. appartient réellement à l'exposant p — 1.

La dernière démonstration semble un peu plus longue que la première , mais elle est plus directe.

56, Ce théorème nous fournit un exemple remarquable de la circonspection dont on a besoin dans la théorie des nombres,, pour ne pas regarder comme démontrées des choses qui ne le sont pas. Lambert, dans la Dissertation que nous avons citée plus haut , fait mention de cette proposition , mais ne dit pas un mot de la nécessité de la démontrer. Personne même n'a tenté de le faire , excepté Euler ( Comm. nop» Ac, Pétrop. T, xvjii ^ p. 85)^ dans son Mémoire intitulé : Demonstrationes circa residua ex divisione potestatum per numéros primons resultantia. On peut voir surtout l'art. Sy , dans lequel il a parlé avec étendue de la nécessité de démontrer cette proposition. Cependant la démon^ration de cet homme pénétrant présente deux défauts ) l'un tient à ce qu'il suppose tacitement , art. 5i et suivans, que la congruence a"^!, (en ramenant ses raisonnemens à notre notation) a réellement n racines différentes, tandis qu'il était seulement démontré que cette congruence ne peut en avoir davantage j l'autre , à ce qu'il ne déduit que par induction la formule du n° 54.

4o RECHERCHES

5/. Nous nommerons avec Euler, racines primitives les nombres qui appartiennent à l'exposant/? — i. Si donc a est une racine primitive , tous les résidus minima des puissances a, a*, a^, . . .W~^ seront difFérens \ d'où l'on déduit facilement qu'ils se trouvent tous parmi les nombres i,2,3,..,;p-— i qui sont en même nombre qu'eux , c'est-à-dire que tout nombre non divisible par p est congru à quelque puissance de a. Cette propriété remarquable est d'une bien grande utilité , et peut considérablement abréger les opérations arithmétiques relatives aux congruences , à peu près de la même manière que l'introduction des logarithmes dans l'arithmétique ordinaire en abrège les opérations. Nous prendrons arbitrairement pour Z>a^^ une racine primitive a, à laquelle nous rap^ porterons tous les nombres non divisibles par p ; et si on a «^ ^ ô ( mod.^p ) , nous appellerons e 17/2^/^^ de b* Par exemple, 2 est une racine primitive suivant le module 19 ; si on la prend pour base ,

aux nombres 1 , 2 , 3,4, 5, 6, 7,8,9,10,11,12,13,14,15,16,17,18

répondront f ^ , „ „ ' ^ ^

lesindicesl°' ^' ^^'^' ^^' ^'^^ 6,3,8,17,12,16, 5, 7,11, 4,10, g.

Au reste il est évident que pour la même base chaque nombre a plusieurs indices, mais qui seront tous congrus suivant le module p — I j aussi quand il sera question d'indices , ceux qui seront congrus suivant le module p — i, seront regardés comme équivalens, de même que les nombres sont regardés comme équivalons lorsqu'ils sont congrus suivant le module p,

58. Les théorèmes qui regardent les indices sont absolument analogues à ceux qui regardent les logarithmes,

Uindice d'un produit de tant de facteurs gu*on voudra , est congru à la somme des indices des differ ens facteurs y suivant le module p — i ,

L* indice de la puissance d*un nombre est congru , suivant le module p — \ y au produit de V exposant par V indice du nombre donné.

Nous omettons les démonstrations à cause de leur simplicité.

On voit par là que si nous voulions construire une table qui

donnât

ARITHMÉTIQUES. ^i

donnât les indices de tous les nombres pour dijBférens modules, nous pourrions nous dispenser de tenir compte de tous les nombres plus grands que le module et de tous les nombres composés. On trouvera à la fin de cet ouvrage un essai de cette table ( Tab. Ii). Dans la première colonne sont rangés les nombres premiers et les puissances de nombres premiers depuis 5 jusqu'à 97, qui doivent être regardés comme des modules: à côté de chacun d'eux, dans la colonne suivante, les nombres pris pour bases \ suivent alors les indices des nombres premiers successifs , qui sont écrits par tranches composées de cinq chacune \ en tête se trouvent les nombres premiers disposés dans le même ordre. Desorte qu'on peut trouver facilement l'indice qui répond à un nombre premier donné , suivant un module donné.

Soit par exemple ^0=67^ l'indice de 60, en prenant 12 pour base, sera

=2lnd.2 + Ind. 3-i-Ind. 5 (mod. 66) = 584-94-39=40.

59. L'indice de la valeur d'une expression quelconque r (mod. p) ,

(n° 3i ) est congru suivant le module /t? — i , à la différence des indices du numérateur a et du dénominateur h , pourvu que les nombres a et Z> ne soient pas divisibles par p.

Soit en effet c une valeur quelconque de cette expression, on aura hc^^a (mod./?)^ donc Ind. b-^-lnà, c^Ind. a (mod. p — i ) , et

Ind. c ^ Ind. a — Ind. b.

Si donc on a deux tables , dont l'une donne les indices qui répondent à chaque nombre pour un module quelconque , et dont l'autre donne les nombres qui répondent à des indices donnés , on pourra résoudre facilement toutes les congruences du premier degré , puisqu'on peut toujours les ramener à d'autres dont les modules soient premiers (n° 5o).

Soit par exemple la congruence 29:1: 4-7^0 (mod. 47 )> on aura

Delà

înd.a:=Ind.— .7— Ind.29=Ind.4o— Tnd.29=i5— 45=i8(mod.46)j

4a RECHERCHES

or 5 est le nombre qui a pour indice iS-, done :c^5 (mod. 47)» Nous n'avons point ajouté la seconde table , mais on verra dans la section VI comment on peut la remplacer par une autre.

60. De même que dans le n° 3i nous avons désigné par un signe particulier^les racines des congruences du premier degré, dans ce qui va suivre, nous représenterons par un autre signe les racines des con-

gruences à deux termes des degrés supérieurs -, et comme \/^ ne signifie autre chose que la racine de l'équation jc"=^', en ajou-

tant le module , \/^ ( mod. p ) représentera une racine quelconque de la congruence x''^A ( mod. p ). Ainsi nous dirons que

l'expression {/y4 (mod. ^) a autant de valeurs qu'elle en a d'incongrues suivant p-, car toutes celles qui sont congrues suivant ;t7 doivent être regardées comme équivalentes (n° 26), Aureste il est clair

que si ^ et ^ sont congrus suivant p, les expressions v/^ (mod. p) ,

y/B (mod./?) seront équivalentes.

Maintenant si l'on fait \/A^a: (mod. ;t7), on aura

n Tnd. :r ^Ind. ^4 ( mod. /?— i ). On déduit de cette congruence , d'après les règles de la section II , les valeurs de Ind. :r, et de là les valeurs correspondantes de x; mais on voit facilement que x a autant de valeurs qu'il j a de racines dans la congruence

n Ind. jr^Ind. A ( mod. p — i ) j donc \/A n'aura qu'une valeur, quand n sera premier avec;»— i , mais lorsque /z et p — i, auront un commun diviseur, et que J" sera le plus grand , Ind. x

aura cT valeurs incongrues suivant p — i , et parconséquent {/A aura autant de valeurs incongrues suivant p , pourvu que Ind. A soit

divisible par cT. Sans cette condition, \^A n'aurait aucune valeur réelle.

Si l'on cherche par exemple les valeurs de l'expression \/ 11 (mod. 19), il faut résoudre la congruence iSInd. ^r^Ind. 11^-6 (mod. 18), on trouvera trois valeurs de Ind, 0:^4^ lo, 16, (mod. 18), d'où il résulte" :r^6, 9, 4*

61. Quoique cette méthode soit très-expéditive , quand on a les tables nécessaires, nous ne devons cependant pas oublier qu'elle est indirecte j il sera donc utile de chercher ce que peuvent donner les méthodes directes. Nous allons exposer ici les observations que l'on peut déduire des notions précédentes j quant à ce qui exige des considérations plus profondes , nous le réserverons pour la section VIII.

Nous commencerons par le cas le plus simple j celui 011-^=1, c'està-dire, dans lequel on cherche les racines de la congruence x"^i (moâ.p). En prenant pour base une racine primitive quelconque, on doit avoir n Ind. jr^o (mod./?— «i ). Quand n est premier avec j)- — I , Cette congruence n'aura qu'une seule racine, savoir

Ind. 0:^0 (mod. p — ^i)-, donc, dans ce cas \/i (mod./?) n'aura

<qu'une valeur x^ i (mod. p)'j mais quand n et p — i ont J" pour plus grand diviseur commun, la solution complète de la congruence n Ind. 0:^0 (mod. /? — i)sera x^o f mod.^-^- ) (n° 3o), c'est-à-dire, que Ind. x devra être congru suivant le modulent?—- 1 à quelqu'un des nombres o, ^—j~» ^ — >••■- jr^ j ou qu il

aura J^ valeurs incongrues suivant le module/? — i; donc aussi, dans ce cas , x aura J' valeurs incongrues suivant p. On voit aussi

que l'expression \/i (mod. p) a aussi J" valeurs dont les indices sont

absolument les mêmes que les précédens ; donc l'expression [/i

(mod. p) est tout- à-fait équivalente à l'expression \/i (mod./?),

ou ce qui revient au même, la congruence x ^i (mod. /?) et la congruence x"^! (mod./?) ont les mêmes racines-, mais la première est d'un degré inférieur à moins qu'on n'ait S =71,

Ex, y/i (mod. 19) a trois valeurs, parceque 5 est le plus grand

commun diviseur de i5 et 18^ elles seront également celles de l'ex-

pression \/i (mod. ig). Ces valeurs sont i , 7, 11.

62. Cette réduction nous offre un grand avantage, puisqu'on n'a plus besoin de résoudre parmi les congruences de la forme .i"^ i(mod./>)

44 HECHEKCHES

que celles où ?i est diviseur du module diminué de l'unité. Mais nous ferons voir plus bas que les congruences de cette forme peuvent encore s'abaisser davantage, quoique ce qui précède ne suffise pas pour cela. H J a cependant un cas que nous pouvons traiter ici à fond , celui où n = 2. Il est évident en effet que les valeurs

de l'expression \/i (mod. p) seront -\-i et — i , puisqu'elle n'en peut avoir plus de deux, et que +1 et — i sont incongrus, à moins que le module ne soit =2, cas auquel il est clair que \/2 n'aurait qu'une seule valeur. Il suit de là que+i et — x sont aussi les valeurs

de l'expression \/i (mod. p)t quand m est premier avec '- , ce qui

arrivera toujours lorsque le module sera tel que ^^ soit un

nombre absolument premier-, par exemple, quand ;?=3, 5, 7, 11,23, etc. ,, à moins que p^- 1 =3/72, cas auquel tous les nombres 1,2, 3. . ./? — I sont racines. Remarquons, comme conséquence,

que l'indice de — 1 est toujours ^^ — ^ (mod./? — i), quelle qu»

soit la racine primitive que l'on prenne pour base j car 2 Ind*

( — 1)^0 (mod.y» — I )*, donc Ind. (—1) sera^o ou ^ 2^;

mais G est toujaurs l'indice de -j-i, et +1 et — 1 doivent avoir des indices différens, excepté dans le cas où/7=2 , qu'il n'est pas nécessaire de considérer,

63. Nous avons fait voir (n^ôi) que l'expression \/^(mod.;7)a«r valeurs différentes ou n'en a absolument aucune, si ^ est le plus grand commun diviseur des nombres neip — i . Or de même que nous avons

trouvé que \/A et \/'A étaient équivalentes quand on a^a ^ i , nous

prouverons plus généralement que l'expression ^A peut toujours

être ramenée à une autre \/B , à laquelle elle est équivalente. Soit

en effet :r"^^, et / une valeur quelconque de l'expression -

(mod./) — 1) qui aura toujours (n^ 3i ) des valeurs réelles. De la congruence x^^A on déduit a;'" ^-^'j mais à cause de tn^^^

(mod. p — i) f x'^^x^ \ donc x^^A\ Ainsi une valeur quelconque

de \/A sera aussi une valeur de \/A'', et toutes les fois que \/A aura des valeurs réelles, elle sera absolument équivalente à Fexpres-

sien \^A', puisqu'elle ne peut avoir de valeurs différentes, ni en

moindre nombre. Il est vrai cependant que \/A' peut avoir des

valeurs réelles, sans que pour cela \/A en ait nécessairement, -^'^^

ai

Exemple. Si Ton cherche les valeurs de l'expression \/2 (mod. 3i), le plus grand commun diviseur des nombres 21 et 3o

est 3 , et 5 est une valeur de ^ ( mod. 3o ) ; donc si \/2 a

des valeurs réelles, elle équivaudra à l'expression \/2.^ ou \/8;

on trouve effectivement que les valeurs de la dernière qui sont

2, 10 et 19, satisfont aussi à la première,

64. Mais afin de ne pas entreprendre inutilement cette opération, il est nécessaire de chercher le caractère auquel on pourra recon-

naître si y^A admet ou non des valeurs réelles. Si on a une table

d'indices la chose est facile, car (n*' 60) \/A aura des valeurs réelles quand Ind. A sera divisible par S" , en prenant pour base une racine primitive quelconque, et dans le cas contraire elle n'en aura pas j mais on peut aussi le découvrir sans le secours de cette

table. Soit en effet it = Ind. ^, si k est divisible par J^, -^-7^-^

sera divisible par ;? — i et réciproquement 5 mais l'indice du

nombre A est ^ ^ ~" ^ ^ ; donc si \/A (mod./?) a des valeurs

réelles,^ sera congru à l'unité-, sinon, il sera incongru. Ainsi dans l'exemple de l'article précédent, on a 2'°= 1024^1

(mod. 3i), d'où l'on conclut que l'expression ^/2 (mod. 5i)a

des valeurs réelles. De même nous voyons par là que y/ — i (mod./?) a toujours deux valeurs réelles, quand/? est de la forme 4'7z-i-i , et n'en a aucune quand /? est de la forme 4'7z-f-5, car. . . (•—I )"'"=! et (— 1)*'"-^' = — I. Ce théorème élégant qui

^B " Recherches

s'énonce ordioairement ainsi: Si p est un nombre premier de la forme 4mH-i y on peut trouver un quarré a* qui rende a*-^-i divi' sihle par p*, mais si p est de la forme 4ni — i fOnne le pourra pas, a été démontré de cette manière par Euler ( Comment, noi^. A.c, Petrop. T. XVIII, p. 112, lyyS). Il en avait donné une autre démonstration bien antérieurement ^ Co77z^. tzc?/^. T,v , p. 5, 1760); dans une première dissertation (T. iv,p. 25), il n'était pas encore parvenu au but. Lagrange a depuis donné aussi une démonstration de ce théorème (Noui^. Mem. de VAc, de Berlin. ijjS ,p. 542), Nous en exposerons encore une différente dans la section suivante, qui sera consacrée à ce genre de considérations.

65. Après avoir examiné comment on peut réduire toutesles exprès-

sions \/A(moà.p) à d'autres dans lesquelles n soit diviseur de /^ — i, et après avoir trouvé le caractère auquel on reconnaît s'il y a des ra-

cines réelles ou non , considérons avec plus de soin les expressions \/A. ■(mod./;), dans lesquelles 72 est diviseur de/? — i. Nous ferons voiï d'abord quelle est la relation qu'ont entr'elles les différentes valeurs de cette expression, ensuite nous indiquerons quelques artifices au mojen desquels on peut le plus souvent trouver une des valeurs.

lO. Quand A^\, etquersera une des valeurs de l'expression \/i (mod. p) , ou que r"^i (mod./»), toutes les puissances de /• seront aussi des valeurs de cette expression ; et il y en aura autant de différentes qu'il j a d'unités dans l'exposant auquel r appartient (n° 4^)'^1 donc r est une valeur appartenant à l'exposant n, les puissances r, r" , r^ , r'^.../" (où l'unité peut remplacer la der-

nière) renfermeront toutes les valeurs de rexpression l^i (mod./?). Nous expliquerons plus en détail dans la section VIII comment on petit trouver ces valeurs qui appartiennent à l'exposant /z.

2^. Quand -f4 est incongru à l'unité, et que Ton connaît une

valeur 2 de l'expression \/A (mod. /?), on trouve les autres de la

manière suivante : soient i , r, r*,r^ , ... r"~' les valeurs de ^/i, on

aura ;z, zr, zr", zr^ . . .zr''~' pour les valeurs de {/ué", car il est évident que tous ces nombres satisferont à la congruence x"^A', puis-»

ARITHMÉTIQUES. 7{ij

qu'en effet, si zr^ est un des nombres de la suite; comme r^-^i et que z'^^A , onaurar"*^!, et partant zY"'=(2r')"^-^. Il est aisé de juger que toutes ces valeurs sont différentes (n° 25)j donc l'ex-

pression \/ A ne peut avoir d'autres valeurs, puisqu'elle ne peut^n

avoir plus de n. Par exemple, si une valeur de y/ A est Zj l'autre sera — z.,Ou doit conclure de ce qui précède, 'que l'on ne peut

trouver toutes les valeurs de \/A , à moins qvi'on ne puisse avoir

toutes celles de }/\,

66. La seconde recherche que nous nous étions proposée, consiste à déterminer le cas où l'on peut trouver directement une

valeur de l'expression }/ A ( mod. /?), dans laquelle n est diviseur de p — I. Cela arrive quand il y a une valeur congrue à une puissance de A f et comme ce cas est très-fréquent, il ne sera pas déplacé de s'y arrêter un instant. Soit z cette valeur, si elle existe, on aura z^A" et z^^A (mod. p)-j donc ^^/4^v ©* si l'on peut déterminer k de manière que cette condition soit remplie. A'' sera la valeur cherchée j mais la condition précédente revient à celle-ci kn^i (mod. f), /étant l'exposant auquel^ appartient. Or pour que cette congruence soit possible, il faut que n soit premier avec^, et

dans ce cas on aura ^=^ ( mod. if )j si au contraire / et tz ont un

diviseur commun, aucune valeur de z ne sera congrue à une puissance de A.

67. Mais comme il est nécessaire pour cette solution de connaître /, voyons comment il faut procéder quand on ne le connaît

pas. On voit d'abord facilement que t doit être diviseur de ^""^

lorsque \/A (mod,p) a des valeurs réelles, ce que nous supposons ici. Soit en effet j- l'une quelconque de ces valeurs, on aura (n° 5û)

y-'=i^ ety^AÇinod. p); en élevant à la puissance ^—^ les

deux membres de la congruence j"^y^, on aura j^-' ^A " ^ i ; d'ailleurs ^'^13 donc^=o (mod. /) (n^ 48). Or si ^^=^ e«t

premier avec n, la congruence kn^i pourra être résolue suîranÉ

le module - — , et toute valeur de k qui y satisfera suivant ce module, y satisfera aussi (n^ 5) suivant le module / diviseur de ^-^i donc on trouvera alors ce qu'on cherchait. Si ^^ n'est pas premier avec n , soit q le produit des facteurs premiers de ^^ qui divisent en même temps n) ^^^ sera premier avec n, et si la con^ dition que t soit premier avec n a lieu , t sera aussi premier avec a , et comme il divise - — i-, il divisera donc ^^-— ^; ainsi en résolvant

la congruence k?i ^ i Tmod. ^^^V ce qui peut se faire puisque n

est premier avec ^ — ^ , la valeur de k satisfera aussi à la congruence , suivant le module /. Tout l'artifice consiste à trouver ua nombre qui puisse remplacer t, que nous ne connaissons pas j mais

il faut se souvenir que dans le cas où^^ n'est pas premier avec Ug

nous avons supposé n premier avec t-, et si cette condition manque, toutes les conclusions sont fausses-, c'est pourquoi, si en suivant témérairement les règles, on trouve pour z une valeur dont la puissance n ne soit pas congrue k A',\q résultat prouvera que cette conditioa n*a p^s lieu, et que partant la méthode n'est pas applicable.

68. Mais dans ce cas même , il est souvent avantageux de faire cette recherche: elle offre l'avantage de faire trouver de vraies valeurs au moyen des fausses. Supposons en effet que les nombres k Qt z aient été convenablement déterminés, mais qu'on n'ait pas z"^-^ (mod./!?). Alors si on pouvait seulement déterminer les

valeurs de y/^;» (mod. ;?), ces différentes valeurs étant multi-

pliées par z donneraient celles de \/A : en effet , si ^ est une valeur de ^^ on aura /^"2"^-^; mais l'expression v^— est

{)lus simple que \/ A^ parceque le plus souvent — appartient a un

exposant moindre que A \ car §i d est le plus grand commun divj-

seup

senrde /et de ç-, — (mod. yy)appar(iendra à l'exposant r/, ce qui se dé-

A montre ainsi: puisque ^^y^*, il vient 7^. -r4''"~'^i (mod./c'); mais

kn — I est divisible par ^-—^ (n^préc), ^^^ l'est par /,ou^^ P^"^ ^■

D'ailleurs -^ est premier avec ^i donc aussi ^—^ est divisible par -4,

ou ^ — ^ par ^, et partant ^/z — i par ^, ou (A'/z — i)r/par/. Donc

^c^n-Oi^j (niod./?)j d'où l'on déduit facilement que — élevé à la puissance r/ est congru à l'unité. Il serait facile de démontrer que — ne peut pas appartenir à un exposant plus petit que d\ mais comme cette démonstration ne peut nous être utile, nous ne nous y arrêterons pas. Nous sommes donc certains que -^ ( mod. p ) appartient toujours à un plus petit exposant que A, excepté dans le cas unique où l'on aurait dz=.t.

Mais à quoi sert cjue — appartienne à un plus petit exposant que Al II y a plus de nombres qui peuvent être A qu'il n'y en a qui peuvent être —, et quand on a occasion de résoudre plusieurs

expressions de la forme y^A, suivant le même module, on y gagne de pouvoir tirer d'une même source la solution de plusieurs. Ainsi,'

par exemple, on déterminera au moins une valeur de v/^(mod. 29);

si l'on connaît seulement les valeurs de y/ — i ( mod. 2g ) , qui sont ±12, en effet l'on voit sans peine, par les articles précédens, que l'on déterminera d'une manièie directe une valeur quand / est impair, et que d sera = 2 quand t est pairj or il n'y a que — I qui appartienne à l'exposant 2.

Exemples,

Soit v/3i (mod. 37)-, on a ^ — 1=36, 7z = 3, ^ — =12, et

partant 7=5) il faut donc qu'on ait 5X:^i (mod. 4)* ce qui

5o REGTTERCHItS

donne k^5. Donc 2^3 1^ (mod. 37)^6-, l'on trouve effective-

vement6^=3i (mod. Sy). Si les valeurs de \/i (mod. 5j) étaient

connues, on pourrait aussi determiner les autres valeurs de y/Si:

or les valeurs de \/i (mod. 5j) sont i , 10, 26) donc celles de \/3i seront 6, 25 , 8.

Soit maintenant \/5 (mod. 37) ; on aura' p — 1==36 , 72=2, —^=18, et partant 9' = 23 donc on doit avoir ak^i (mod. 9), d'où X:^ 5; donc z^ 35^21 (mod. ^j); mais 21* n'est pas congru

avec 3, mais avec 34; or on a ^^ ^^ mod. 37)=^ — i et \/ — i (mod. 57) ^±6; d'où l'on tire les vraies valeurs ±6.21 ^dbi5.

Yoilà à-peu-près tout ce que nous pouvions exposer ici sur la résolution de ces expressions» Il est clair que lé^ méthodes directes deviennent souvent assez longues-, mais cet inconvénient a lieu dans presque toutes les méthodes directes de la théorie des nombres : Aussi nous n'avons pas cru devoir négliger de faire voir ce qu'on peut en attendre. Il convient aussi d'ohserver que les artifices particuliers qui se présentent à un homme exercé, n'entrent pas dans notre plan.

69. Revenons maintenant àtit racines que nous aVons appelées primitwes. Nous avons fait voir que , si l'on prenait pour base une racine primitive quelconque , tous lés nofmbres dont les indic€$^ sont premiers avec p — 1, étaient aussi des radîhès prinïitives, et qu'il n'j en aurait pas d'autres, d'où nous avons conclu le nombre de ces racines (n° 53) : et comme le choix de celle que l'on prend pour base est en général arbitraire, oh Voit qu'ici, cdrtifiie danslèsloga^ rithmtes, on peut avoir plusieurs systèmes Ç). Chérrfcbons les relation^; qui les lient eritr'eux. Soient aet b deux racines primitives, et miiix> autre nombre. Soitde pluslnd. Z^^/S, quand a eist pHs pcfiit ba^è*,^ Ind. 7n^/À> (mod. p — i }. Soit au conttaire Ind; a^d ylnû. m^v

(mod .;7 — I ) dans l'hypothèse où l'on prend Z> pour base; on aura a ^b.

(*) Mais ils diffèrent en cela, qxie dans les logàritlrnïes le il'ôthb're ^(fes-systêtUes eet infini , et qu'il est ici égal au nombre des racines J^riBÙtlteé^ c^ les-baaes eoagruès prodùièéût évideiruuent les mêmes systèmes.

ARITHMETIQUES. 5i

^oncaa ^Z> ^a, d'oùa/3^i (mod./? — i). On trouvera de même v^cLfj., /uL^^v (mod. yD — I ). Si donc on a une table d'indices construite pour la base iz , on pourra facilement la changer en une autre dont la base est b. En effet, si lad. Z>^/3 pour la base a, lad. a

sera ^ r (mod. ;?— . i ) pour la base b, et multipliant par ce nombre

-tousles indices de la table, on aura tous les indices pour la base b,

70. Mais quoiqu*un nombre donné puisse avoir plusieurs indices, en prenant pour base différentes racines primitives, tous ces indices auront cette propriété commune, que leur plus grand commun diviseur avec p — I sera le même. En effet , ^ étant un nombre donné , si Ind. A^m pour la base a, et Ind. ^^n pour la base Z», et si leurs plus grands communs diviseurs /-t et v avec p — i sont supposés inégaux; soit jtA>-i', ft ne divisera pas n\ mais si Ind. ^^.a pour la base b, on aura (art. précéd.) n^cLin (mod./? — i), et partant ^c divisera aussi ?i.

On peut encore s'assurer que ce diviseur commun des indices d'un nombre donné et de /; — i , est indépendant de la base en

observant qu'il est égal à^~" ^ , t étant l'exposant auquel appar-

« tient le nombre dont il s'agit. En effet, si l'indice est â: pour une base quelconque, ,^ sera Je plus petit nombre (zéro excepté), qui multiplié par^, donne un produit divisible par/7 — :i,ouiaplus petit©

valeur de l'expression -r- (mod. p — i)-, mais on déduit sans peine

du n° 29 que celte valeur est égale au plus grand commun diviseur des nombres k et p — i. C^)

. (*) ï*a dernière (phy^se de L'auteur ne me semble point prouver ce qu'il a avancé ; , iL, s'y. e^t sans dqute, glissé, quelques. f^u,tçs d'impression qui lui ont échappé. Au reste je crois que l'on peut y suppléer de la maaière suivante :

Puisque t est le plus petit nombre qui repde kt divisible par p — 1 , ce sera aussi

celui qui rendra —r divisible par " , - , d étant le plps grand commun diviseur entre k et p — 1. Or -j et" , - étant premiers entre eux, la plus petite valeur -^e t convenable est' ^^^ ;'doii<i; ^^- = t et Jz=^— ^. (.Vofe du traductùur^)

Sa R E C H E R C H E S

71. Ou démontre facilement que l'on peut toujours trouver ime base telle, qu'un nombre appartenant à l'exposant / ait un indice donné à volonté. I^e plus graud commun diviseur de cet indice

et de p — I étant ■^— — , désignons par r/ce diviseur, et soit l'indice

proposé "^dm^ soit dn l'indice du nombre donné quand on prend pour base la racine primitive (juelconque a\ on aura m et n premiers avec — 1 — ou t. Or si ë est une valeur de l'expression -j^

(mod./; — 1) ,eten même temps premier avec/? — i, a sera la racine primitive cherchée, car on aura a ^=^2""^ au nombre propose ( mod 7^) . Il nous reste à prouver que l'expression ^— (mod. p — i ) peut admettre des valeurs premières avec p — ij elle équivaut à — (mod. ^^)ou — (mod./),(n° 5i, 2°) et toutes les valeurs en seront

premières avec/; carsiune valeurs avait un diviseurcommiin avec t, ce diviseurdevrairt aussi diviser /72^, et partantdiviser/? qniestcongru h me , suivant le module /, ce ijuL est contre l'hypothèse suivant lacjuelle n est premier avec /. Ainsi, quand tous les diviseurs premiers de p — I divisent aussi /, toutes les valeurs de l'expression

- Cmod. /) sont premières avec p — i , et leur nombre est d; mais

quand p — I renferme encore d'autres facteurs premiersy,^, h, etc.

qui ne divisent pas /, soit e une valeur de — ( mod. t ) , comme

t,f, g, h, etc. sont premiers entre eux, on peut trouver un nombre £ congru à ^ suivant le module/, et congru, suivant^,^, h, etc., à des nombres quelconques premiers avec ceux-ci (n° 32). Ce nombre ne sera divisible par nucnn facteur de p — i, et partant sera premier avec lui, comme il est nécessaire. On pourrait démontrer sans peine par la théorie des combinaisons, que le nombre de ces

valeurs est ^ ~ ^ . ^-^ . ^ ~ ' . ~ ' . etc. ; mais nous omettons cette

démonstration qui ne peut nous être d aucune utilité.

72. Quoiqu'en général an puisse prendre arbitrairement pour base une racine primitive quelconque , certains avantages parti-

A HI T H M ET I QV 'E S. ;53

cullers peiiVPnt faire préférer une bai^ ^ toute antre. Dans latabie I nous avons toujours pris lo pour base quancl il était racine primitive, et dans les autres cas nous avons choisi la base de manière que l'indice du nombre lO fût le plus petit possible, c'est-à-dirô

~=:^~ , t étant l'exposant auquel lo appartient. On en recori-

naîtra l'avantage dans la sect. V-I<> pii la même table sera- employée à d'autres usages. Mais commeâl. peut -encore rester ici quelque chose d'arbitraire, ainsi qu'on le voit par l'article, précédçj[;i^ nous avons toujours choisi , parmi toutes les racines primitives qui satisfont à la question, la plus petite pour base: ainsi pour

^=r:y3,;on a /=8 et r/=g, 6 a ^-^ = 6 valeurs qui sont 5', 14,

20, 28^ 3g, 40, et nous .avons pris 5, pour base.

73 . La plupart dés niétliôcfëâ qui servent a'trouver les racines primitives reposent en grande partie sur le tâtonnement. 6i l'on réunit ce que nous avons dit (n^ 55 j avec ce que nous dirons plus bas sur la résolution de la congruence .r"^i> on aura à-peu-près fout ce qui peut se fa ire, par les méthodes générales. Fluler avoue ( Opuscula analyt, T. i , p. i52.) qu'il lui semble extrèmenienf difficile d'assigner ces nombres, et que leur nature doit être rangée dans les points les plus épineux de la théorie des nombres; mais on les trouve assez facilement par la méthode suivante. Les hommes exercés préviendront facilement la longueur du calcul par beaucoup d'artifices j mais l'usage les indique mieux que les préceptes.

fîH loJiQh'prèn^ra à volonté un nom'br^'jTremieraV&le mocî^iîe/^^^ et souvent le calcul devient plus simple lorsqu'on prend ^ le plus

'petit possible, 2 par exemple; on déterminera sa période ('no46}, c'est-à-dire les résidus minima de ses puissances , jusqu 'à ce que l'on parvienne à une puissance tv', qui aif i pour résidu minimum {^^'^^, Si l'on B.t-=p — I, a sera une racine primitive.

(*) Nous désignerons toujours le module par p.

( ) Il est aise de voir qu'il n'est pas nécessaire de connaître ces puissances, car on peut obtenir le résidu minimum d'une puissance au moyeu de la puissance précédente.

2®. Mais si t<Cp — 1 9 on prendra un autre nombre h , qui ne soit pas contenu dans la période de a, et l'on cherchera de la même manière sa période. En nommant z/ l'exposant auquel Z» appartient, on voit facilement que wn'est ni égal àr/^ ni une de ses parties alir quotes, car dans les deux cas on aurait ^^i, ce qui est impossible, la période de a renfermant tous les nombres dont la puissance./ est congrue à l'unité (n*^ 55). Or si u=:p — i , b sera une racine primitive-, si u n'est pas =zp — i , mais un multiple de t, nous aurons encore l'avantage de connaître un nombre qui appartienne à un exposant plus grand , et partant nous approcherons de notre but, puisque nous cherchons le nombre qui appartient à l'exposant maximum-, mais si u n'est ni =p-— i, ni multiple de ^, nous pouvons trouver un nombre appartenant à un exposant plus grand que t et w, cet exposant sera le plus petit nombre divisible à la fois par i et u. En effet, so'xiy ce dernier nombre*, on décomposera j en deux facteurs 7W et n premiers entre eux, dont l'un divise / et l'autre u (*}.

Soit oT'^^A, b"^B (mod. p'), wi45 appartiendra à l'exposant^; car on voit facilement que ud appartient à l'exposant m, B à l'exposant n, et parconséquent AB appartiendra à l'exposant jnn t puisque m et /2 sont premiers entre eux, comme on peut Je déwiDûtrer en suivant exactement le procédé r du. n" 55.

^^.Siy=p — I, ABseiSL une racine primitive, sinon on prendra de même un troisième nombre qui ne se trouve pas dans la période 'de AB-y ce nombre sera uneracine primitive, ou bien il appartiendra à un exposant >/, ou bien enfin par son moyen on déterminera un nombre appartenant à un exposant ^j* : donc, comme les nonibrçs qui résultent de la répétitioa de cette opération ,. apparti^nent à dçs

:[ir.i 1 !i :; i.

(■•■) On voit facilement parlé ^^ i8 comment on peut ràire cette décomposition: On décomposera^ en facteurs qui soient des nombres premiers ou des puissances de nombres premiers diîFérens; cbacun d'eux divisera t ou u, ou tous les deux. On écrira sous t ou sous u ceux qui .divisent iouiu. ,Quant,à ceux qui diviseront apt (, peu importe sous lequel on les écrive. Si l'on fait nj.==\e. produit de ceyx qui sont écfits sôus f , n= le produit de ceux qui ppnt écrits sous ,u,, il est évide^it que fn divisera" f , que n dvviserà ù et quê mn'z==y.

ARÎTHMÉTIQUMS. ^

exposans qui vont toujoiirs en augmentant, et sont "ôêàirtïïiôms'clîvi^' seurs de p — i , il est évident qu'on en trouvera enfin un qui appartiendra an maximum p*^\ y ce sera la racine primitive.

74. Eclaircissons ceci par un exemple. Soit pp;=.j'^y pour lequel on demande une racine primitive. Essayons d'abord le nombre 2.^ dont la période e§t •'