§ Posté le 14/10/2011 à 19h 29m 05
Allez, aujourd'hui, on va parler un peu de maths, c'est bien, les maths. Mais que les étudiants en sciences humaines et en littérature (vous savez, ceux à qui est possiblement déconseillé l'excellent webcomic XKCD (traduction française ici 
)) se rassurent : ça va rester tout-à-fait abordable.
En fait, nous allons parler des nombres premiers, qui sont un élément important du passionnant sujet d'étude choisi par certains types biens, quoiqu'expatriés très loin (hop, mon quota de pub pour de bons sites est rempli dès l'intro 
)
Pour commencer, plaçons les choses dans leur contexte. Nous ne nous intéressons ici qu'aux nombres entiers naturels, c'est-à-dire les nombres qui n'ont pas de virgule et qui sont plus grand que zéro. Ceux que l'on utilise le plus naturellement du monde, quoi. Si vous gardez quelques souvenirs de vos cours à l'école élémentaire, je ne pense pas avoir besoin de vous présenter les quatre opérations principales(1) que nous utilisons sur ces nombre : addition, soustraction, multiplication et division.
C'est sur la dernière de ces opérations que nous allons nous pencher maintenant (et aussi un peu à la troisième, vous verrez). Comme vous le savez, quand on ajoute, ou qu'on soustrait deux nombres entiers, ou qu'on en multiplie un par un autre, on obtient toujours un nombre entier comme résultat. Par contre, la division, elle, nous pose un peu plus problème, parce que si on ne fait pas attention, diviser un nombre entier par un autre peut ne pas tomber juste sur un nombre entier.
Quand on rencontre une division à qui ça arrive, il y a deux manières de procéder : soit on prend son courage à deux mains et on continue après la virgule, soit on on s'arrête, et on obtient un reste. Cette deuxième façon de faire est appelée division euclidienne, du nom d'Euclide, un savant grec d'il y a deux mille trois cent ans que l'on considère comme le fondateur des mathématiques modernes(2).
Mais je vous l'ai dit, nous ne nous intéressons ici qu'aux entiers naturels. Donc on va éviter pour l'instant ce problème et ne regarder que les divisions qui « tombent juste », celles pour lesquelles on n'a pas de virgule à franchir et dont le reste vaut zéro. Déjà, elles ne peuvent arriver que si le nombre qu'on divise (le dividende) est plus grand que le nombre par lequel on le divise (le diviseur). Dans le cas contraire, quand on essaye de faire la division à la main, on tombe sur une virgule tout de suite, et ce n'est pas ce que l'on cherche.
Mais même quand le diviseur est plus petit que le dividende, ça ne « marche » pas toujours. En fait, ça ne marche que quand le diviseur, lorsqu'on le multiplie par le résultat de la division (dans le cas d'une division euclidienne, on appelle ce résultat le quotient), nous redonne le dividende.
Je vais encore vous rappeler vos cours d'élémentaire : une division qui « tombe juste » peut donc être vue comme une multiplication à trou ; exactement comme une soustraction peut être vue comme une addition à trou.
Dans ce cas particulier, on dit que le dividende est un multiple du diviseur. Et l'on dit aussi (désolé pour le double-sens du mot, mais je n'y suis pour rien) que ce dernier est un diviseur du premier. Voilà pour les pré-requis en ce qui concerne la division. Venons-en maintenant aux faits.
Vous savez sans doute que diviser ou multiplier n'importe quel nombre par un ne change rien, le nombre d'arrivée sera égal au nombre de départ (puisque j'en suis à vous donner le jargon mathématique, on dit dans ce cas que un est un élément neutre pour la multiplication et pour la division). Vous savez aussi que tout nombre strictement positif(3) divisé par lui-même donne un. Tout nombre plus grand que un admet donc au minimum deux diviseurs : un et lui-même.
Les nombres premiers, dont je vous parlais au début, sont les nombres entiers naturels qui ont la particularité d'avoir très exactement deux diviseurs, c'est-à-dire que n'importe quel autre nombre que un et eux-mêmes par lesquels on les diviserait donnerait un résultat à virgule ou, dans le cas d'une division euclidienne, un reste plus grand que zéro.
On note au passage que un n'est pas considéré comme un nombre premier, parce que s'il correspond à l'explication de la défintion (il n'admet pas de diviseur autre que un et lui-même), il se trouve dans son cas que un est lui-même, et que donc, il n'admet qu'un seul et unique diviseur. Je vous rassure tout de suite, c'est le seul cas particulier bizarre comme ça, les autres nombres sont plus sympas.
Bon, maintenant que nous savons ce que c'est qu'un nombre premier, on peut se demander à quoi ça sert. Je ne développerai pas ce point pour l'instant, mais sachez quand même que c'est super-important, par exemple pour les gens qui veulent que leurs messages ne soient compris que par les gens auxquels ils les adressent. Vous trouverez un (tout petit) peu plus de précisions dans l'article dont je vous parlais en intro, et j'évoquerai sans doute ça dans de futurs articles, mais c'est un peu plus complexe, et j'ai envie que cet article reste simple (j'espère que vous trouvez qu'il l'est).
En plus, on n'a pas forcément besoin d'avoir une finalité pour tout, si ? Savoir des trucs juste pour le plaisir de savoir des trucs, sans que nécessairement ça ne « serve » à quelque chose, c'est quand même sacrément intéressant aussi. Nous sommes en tout cas quelques uns à le penser, et c'est un peu la raison d'être de plusieurs de mes articles.
Plutôt que de m'étendre longuement sur les multiples usages qui en sont faits, je préfère donc vous indiquer une bonne méthode pour les démasquer, à vous de voir ce que vous en ferez. Cette méthode n'est pas toute jeune, puisqu'elle a été inventée, il y a de ça quelques deux mille trois cent ans, par un autre savant célèbre de la Grèce antique, un certain Ératosthène.
Cette méthode est relativement simple, quoiqu'un peu longue à dérouler « à la main », et présente l'avantage d'identifier d'un coup tous les nombres premiers dans un intervalle donné, sans avoir besoin d'essayer de faire la moindre division.
Un de ses autres intérêts est de montrer que le concept d'algorithme a été inventé quelques siècles avant celui d'informatique, bien que certaines personnes aujourd'hui n'aient tendance à croire que le premier n'est qu'une sous-partie du second. L'informatique, en fait, c'est le « traitement automatisé de l'information », c'est-à-dire le fait de dérouler automatiquement des algorithmes sans avoir besoin de le faire à la main.
Mais cet algorithme-ci, c'est à la main que nous allons le faire tourner.
Pour cela, commencez par choisir un nombre maximal à considérer (le cas le plus courant est de choisir 100, parce que c'est un nombre pas trop grand et facile à concevoir pour nous qui comptons en base 10). Puis prenez une feuille de papier (ou un éditeur de texte, si vous préférez taper, mais malgré mon habitude de tout faire au clavier, je trouve personnellement que c'est plus pratique sur papier) et inscrivez, dans l'ordre, tous les nombres situés entre un et votre maximum. Vous pouvez les disposer, par exemple, par rangées de dix, ou tout autre moyen qui vous semblerait agréable.
Une fois ceci fait, commencez par rayer un, qui, on l'a vu, n'est pas concerné. Vous pourriez même ne pas l'écrire du tout, d'ailleurs, ça reviendrait à peu près au même, mais pour les rangées de dix, c'est plus pratique. Bref.
Nous l'avons vu, les notions de multiple et de diviseur vont l'une avec l'autre. Un nombre qui est un multiple d'un autre admet cet autre nombre comme diviseur. C'est là-dessus que nous allons travailler : nous commençons par le premier nombre que nous rencontrons, à savoir deux (le plus petit de tous les nombres premiers), et nous allons rayer de la liste tous ses multiples.
C'est-à-dire que nous allons laisser deux tranquille, mais qu'à partir de lui, nous allons compter de deux en deux et rayer tous les nombres que nous rencontrerons : quatre, six, huit, etc.
Une fois arrivés à la fin de la liste, nous allons revenir au début, choisir le premier nombre non-encore rayé (pour l'instant, c'est facile, c'est trois) et recommencer l'opération, à savoir maintenant compter de trois en trois et rayer tous les nombres sur notre passage : six (qui est déjà rayé, mais ç'n'est pas grave), neuf, douze (idem), etc.
Ensuite, quatre étant rayé, on le laisse tomber et on choisit cinq ; et on recommence à compter de cinq en cinq à partir de lui. Puis, partant de sept, de sept en sept, et ainsi de suite.
On pourrait continuer ainsi jusqu'à avoir terminé toute la liste. En fait, comme ce serait peut-être un peu long et pas forcément sympa (au bout d'un moment, ça finit par faire de grandes marches), il y a quand même un truc pour s'arrêter un peu plus tôt : si le nombre sur lequel vous vous trouvez, multiplié par lui-même (multiplier un nombre par lui-même, ça s'appelle calculer son carré), donne un résultat supérieur à votre nombre maximal (par exemple, si vous vous arrêtez à cent, 11 × 11 donne 121, qui est plus grand que 100), vous pouvez vous arrêter, vous n'avez pas besoin de chercher à rayer ses multiples.
Cela s'explique par le fait qu'un même nombre peut être le multiple de plusieurs autres. Par exemple, quand nous cherchions les multiples de trois, nous n'avons pas eu besoin de rayer six, qui était déjà un multiple de deux. Comme on raye à chaque fois tous les multiples d'un même nombre, on sait qu'à chaque fois, le premier nombre qui ne sera pas encore rayé sera le carré du nombre de départ.
En effet(4), si on prend trois entiers A, B et C, avec B plus grand que C, et qu'on les multiplie l'un par l'autre, A×B sera aussi plus grand que A×C. Pour obtenir un nombre plus petit que le carré du nombre qui nous intéresse (A×A), il aurait donc fallu le multiplier par un nombre plus petit que lui-même. Or, vu qu'on progresse du plus petit au plus grand, tous les multiples des nombres plus petits ont déjà été rayés.
Donc quand on calcule que le carré d'un nombre est plus grand que notre nombre maximal, on sait qu'on ne trouvera plus aucun multiple pas encore barré sans avoir à sortir des nombres qui nous intéressent : on a fini.
Vous pouvez donc maintenant regarder votre liste : les seuls nombres qui ne sont pas barrés sont les nombres premiers inférieurs ou égaux au nombre maximal que vous recherchiez. Vous venez donc de trouver tous les nombres premiers sans avoir à faire la moindre division, et vous venez en plus de dérouler un algorithme à la main. Merci, monsieur Ératosthène !
(Pour vérifier au cas où : si vous aviez choisi de travailler de 1 à 100, les nombres que vous étiez censés trouver sont les suivants : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 et 97. Si ça vous intéresse, vous trouverez sur Wikipédia une image animée vous présentant le déroulement de l'algorithme jusqu'à 120)