SUR LA DÉCOMPOSITION DES NOMBRES EN FACTEURS PREMIERS

405. Nous avons vu, au n" 37, comment on reconnaît si un nombre est premier. On le divise successivement par les nombres plus petits que lui, et Ton voit si certaines de ces 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. On est <lonc aidé par une table des 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 5.

Enfin, les divisions étant faites dans l'ordre qu'on a dit plus haut, tandis que les diviseurs augmentent, les quotients vont en diminuant ou tout au moins n'augmentent pas. On arrive donc à une division dans 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. En 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 division à 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é.

406. Enfin nous allons montrer comment on peut restreindre le choix iles diviseurs à essayer. La théorie des formes quadratiques va nous permettre, en effet, de fixer certaines formes linéaires dans lesquelles doivent se 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 m impair. Supposons qu'on ait mis m sous la forme

(i) m =^ ax^-h2bxy -hcyt^

Si or et ^ n'étaient pas premiers entre eux, m ne serait pas premier. Supposons donc que x et y soient premiers entre eux. On sait alors (n° 352) que la congruence

(2) n*s — D (mod m),

est possible, en posant

D = ac — 6».

SUR LA DÉCOMPOSITION DR8 NOMBRES EN FACTEURS PREMIERS. 3a5

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

La congruence (2) entraîne la suivante

/iJ — — D (mod/>), cette dernière entraîne la condition

Soit D'* le plus grand carré par lequel soit divisible D Posons

D = D'»D\ La condition ( '\ ) peut s'écrire plus simplement

Or D' n'étant plus divisible par aucun carré différent de 1, et p étant impair, cette condition entraîne (n^ 194) que p appartienne à certaines progressions arithmétiques de raison D' ou 4 D'« Pour voir si m est premier, il suffira donc d'essayer les diviseurs de m par des diviseurs appartenant à ces progressions.

407. Remarque, — Supposons qu'on ait mis m sous différentes formes m = ax'^-^'xbxy -\-cy^^ a' x'^-^'xb' x' y-\-d y^—a' af^-\-iV af y^-^-c'y^^ x^ y étant premiers entre eu%, ainsi que x\y' et J^,/'. On en déduit plusieurs systèmes de progressions arithmétiques auxquelles appartiennent nécessairement tous les facteurs premiers impairs de m. Il ne peut y avoir que les nombres communs à ces différents systèmes qui soient facteurs premiers 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 facteurs premiers.

408. Pour appliquer cette théorie, il faut, étant donné un nombre m, le mettre sous la forme

aa:--f- 7.bxy -h cy^.

On peut y arriver par tâtonnements. Si, par exemple, on se borne à la forme particulière ic*-+- 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 Dj'*, ce qui est toujours possible» puisqu'on peut, en tout cas, prendre ^ = i. En prenant x assez voisin de /m. on aura, pour D^', un nombre relativement petit.

On trouvera d'ailleurs à la fin du Volume une Table donnant les expressions linéaires des diviseurs des formes quadratiques a?' -f- Dj^', pour toutes les valeurs de D de — loi à H- 101.

409. Exemple. — Dans 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 />, et nous avons raisonné successivement dans l'hypothèse où cette expression est première, et dans l'hypothèse où elle ne l'est pas. En fait, est-elle première ou non?

Pour/? = 2, 3, 5, 7, II, on a respectivement

Toutes ces valeurs de A sont premières, elles sont contenues dans la Table donnée à la fin de cet Ouvrage.

Soit maintenant /> = i3, on trouve

A = 3oo3i.

Ce nombre sort des limites de la Table. Sa racine, à une unité près, est 173.

On sait d'ailleurs, d'après le raisonnement fait au n*35, que ses facteurs premiers sont supérieurs à i3. On voit donc dès maintenant qu'on n'a besoin de'ssayer que les divisions de A par les nombres premiers de 17 à 173, tous contenus dans la Table I.

Maintenant mettons 3o3oi sous la forme a?*H- ï>y^. Si l'on essaye ar= i;^, on trouve

3oo3i = i73 4-102,

valeur peu favorable, car la forme x^-\-ioiy^ sort des limites de la Table 111. Essayons x = 174, on trouve

3oo3i = 174 — 5.7'.

D'ailleurs 174 et 7 sont premiers entre eux. Donc 3oo3i est reprcsenié proprement par la forme

Donc, ses diviseurs premiers sont de l'une des formes

(4) 2o/i-hi, 9, t^i, 19.

En essayant a: = 172, on ne trouve rien de favorable. En essayant x = 175, on trouve

3oo3i =775* — 66.3».

175 et 3 sont premiers entre eux. Donc 3oo3i est représenté proprcmeni par la forme

Donc ses diviseurs premiers sont de l'une des formes

I 24A-H1, 5, i3, 17, 19, 25, 3i, 4i, 43, 49» 53, 59, 61 ( 85, 95, 97, io3, 109, 125, 139, i55, 161, 167, 169,