SUR LA DÉCOMPOSITION DES NOMBRES EN FACTEUR8 PREMIERS

405. Mous avons vu. au u"'.\~. comment on reconnaît si un nombre esl premier. On le divise successivement par les nombres plus petits que lui,

• I l'un voit m certaine- de ce- divisions réussissent.

Il est évidemment avantageux d'essayer les diviseurs par ordre de grandeur croissante. On peut d'ailleurs se borner aux diviseurs premiers. < >n est

1 ■ aidé par une table 'les nombres premiers, même n'allant pas jusqu'au

nombre proposé. En tout cas il est inutile d'essayer les diviseurs que l'on reconnaît immédiatement n'être pas premiers, par exemple les nombres pairs, les nombres divisibles par 3, par ">.

Enfin, les divisions étant faite- dan- l'ordre qu'on a dit plus haut, tandis «lue les diviseurs augmentent, les quotients vonl en diminuant ou tout au inoins n'augmentent pas. On arrive donc à une division dan- laquelle le quotient est inférieur ou égal au diviseur.

Si, à ce moment, aucune division n'a réussi, on peut arrêter les essais, le nombre proposé est'premier. lui effet, si une division suivante réussissait, le nombre proposé serait divisible par le quotient de cette division. c'est-à-dire par un nombre inférieur OU au plus égal au diviseur de la divi-ion à laquelle on s'est arrêté, ce qui est impossible.

Ceci revient à dire qu'on n'a besoin d'essayer que des diviseurs inférieurs à la racine carrée du nombre proposé.

M)6. Enfin nous allons montrer comment on peut restreindre le choix des diviseurs à essayer. La théorie des formes quadratiques va nous permettre, en effet, de fixer certaines formes linéaires dans lesquelles doivent c trouver les facteurs premiers d'un nombre.

Soit m le nombre dont il s'agit de savoir s'il est premier ou non. Je peux supposer /// impair. Supposons qu'on ait mis m sous la forme

i i m — ao72-t- ibxy -+- cy'-.

Si ./• et y n'étaienl pas premiers entre eux, /// ne serait pas premier. Supposons donc que x et y soient premiers entre eux. <>n sait alors n° 'So"2) que la congruence

//- . — D ( mod m i,

'c, en posant

D = ac — b1.

SUR LA DÉCOMPOSITION DBS NOMBRES EN FACTEURS PREMIERS. 3i5

Soit p un facteur premier quelconque de m. Le nombre p est nécessairement impair, puisque m l'est.

La congruence (i) eut raine la -ni vaille

// - I» ( niod p),

cel le dernière entraîne la condition

Soit D'2 le plus grand carré par lequel suit dh isible l> l'osons

D = D'*D". La condition i 3 | péul s'écrire plus simplement

Or D" n'étant plus divisible par aucun carré différent de i, et /) étant

impair, cette condition entraîne ( n" 194) que p appartienne à certaines progressions arithmétiques de raison D" ou 4D". Pour voir si m est premier, il suffira donc d'essayer les diviseurs de m par des diviseurs appartenant à ces progressions.

11)7. Remarque. — Supposons qu'on ait mis m sous différentes formes ni = ai!+ ibxy-{-cyi=a'x'^ --'.b' x'y'-i-c'y'-2= a" x'^-h^b" x"y"-h c"y'"2, x, y étant premiers entre eux, ainsi que x',y' et x",y". On en déduit plusieurs systèmes We progressions arithmétiques auxquelles appartiennent née sssairement tous les facteurs premiers impairs de m. Il nepeutyavoir que les nombres communs à ces différents systèmes qui soient facteurpremiers impairs de m.

Remarque. — Le procédé précédent permet ainsi non seulement de reconnaître si un nombre est premier, mais de le décomposer en facteur.-» premiers.

ION. Pour appliquer cette théorie, il faut, étant donné un nombre m., le

met I i e -,,11- la forme

ax- 2 bxy -+- cy"1.

On peut \ arriver par tâtonnements. Si, par exemple, on se borne à la forme particulière ,r2+ D/-, il suffira de prendre un nombre x quelconque, de l'élever au carré, de retrancher le résultat du nombre m, puis de mettre la différence sous la forme Dy~, ce qui est toujours possible, puisqu'on peut, en tout cas, prendre jr = i. En prenant x assez voisin de \ ///. on aura, pour l*> ', un nombre relativement petit.

( >n t rouvera d'ailleurs à la fin <lu Volume une Table donnant les expressions linéaires <\r- diviseurs des formes quadratiques #2 -+- Dy2, pour toutes les valeurs de D de -- toi à -+- ror.

326 NOTt I .

i09. Exemple. — Dan- la démonstration du n° 35, nous avons considéré l'expression A obtenue en faisant le produit des nombres premiers depuis i jusqu'au nombre premier />. el nous avons raisonné successivement dans l'bypotbêse où cette expression est première, <-t dans l'hypothèse où elle ni' l'est pas. En fait, est-elle première ou non?

Pour p — •>., 3. "'.7. 1 1 . mu ;■ 1 e»|>rctivrii).'iit

\ i. -, II, Ml. ' il I .

Toutes ces valeurs de V sont premières, elles sont contenues dans la Table

donnée à la fin de cet I >u\ rage.

Soit maintenant p 1 3. on trouve

A — 3oo3 1 .

Ce nombre sort des limites «le la Table. Sa racine, à une unité près, est i;3.

On sait d'ailleurs, d'après le raisonnement fail au n° .'!.%. que ses facteurs

premiers sont supérieurs à 1 >. On voit <l dès maintenant qu'on n'a

besoin de'ssayer que les divisions de A par les nombres premiers de 17