RE CHER CHE S

se reconnaîtront îmmédiate-nent à Tinspection î en efFet, ce sont ceux de la première coloniie auxquels répond dans chaque colonne le petit trait indicateur , findis que l'on doit rejeter tous ceux auxquels répond un espace vide dans un quelconque des bâtons. Un exemple éclaircira suffisamment cette explication.

Si Pon sait, d'une maiière quelconque, que les nombres —6, +i5, — 14, ^ly, 4.37, —55

sont résidus de ggySSi, 3n doit rassembler la première colonne, qui, dans ce cas, doit êirc continuée jusqu'à 997, c'est-à-dire^ Jusqu'au nombre immédiatement moindre que {/ggj^Si , et les bâtons en tête desquels sort inscrits les nombres —.6, -|-i5, etc. Voici une partie du tablau que Von forme de cette manière

etc.

ii3 i3i etc.

etc.

De la même manière ^u'on reconnaît ici à l'inspection, que des nombres premiers coienus dans ce tableau, 127 est le seul qui

reste dans a>, après l'eilusion faite avec les nombres 6, i5, etc.

on reconnaîtra, en sihevant le travail jusqu'à 997, qu'il' n'en reste effectivement m d'autre. En essayant la division par 127,

elle réussit , et l'on a

Au reste, il suit de ce que nous venons d'exposer, qu'il faut employer surtout des résidus qui ne soient pas tiès-grands, ou du moins qui puissent se décomposer en facteurs premiers de grandeur raojenne, puisque l'usage immédiat de la table auxiliaire ne s'étend pas au-delà des nombres placés en tête, et que l'usage médiat ne s'étend qu'aux nombres qui peuvent se décomposer en facteurs premiers contenus dans la table.

332, Nous donnerons trois méthodes différentes pour trouver des résidus du nombre M'y mais avant de les exposer, nous présenterons deux observations à l'aide desquelles on pourra déduire des résidus plus simples, lorsque ceux que l'on aura obtenus ne paraîtront pas convenables.

1°. Si le nombre aA*, divisible par le quarré A*, que nous supposons premier avec M , est résidu de M, a sera aussi résidu } ainsi les résidus divisibles par de grands quarrés sont aussi utiles que les petits, et nous supposerons que les résidus trouvés par les méthodes suivantes aient été délivrés de leurs facteurs quarrés.

2°. Si deux ou plusieurs nombres sont résidus, leur produit le sera aussi. En combinant cette observation avec la précédente, on peut très-souvent déduire de plusieurs résidus qui ne sont pas tous assez simples, un autre qui le soit beaucoup, pourvu qu'ils aient un grand nombre de facteurs communs. C'est pourquoi il est utile d'avoir des résidus composés de plusieurs facteurs qui ne soient pas trop grands, et il convient de les décomposer sur-lechamp en leurs facteurs. La force de ces observations se reconnaîtra mieux par des exemples et par un usage fréquent, que par des préceptes.

(*) L'auteur a construit pour son propre usage une grande partie de l'appareil de cette table , et il l'aurait publié volontiers, si le petit nombre de ceux auxquels elle serait utile, suffisait aux frais d'une telle entreprise; cependant si quelque amateur , après s'être bien pénétré des principes , desirait se construire une pareille table, l'auteur se ferait un grand plaisir de lui communiquer, par lettres, les différens procédés et les artifices que l'on peut employer.

I. La métbode la plus simple et la plus commode pour ceux à qui l'habitude a donné quelque dextérité, consiste à décomposer le nombre M, ou plus généralement, un multiple quelconque de ce nombre en deux parties quelconques, ensorte qu'on ait kM^=-a-\-b , a et b étant tous deux positifs, ou l'un positif et l'autre négatif-, le produit pris avec un signe contraire sera résidu de M, en eflet, on aura — ab^a^^b^ (mod. M), eé partant -^abRM. On doit prendre les nombres a et ^ de manière que le produit soit divisible par un grand quarré , et que la division donne un quotient assez petit, ou du moins decomposable en facteurs qui ne soient pas trop grands, ce qu'on peut toujours faire sans peine. On doit surtout recommander de prendre pour a un quarré, ou le double, ou le triple d'un quarré, dont la dijfférence avec M soit petite ou du moins decomposable en facteurs qui puissent être employés commodément.

Ainsi, par exemple, on trouve

997351 = (999)^ — 2.5.67 =(:994)' + 5.ii.i3*

= 2.(706)^+5.17.3* =5.(575)^ + 11.31.4 = 5. (577)^-7. 1 3. 4* =5.(578)^-7.19.37 = 11.(299)^+2. 5.5.29.4^= 1 1 . (3oi)"+ 5. 1 1% Qic,

On tire de là les résidus :

2.5.67,-5.11, — 2.5.17, — 5.ii.5i, 3.7.13, 5.7.19.37,— 2. 3.5.1 1.29J*,

la dernière décomposition donne le résidu — 5. 11 , que nous avons déjà. Au lieu des résidus — 3.ii.3i et — 2. 5. 5. 11 .29, on peut tirer de leur combinaison avec — 5. 11, les résidus 3,5.5i, 2.3.29.

II. La seconde et la troisième méthode se déduisent de ce que, si deux formes binaires (A , B, C), (A', B', C) de même déterminant M ou — M, ou plus généralement -àzkM , appartiennent au même genre, les nombres AA' , AC , A' C sont résidus de kMf ainsi qu'il est aisé de le conclure de ce que le nombre caractéristique de l'une des formes est également celui de l'autre, et que parconséquent, si l'on représente ce nombre par m y les nombres rtiA , mC , m A' y inC sont tous résidus de kM, Si donc (a, b, a') est une forme réduite de déterminant positif TLT, ou plus généralement, de déterminant kM , et que (a, b' , a") ,

ARITHMÉTIO^TlS. 4^5

(a% l\ a^)) etc. soient des formes de sa période, qui sont parconséqnent équivalentes à (û, bj a) et du même genre qu'elle, les nombres aa', aa ^ aa", etc. sont tous résidus de M. On calcule avec facilité un grand nombre de formes d'une pareille période, à l'aide de l'algorithme du n° 187. On obtient ordinairement les résidus les plus simples en faisant a = i j on rejettera ceux qui seraient composés de trop grands facteurs.

Nous joignons le commencement des périodes des formes (i, 998, -1327) et (i, i4i2, --918), dont les déterminans sont 99735i et 1994662 respectivement , c'est-à-dire, M et aiJf :

( —626, 891, 325) (—1062, esQ, 1473)

( 325, 734 — i4ii) ( 1475^ ^^1> —901)

( 382, 85i, — 7i5) etc.

Ainsi tous les nombres: —1327, 670, etc. sont des résidus de 997531 ; et en négligeant ceux qui renferment de trop grands facteurs, il reste les suivans :

Nous avions déjà trouvé le résidu 2.5.67, ainsi que —5. 11, qui résulte de la combinaison du troisième et du cinquième.

m. Si C est une classe quelconque de» déterminant négatif

M ou —/fiW différente de la classe principale, et que sa période

(u° 307) soit C% C\ etc ; 'es classes O, C\ etc. appartiendront au genre principal, et les classes C\ C\ etc. appartiendront au même genre que C. Si donc (a, b, c) est la forme la plus simple de C\ et {i\ à', c') une forme d'une classe de cette période, de C% par exemple, on aura a RM, ou aa'RM, suivant que n sera pair ou impair) c', dans le premier cas, acj ac et ce', dans

424 RECHEKCHES

le second, seront encore résidus. Le calcul de la période ; c'està-dire celui des formes les plus simples, s'exécute avec une facilité étonnante, quand « est très-petit, et surtout quand û = 3 , ce que l'on peut toujours obtenir si kM^2 (mod. 5) ( ). Voici le commencement de la période de la classe dans laquelle est contenue la forme (5, i, 532444)*

C7= ( 3, 1,332444), C»=( 9, — -2, 2io8i5),

C^=z (476, 209, 2187), C^=z (1027, 542, io85), C9= (932, —437, 1275), C-= ( 425, 12, 2347),

etc.

On tire de là les résidus suivans, en rejetant ceux qui sont inutiles ,

3.476, 1027, io85, 4^5, ou, en supprimant les facteurs quarrés, ''^ 3.7.17, 13.79, 5.7.31, 17.

Si l'on combine convenablement ces nombres avec les huit qu'a donnés la méthode II, ou obtient facilement les douze suivans:

—5. II, 79, — 83, —2.59, — 2.5,3i, 2.5.6j,

XiCS six premiers sont ceux dont nous nous sommes servis n" 33 1,' Nous aurions pu ajouter les résidus 19 et —29, si nous avions voulu nous servir de ceux qu'a fournis la méthode I j quant aux autres trouvés par cette méthode, ils sont dépendans des résidus que nous venons de déterminer.

333. La seconde méthode, pour décomposer en facteurs un nombre donné, se tire delà considération des valeurs de l'expression v/--"^(mod. ikj), et repose sur les observations suivantes:

I. Quand i)/est un nombre premier, ou une puissance d'un nombre premier, impair et non-diviseur de Z>, — D est résidu ou non-résidu de M, suivant que M est compris dans une forme

(*) Comme le cas où M est divisible par 3 , ne peut se présenter (n° Sag) , il est aisé de voir que l'on est même toujours maître de prendre k tel que kM soit ^2 (mod. 3). (^NoU du. traductçur).

^e diviseurs ou de non-diviseurs de x^^D, et dans le premier cas, l'expression y/^JJ (mod. M) n'aura que deux valeurs qui seront opposées.

II. Mais quand M est composé et -^.-pp'p" etc., p^ p', p" , etc. désignant des nombres premiers impairs et non-diviseurs de Z? , ou des puissances de tels nombres, — D ne sera résidu de Mque quand il le sera des nombres yc ,;»', /, etc., c'est-à-dire, quand tous ces nombres seront contenus dans des formes de diviseurs? de x^-\^D. Or en désignant toutes les valeurs de l'expression V—l>, suivant les modules p, p', p% etc., par r, r' , r\ etc. respectivement, on trouvera toutes les valeurs de la même expression, suivant le module M, en déterminant des nombres qui soient =d=r (mod. ;p), =d:;r' (mod.;?'), etc.; ainsi le nombre

de ces valeurs sera 2^*, si l'on exprime par p. le nombre des facteurs p y p', p\ etc. Si donc ces valeurs sont R, -—R, R', —R', R', etc., la congruence R^R a évidemment lieu par elle-même, suivant tous les modules de p, p', p% etc. , et la congruence i?= — R n'a lieu suivant aucun de ces nombres ; donc le plus grand commun diviseur de i? — R et de Bl est M, et celui de R-^-R et cle M est x ; mais deux valeurs telles que R et R', qui ne sont ni identiques, ni opposées, seront nécessairement congrues, suivant un ou plusieurs des nombres p, p',p", etc. mais ne le seront pas suivant tous, et l'on aura , suivant les autres, R^ — K-^ donc le produit des premiers est le plus grand commun diviseur des nombres M et R — R', tandis que le produit des derniers est le plus grand commun diviseur des nombres M et R-\-R\ Il est facile de conclure de là que si Ton cherche les plus grands communs diviseurs entre M et les diflérences d'une valeur donnée de l'expression yZ-^D (raod.il/) à toutes les autres, l'ensemble de ces communs diviseurs contiendra les nombres i , p , p', p", etc. et les produits de ces nombres pris deux à deux, trois à trois, etc. On parviendra donc de cette manière à déterminer les nombres P > P'> P'> ^^^* i ^^ l'aide des valeurs de cette expression.

Au reste, comme la méthode du n' 327 réduit la recherche des valeurs de l'expression / — D (mod. 3/) à celle des valeurs

qui sont de la forme ^ (mod. il/), dans lesquelles le dénorai-

Hhh

4^6 bechehchks

Dateur n est premier avec M, il n'est pas nécessaire , pour parvenir à notre but, de trouver ces valeurs-, car le plus grand commun diviseur du nombre M et de la différence B. — i?', R et K

corresppndan^ à — et ~, sera évidemment le plus grand commun

diviseur des nombres 71/ et niH {R — /?')> «^ des nombres Afet T^n'—nin, puisque ce dernier est congru à nn^R—K) suivant le module M,

334. L'application des observations précédentes au problème dont il s'agit, peut se faire de deux manières-, la première nonseulement décide si le nombre proposé M est premier ou composé, mais encore donne dans le dernier cas les facteurs euxmênies; la seconde a l'avantage de l'emporter le plus souvent par la brièveté des calculs, mais quelquefois elle ne donne pas les facteurs des nombres composés, à moins qu'on ne la répète plusieurs fois-, au reste elle distingue avec autant de facilité que la première, les nombres premiers des nombres composés.

I. On cherchera vm nombre négatif — D qui soit résidu quadratique de M, et l'on peut employer à cette recherche les méthodes exposées n° 332, I et II. Il est indifferent en soi de prendre tel ou tel résidu , et il n'est pas nécessaire, comme dans la solution précédente, que D soit un petit nombre j mais comme le calcul deviendra d'autant plus simple, qu'il j aura moins de classes de formes binaires, dans chaque genre proprement primitif de déterminant — D ^ on trouvera de l'avantage à choisir, s'il est possible, un des soixante-cinq nombres cités au n° 3o3. Ainsi pour M=99733i, parmi tous les résidus déterminés plus haut, le plus avant igeux est — 102. On cherchera toutes les valeurs de l'expression y/ — D (mod. M) , et s'il n'y en a que deux qui soient opposées, M sera certainement un nombre premier, ou une puissance d'un nombre premier; s'il j en a un plus grand nombre,

a'*, par exemple, M sera composé de }x facteurs qui sont des nombres premiers, ou des puissances de nombres premiers. Or il sera extrêmement facile de reconnaître si ces nombres sont premiers, ou des puissances de nombres premiers, et dans ce dernier cas, la méthode par laquelle on trouve les valeurs de \/ — D (mod. M) indique d'elle-même tous les nombres premiers dont une

ARITHMETIQUES. 437

certaine puissance divise le nombre M-, savoir, si M est divisible par le qiiarré d'un nombre premier -tt, le calcul conduira certainement à une ou plusieurs représentations du nombre il/, telles que M^=zam'''\'ibmn'\^cn% dans lesquelles le plus grand commun diviseur des nombres ttz et ^z est -tt, et cela arrive parcequ'alors — D est aussi résidu de — ; mais quand il n'y a aucune représentation dans laquelle m et n aient un diviseur commun, c'est un indice certain que M n'est divisible par aucun quarré, et que parcouséquent p, p', p\ etc. sont des nombres premiers.

Exemple, Par la méthode exposée p^is haut, on trouve quatre valeurs de l'expression /— 4û8 (mod-gcySSi) qui coïncident avec celle des expressions rfc^,^, d=,^^;.,,Ï3s , plus grands communs diviseurs du nombre ggySSi, avec