Nombres premiers plus petits qu'un nombre donné

On voit maintenant l'importance qu'il y aurait à connaître tous les nombres premiers. Nous allons montrer que cela est impossible, car la suite des nombres premiers est illimitée. On ne connaît môme pas de loi qui permette de former successivement tous les nombres premiers. Bien mieux, on ne connaît pas de procédé de calcul, qui, appliqué à des nombres entiers, ne donne que des nombres premiers.

Théorème. — // n'y a pas de nombre premier supérieur à tous les autres.

Supposons, en effet, qu'il existe un pareil nombre pre-

mior p ; la suite des nombres premiers ne comprendrait alors pas de nombre supérieur à p et serait limitée : ce serait la suite

Si nous considérons alors le nombre formé par le produit de tous ceux-ci, augmenté de 1,

ce nombre nous révèle Texistence d'un nombre premier supériGur à p ; car il n'est divisible par aucun des nombres premiers considérés, sauf 1, puisque chacun d'eux divise la première partie et ne divise pas la seconde. Le nombre A est donc premier ou admet des facteurs premiers, et ceuxci sont plus grands que p, d'après ce qu'on vient de voir ; dan? les deux cas, on voit qu'il existe au moins un nombre premier supérieur à p,

11 résulte de ce théorème que les seules questions que Ton puisse se poser, au point de vue où nous nous sommes placé, sont les suivantes : trouver tous les nombres premiers non supérieurs à un nombre donné, ou trouver une loi qui permette de former successivement tous les nombres premiers.

La seconde question n'a pas encore reçu de réponse. Quaat à la première, elle est facile à résoudre bien que, dans la pratique, elle puisse donner naissance à de longues opérations.

Trouver les nombres premiers inférieurs à un nombre donné, 100, par exemple.

Pour résoudre cette question, nous écrirons, sur un certain nombre de lignes horizontales, les cent premiers nombres*

NOMBRES PRBMIBRS 117

Nous barrerons dans ce tableau les nombres divisibles par 2, par 3, par 4, etc. ; les nombres qui resteront seront les nombres premiers cherchés.

Demandons-nous conmient on pourra barrer les nombres divisibles par 7, par exemple. A cet effet, il faudra partir de 7, ajouter 7 unités à ce nombre, ce qui se fera en comptant un, deux, trois, quatre, cinq, six, sept, sur les nombres qui viennent immédiatement après, et barrer le nombre ainsi obtenu; on partira de ce nouveau nombre, auquel on ajoutera 7 unités de la même manière et on barrera le nombre qu'on obtient ainsi; on continuera de cette manière jusqu'à ce que l'on sorte des limites du tableau.

Il est facile d'apporter des simplifications à ces opérations : il suffit de faire les quelques remarques qui suivent.

1** On commencera les opérations indiquées par les plus petits nombres du tableau 2, 3, 4, 5, ....; si Ton arrive à un nombre non barré, 5, par exemple, dont on ait à supprimer les multiples, ce nombre est premier, car il n'est multiple d'aucun nombre plus petit que lui, autre que un.

2° Si l'on rencontre un nombre barré, 4, par exemple, c'est qu'il est multiple d'un nombre inférieur, et il n'y a plus à supprimer ses multiples; ils le sont déjà, comme multiples du nombre plus petit.

3* Quand on aura barré les multiples de 7, le premier nombre non barré, venant après 7, sera 11. Il n'y aura pas lieu d'aller plus loin et de considérer ce nombre, car 11 X 11 ou 121 est un nombre supérieur à 100, et tout nombre inférieur à 100, divisible par 11, donne un quotient

plus petit que il, c'est-à-dire est multiple d'un nombre inférieur à 11, et, comme tel, a été barré. Cette remarque 9*iippHque a fortiori à tous les nombres non barrés supérieurs à 11.

Eo définitive, il n'y a donc à barrer, par le procédé indiqué, que les multiples de 2, de 3, de 6 et de 7. Les nombres qui restent alors sont les nombres premiers plus petits que 100. Voici le tableau, tel qu'il se présente alors :

2 3-4.8^ 7"^ "-9. "^iOL

"34, ^33.^^"85.^^ 37^-S8L"38l"^IÔ.

53 "W. "58l. ^tSe. "TW. "l». 59 "^W.

61 "61. ^«3. ^eWL "65. ^^66l 67 ^^8». >6âL ""KL

71 ^^ 73 "T4< "75. "76. "TL ^^78. 79 "«ft.

Les nombres qui restent 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, sont les nombres premiers plus petits que 100.

L'opération précédente^ est connue sous le nom de crible d'Étatosthène,

Cette méthode est extrêmement longue, quand on se fixe une limite élevée. Elle a cependant été employée pour cons- Iruire des tables de nombres premiers très étendues. La plus importante est celle de Burckhardt : elle s'étend à lous les nombres premiers inférieurs à 3.036.000.

75. Reconnaître si un nombre donné est ou n'est pas premier, — La méthode est très simple et il suffit de l'exposer sur un exemple.

Proposons-nous de chercher si le nombre 641 est premier

OU non. Il nous suffit de remarquer que le nombre 641 est inférieur au carré de 30, 641 < 900; nous pouvons alors en conclure que si ce nombre admettait un diviseur premier supérieur à 30, il aurait nécessairement un diviseur inférieur à 30, le quotient de 641 par le diviseur supposé. Il n'y a donc qu'à chercher s'il y a parmi les nombres premiers inférieurs à 30, % 3, 5, 7, 11, 13, 17, 19, 23, 29, des diviseurs de 641, ou bien s'il n'y en a aucun.

Il est visible d'abord que 2, 3, 5, 7, 11 ne sont pas diviseurs de 641; les nombres 13, 17, 19, Î3, 29 conduisent aux divisions suivantes :

aucune d'elles ne réussit; donc 641 est un nombre premier.

Remarque I. — Nous eussions pu ne pas faire la dernière division, car la division précédente nous montre que le quotient de 641 par 27 est 23 et le reste 20; donc tout nombre supérieur à 27 ne peut donner qu'un quotient, au plus égal à 23, et, par suite, le quotient de 641 par 29 sera inférieur à 29, et ne pourra être exact, sans quoi on eût trouvé déjà pour 641 un diviseur inférieur à 29.

Dans la pratique, on essaie successivement les divers nombres premiers, dans l'ordre où ils se présentent naturellement, et l'on s'arrête dès que l'une des divisions se fait exactement, ou bien dès que le quotient est inférieur au diviseur employé. Dans le premier cas, le nombre donné est un nombre composé; dans le second, c'est un nombre premier. On reconnaît de suite, à l'aide des caractères de divisibilité, si les nombres 2, 3, 5, 7, 11 sont ou ne sont pas diviseurs ; et lés essais véritables né commencent qu'à par^ tir de 13.

Exemples : Pour le nombre 1459, les essais s'arrêtent au nombre 41; il suffit même d'aller jusqu'à 37, car on a

HQ

et, d'après une remarque déjà faite, tout nombre supérieur à 39 donne un quotient inférieur ou égal à 37, c'est-à-dire plus polit que lui.

Pour 2921, les essais s'arrêtent à 23, qui est un diviseur de ^^2L Ce nombre est donc un nombre composé et Ton a

2921 = 23X127; 23 et 127 sont les facteurs premiers de 2921.

Remarque IL — Cette méthode s'applique sans difficulté aux petits nombres, par exemple aux nombres inférieurs à lllOOO; mais quand le nombre est grand, elle est excessivement lougue et peu commode. Elle exige d'ailleurs que l'on posst de une table de nombres premiers assez étendue.

Il y a d'autres procédés, mais nous ne pouvons en parler ici {Recherches arithmétiques de Gauss, section sixième).

Remarque III. — On pourrait penser que les nombres

N = i.2.3.5.7 p+1 du n** 74 sont des nombres

premiers; les premiers d'entre eux, en effet, sont premiers, car on a

et tous ces nombres sont premiers; mais le tiombre 1 . 2 . 3 . 5 . 7 . 11 . 13 -h 1 = 30031 est le produit des deux facteurs premiers 59 et 509.

Fermât avait annoncé que tous les nombres compris dans la forme 2**-i-l, où x désigne un nombre entier, iiiont lies nombres premiers; mais Euler a montré que le nombre qu'on obtient pour a? = 5, 2^^ h- 1, est un nombre composé ; ce nombre est 4294967297 et est divisible par 641, Depuis lors, comme nous l'avons déjà dit, on n'a

découvert aucune forme ne contenant que des nombres premiers.

* 76. Restes des puissances d'un nombre, relatifs à un module premier donné. — Théorème. — La suite des restes relatif t à un module premier p des diverses puissances d'un nombre a non divisible par p est une suite périodique^ qui ne contient aucune partie non périodique. — La suite des puissances de a est

Il n'y a dans cette suite aucun nombre divisible par p, car chacun d'eux est le produit d'un certain nombre de facteurs a, et de tous ces facteurs aucun n'est divisible par p (n« 72, 3«) ; d'autre part, le nombre des restes relatifs au module p est limité ; il y a donc forcément des puissances de a qui donnent le même reste ; soient a*» et a»» deux puissances de a qui donnent le mémereste^ et désignons par a*» celle qui vient après Tautre, de sorte que m > n. Alors la différence d™ — a» est divisible par p ; mais elle peut s'écrire a'»(a*«-« — 1), car a» = a^.a"»-»» (n« 42). Or le premier facteur, o", n'est pas divisible par p ; donc le second est divisible par p ; donc a»*-* admet pour reste, par rapport au module |7, le nombre 1.

11 y a donc dans la suite des puissances des nombres qui donnent pour reste 1. Soit a* le premier d'entre eux, la plus petite puissance de a qui donne pour reste 1 . On a a' = muU p-hi, et, en multipliant les deux premiers membres de cette égalité par

a^a^ja^, , a^ , nous avons successivement a*** = multp ■+- a ,

û«+« = mult p -H a», . . . , a*^* =r mult p-ha^; les t nombres a', a'+*,---'->«**^» qui suivent les t premiers, donnent donc les mêmes restes qu'eux ; de même les t nombres

0^, a«+*, a****, , a«*-*, redonnent les mêmes restes; et ainsi

de suite. La suite des restes est donc périodique, et la période commence au premier reste, 1 .

Remarque 1. — Les t restes fournis par 1, a, a',..., a^*, sont tous différents, si l'on suppose que a* est la plus petite des puissances donnant pour reste 1 ; car si deux d'entre elles donnaient le même reste, a* et a^, k> h, on verrait comme précédemment que a*"* donne pour reste i, ce qui n'est pas, puisque cette puissance de a vient avant a^ Cette suite de t restes différents a = J, a', a", ,0^*^), constitue donc la période qui se

reproduit indéfiniment et sans altération.

Remarque 11. — Considérons une puissance quelconque de a, a«, et supposons d'abord q divisible par <, q =z q't ; nous venons de voir que le reste de a«'' commence la (g'-l- !)• période ; il est donc égal à 1. On peut voir cela autrement, en écri-

PROPRIËTES DES NOMBRES

vanl 0^= multp+ 1 ; si on multiplie celte égalité par ellemême, membre à membre, on aura a*' = mult p + \ ; puis, muIUpliant cette égalité par la précédente, a** = multp + 1; et ainsi de suite, jusqu'à as'' = mnilp-hi. Supposons maintenant g non divisible par t, qznq't-^r, (r<,t); nous pouvons écrire oJ** = mult p H- 1, et, en multipliant les deux membres par a^, cfi'^*^ ou a« = mult p ■+• aT, Donc a« donne le même reste qne a*", et, pour calculer le reste relatif à une puissance, il ''aut remplacer Texposant par son reste relatif au module t,

Eseemple: 3' donne pour reste 1, par rapport au module 13 ; donc 3""^*^ peut être remplacé par 3 et donne pour reste 3 ; 3*<>°' peut être remplacé par 3^ et donne pour reste 9 ou — 4.

Remarque 111. — Le calcul des restes successifs se fait en multipliant, à chaque fois, le reste que Ton vient de trouver par a, et prenant le reste de ce produit ; on part de 1, et on continue jusqu'à ce que Ton retrouve 1. C'est ainsi qu*a été formé le tableau suivant, qui contient les restes des puissances de 10, par rapport aux modules premiers inférieurs à 50, autres que 2 et 5.

Périodes des restes des diverses puissances de 10, par rapport atuo modules premiers inférieurs à BO.

Modal ea

Périodes de restes 3, -2.

Dans ce tableau, on n'a mis que les restes minimas absolus. On a marqué d'un astérisque les modules pour lesquels la période comprend tous les restes possibles, autres que 0. \

Ce tableau contient les caractères de divisibilité par 3, 7, li, ^ 13, 17, 19, 23, 29, 31, 37, 44, 43, 47, dans le sens qui a été attaché à cette expression antérieurement.

Le théorème qui vient d'être établi est susceptible d'extension, comme nous le verrons plus tard. Pour plus de détails^ on pourra consuHerlesRechercJies arithmétiques àe Gauss (section troisième) ou V Algèbre supérieure de J. Serre t (tome 11).

* 77. Exposant auquel appartient an nombre, par rapport à un module premier p. — Si a* est la plus petite puissance de a qui donne pour reste 1, on dit que a appartient à l'exposant t, par rapport au module premier p.

Le tableau précédent nous montre que, dans tous les cas qui y sont contenus, l'exposant auquel 10 appartient est égal à p — 1 ou à un diviseur de p — 1. Nous allons montrer que cette propriété est générale.

Théoréhe. — L'exposant auquel appartient un nombre a, non divisible par un nombre premier p, par rapport à ce module, est égal à p — 1 ou est un diviseur de p — 1 .

Soient t l'exposant de a et (A) l'ensemble des restes donnés

par la suite 1, a, a«, , a*"* ; désignons ces restes par

a, a', a", , a(^*); a = 1. Nous avons vu que ces restes sont

tous différents ; par conséquent leur nombre ne peut dépasser p — 1. Le nombre t est donc égal à p — i ou inférieur à p-i.

Si *<p — 1, il y a, parmi les p — 1 premiers nombres entiers, des restes qui ne sont pas dans l'ensemble (A), c'est-à-dire qui ne sont pas des restes de puissances de a ; soit ? l'un d'eux, il est facile de montrer que les produits des restes a, a', a", ...., par ? conduisent à de nouveaux restes distincts et différents des précédents. Les restes des produits pa, pa', po*, sont différents;

car si deux d'entre eux donnaient le même reste, PaW et paW, leur différence pxW — paW serait divisible par p ; or cette différence est le produit de deux facteurs P et aW — a(*) qui sont tous deux inférieurs à p ; elle n'est donc pas divisible par p. D'autre part, ces nouveaux restes sont différents des précédents, car si paW donnait pour reste (z(*), la différence p(z(*) — «(*) serait divisible par p ; or on peut, dans cette différence, remplacer flrf*) et a(*) par a* et a*, qui ne diffèrent de ceux-ci que par des multiples de p, ou par a* et a*+* ; elle peut alors s'écrire

ou a*(a'+*-A — P).

124 PROPRIÉTÉS DBS NOMBRES

Pour qu*elle fût divisible par py il faudrait que ? fût le reste de a*+*~*, c'est-à-dire un reste de puissance de a, ce qui n'est pas.

r.es nouveaux restes p, P', P", forment donc un nouvel

ensemble (B) différent du précédent, et tous les nombres des ensembles (À) et (B) sont distincts ; nous avons donc déjà 2t restes relatifs à p. Si nous les avons ainsi tous obtenus, 2t =p— 1 ; sinon, soit y un de ceux qui manquent.

Multiplions tous les nombres de l'ensemble (Â) par y- ^ous

allons montrer que les restes provenant des produits ya, ya', fOL",

sont tous différents et diffèrent de ceux des ensembles (A) et (B). Nous verrions d'abord, comme précédemment, qu'ils sont distincts et qu'ils diffèrent des restes de l'ensemble (A) ; il nous reste à faire voir qu'ils diffèrent aussi de ceux de l'ensemble (B). Si l'un d'eux se trouvait dans l'ensemble (B), c'est que la différence pa(*) — Y«^*^ serait divisible par j9, ou bien la différence Pa«+* — Y^*; mais cette différence est Je produit de a* par p^f+A-fc — Y^ et le premier facteur n'est pas divisible par p; le second serait donc divisible par p, et f serait un reste du second ensemble, ce qui n'est pas.

Si tous les restes sont alors obtenus, on a 3t = p — 1 ; sinon, soit 8 l'un de ceux qui n'ont pas encore été obtenus ; nous considérerons de même les produits 8a, 8a', 8a'', Et ainsi de suite.

Nous arriverons ainsi à trouver tous les restes relatifs au module p, et nous voyons qu'on a forcément nt = p — 1 ; donc p — 1 est divisible par t.

Exemples: Les restes des puissances de. 2, par rapport au module 13, sont

1 , 2, 4, - 5, 3, 6, — 1 , — 2, — 4, 5, - 3, - 6 ; on a donc ici t = 12 = /) — 1.

Les restes des puissances de 3 sont 1^ 3, — 4; on a donc ici

Lorsque a appartient à Texposant p — 1 , on le nomme racine primitive de ^: 10 est racine primitive de 7, de 17, de 19, de 23, etc.; 2 est racine primitive de 13.

Nous verrons plus tard qu'il y a toujours des nombres appartenant aux diviseurs de /) — 1, et, par suite, qu'il y a toujours des racines primitives relatives à un module premier quelconque.

* 78. Théorème de Fermât. — 5» p désigne un nombre premier et a un nombre non divisible, par p, la différence a^""* — I est toujours divisible par p. — En effet, désignons par t l'exposant auquel a appartient ; nous avons vu que t est un diviseur de p — 1 ou j9 — 1 lui-même, et que a' = mult p -I- 1. Le

nombre ^-— — est donc un nombre entier, et si nous élevons

les deux membres de inégalité précédente à la puissance ^-7^ »

nous avons : o^* = rouit p -H 1 , ce qui démontre le théorème. Ce théorème, un des plus importants de Tari thmé tique, a été énoncé par Fermât, sans démonstration ; il a été démontré pour la première fois par Ëuler, mais par une méthode différente de celle que nous venons de donner.

EXERCICES

1« Sauf 2 et 3, tous les nombres premiers sont compris dans les formes 6* -♦- 1, 6* — i, h étant un nombre entier quelconque, ou dans les formes iZh-hij <2A+5, 12A4-7, 12A+H.

2^ Pour qu*un nombre soit divisible par le produit de deux nombres premiers, il faut et il suffit qu'il soit divisible par chacun d'eux. En conclure le caractère de divisibilité par 33.

3^ Un nombre inférieur à 100 contient au plus 6 facteurs premiers, distincts ou non.

4* Montrer que le nombre 2» -f 2* -H 2 -f- i n'est pas premier.

5<> Tout nombre premier impair est la différence entre les carrés de deux nombres consécutifs.

6® Les nombres premiers de la forme ik—i ne peuvent être des sommes de deux carrés. Vérifier que tous ceux de la forme 4À + 1 qui sont plus petits que 100 sont des sommes de deux carrés.

V Former la table des nombres premiers compris entre 100 et 200.

8° Chercher si le nombre 2** — 1 est ou n'est pas premier.

9° Former les restes des puissances de 2, relatifs aux modules 13, 17, 73 ; former les restes des puissances des nombres inférieurs à 17 par rapport au module 17.

lOo Montrer que les restes des puissances 1 , a, a^,..., a*"* appartiennent à Texposant < ou à un exposant inférieur, en admettant que a appartienne à l'exposant t.