Les entiers naturels : introduction

Évaluation d’entrée

Avant de parcourir l’unité, il convient de mesurer le point de départ. Cette évaluation est une auto-évaluation : elle n’est pas notée, et son seul but est d’orienter l’étude. Ses dix questions portent, une à une et dans l’ordre, sur les dix leçons de l’unité ; la quatrième demande en outre de mettre sous forme de somme un problème décrit avec des mots. Les mêmes compétences sont mesurées de nouveau à la fin, dans la leçon de synthèse ; comme c’est la première unité du cours, il n’y a pas de questions sur des unités antérieures. Une question qu’on ne parvient pas à résoudre signale la leçon sur laquelle il vaut mieux s’arrêter.

Les contenus de l’unité

Le plan d’études a signalé que le cours construit ses objets au lieu de les supposer connus. Cette première unité est le fondement de cette construction : elle part de quelques axiomes sur les nombres avec lesquels on compte et en déduit toute l’arithmétique des entiers naturels. Le peu qu’elle admet en outre est déclaré expressément en son lieu : les règles de la théorie naïve des ensembles et de la négation des quantificateurs ; l’existence des fonctions définies par récurrence, que garantit le théorème de récurrence de Dedekind ; l’unicité du nombre d’éléments d’un ensemble fini, et la finitude de ses sous-ensembles, sur lesquelles repose le dénombrement ; la commutativité généralisée des produits finis ; et les règles élémentaires des entiers relatifs, des rationnels et des réels, que certains exemples et problèmes anticipent et que l’unité suivante construit. Ses dix leçons forment une chaîne dans laquelle chaque maillon s’appuie sur les précédents.

1. Ensembles, relations et fonctions. Elle fixe le langage dans lequel tout le cours est écrit : les ensembles et leurs opérations, les relations, en particulier les relations d’équivalence et d’ordre, et les fonctions. Les relations d’équivalence reparaîtront dans l’unité suivante, où les entiers relatifs et les rationnels sont construits comme classes de couples.
2. Les entiers naturels et les axiomes de Peano. Elle définit les entiers naturels au moyen de $1$, de l’opération successeur et de cinq axiomes, dont le dernier est le principe de récurrence. Tout ce qui suit dans l’unité est conséquence de ces axiomes et du peu qu’on admet expressément.
3. Opérations de base sur les entiers naturels et relations d’ordre. Elle énonce le théorème de récurrence, définit grâce à lui l’addition, la multiplication et la puissance, démontre par récurrence leurs propriétés et fonde l’ordre sur l’addition. Elle montre que la soustraction et la division n’existent pas toujours entre entiers naturels, ce qui annonce l’unité suivante.
4. Sommes, suites arithmétiques et géométriques, récurrence. Elle introduit la notation de sommation, les sommes télescopiques et les suites arithmétiques et géométriques, et démontre que la récurrence simple implique la récurrence forte et le principe du bon ordre, et en quel sens ceux-ci lui sont équivalents. Le principe du bon ordre sera l’outil de presque toutes les démonstrations d’existence de l’unité.
5. Divisibilité et division euclidienne. Elle démontre, à l’aide du bon ordre, que tout entier relatif admet un quotient et un reste uniques, et par là elle classe les entiers relatifs selon leur reste et justifie les critères de divisibilité.
6. Nombres premiers et théorème fondamental de l’arithmétique. Elle prouve qu’il y a une infinité de nombres premiers et que tout entier naturel strictement supérieur à $1$ se décompose en facteurs premiers d’une seule manière, et elle en déduit, entre autres, que la racine carrée d’un entier naturel qui n’est pas un carré parfait est irrationnelle.
7. Plus grand commun diviseur et plus petit commun multiple. Elle présente l’algorithme d’Euclide, qui calcule le plus grand commun diviseur sans décomposer en facteurs premiers, en déduit l’identité de Bézout et résout complètement les équations diophantiennes linéaires.
8. Congruences et arithmétique modulaire. Elle transforme la division euclidienne en un calcul : deux entiers relatifs sont congrus modulo $n$ lorsqu’ils ont le même reste, et la congruence est compatible avec l’addition et la multiplication, de sorte que bien des problèmes de divisibilité se résolvent en ne calculant qu’avec les restes.
9. Systèmes de numération de position. Elle démontre que tout entier naturel s’écrit d’une seule manière dans n’importe quelle base, explique pourquoi les procédés de calcul appris à l’école sont corrects et pourquoi les ordinateurs travaillent en base $2$.
10. Combinatoire élémentaire et formule du binôme de Newton. Elle définit le nombre d’éléments d’un ensemble fini, démontre les principes additif et multiplicatif, apprend grâce à eux à compter sans énumérer, définit les coefficients binomiaux et démontre la formule du binôme de Newton, qui réunit la récurrence, les sommes et le dénombrement.

L’unité se termine par la leçon de synthèse et défis, qui rassemble l’acquis, reprend dans son évaluation de sortie les compétences de l’évaluation d’entrée et propose des problèmes plus difficiles qui combinent plusieurs leçons.

Le contexte historique

Compter est antérieur à écrire. Des os portant des séries d’entailles, comme celui d’Ishango, découvert au Congo et dont l’ancienneté est estimée à quelque vingt mille ans, sont souvent interprétés comme des relevés de quantités. Les premières civilisations urbaines eurent besoin de compter des troupeaux, de mesurer des champs et de répartir des récoltes, et elles développèrent ainsi des systèmes de numération : il y a environ quatre mille ans, les scribes de Mésopotamie utilisaient déjà une numération de position en base $60$, dont la trace perdure dans la mesure du temps et des angles.

En Grèce, à partir du VIe siècle avant notre ère, les pythagoriciens étudièrent les nombres pour eux-mêmes et non seulement comme instruments de calcul. Ils classèrent les nombres figurés, comme les nombres triangulaires $1$, $3$, $6$, $10$, qui sont les sommes $1 + 2 + \cdots + n$, et distinguèrent les nombres pairs des impairs. Vers l’an 300 avant notre ère, Euclide réunit dans les livres VII à IX des Éléments l’arithmétique de son temps, ordonnée de façon déductive : l’algorithme qui porte son nom, le lemme selon lequel un nombre premier qui divise un produit divise l’un de ses facteurs, la démonstration de l’existence d’une infinité de nombres premiers et la construction des nombres parfaits pairs. Au IIIe siècle avant notre ère, Ératosthène de Cyrène imagina son crible des nombres premiers, et probablement au IIIe siècle de notre ère, Diophante d’Alexandrie étudia dans ses Arithmétiques des équations dont les solutions devaient être des nombres entiers ou rationnels.

La numération décimale avec le zéro comme chiffre se forma en Inde, fut exposée au IXe siècle par al-Khwarizmi et parvint en Europe, entre autres voies, par le Liber Abaci de Fibonacci, en 1202. Le triangle des coefficients binomiaux était connu en Inde, en Perse et en Chine des siècles avant que Pascal lui consacre, au milieu du XVIIe siècle, le traité qui lui donna son nom en Occident. Or le raisonnement par récurrence comme méthode explicite de démonstration est tardif : Francesco Maurolico l’employa dans un ouvrage publié en 1575 pour prouver que la somme des premiers nombres impairs est un carré, et Pascal le formula clairement dans son traité du triangle arithmétique. Au même siècle, Fermat imagina la méthode de descente infinie, une forme du principe du bon ordre, et vers 1665 Newton étendit la formule du binôme de Newton aux exposants fractionnaires et négatifs. En 1801 Gauss publia ses Disquisitiones Arithmeticae, avec lesquelles l’arithmétique devint une théorie systématique, et l’on y trouve la première démonstration explicite de l’unicité de la décomposition en facteurs premiers.

Au cours du XIXe siècle, l’analyse mathématique fut reconstruite sur des bases arithmétiques : les nombres réels furent définis à partir des rationnels, comme le fit Dedekind en 1872 avec ses coupures, les rationnels à partir des entiers relatifs, et les entiers relatifs à partir des entiers naturels. S’il en est ainsi, toute la construction reposait sur les entiers naturels, et il restait à dire ce qu’ils sont et de quels principes se déduit leur arithmétique. En 1861 Hermann Grassmann avait montré que l’addition et la multiplication peuvent être définies par récurrence à partir du successeur, et que leurs propriétés se démontrent par récurrence. En 1888 Richard Dedekind publia son essai Que sont et à quoi servent les nombres ?, qui caractérise les entiers naturels par le successeur et la récurrence, et en 1889 Giuseppe Peano publia, en latin, ses Arithmetices principia, nova methodo exposita, avec la liste d’axiomes que ce cours adopte et qui, comme là-bas, commence à $1$.

Le problème à l’origine de la théorie

Les entiers naturels sont en nombre infini, et presque tout ce qu’il importe d’affirmer à leur sujet est une affirmation sur tous à la fois : que l’addition est commutative, que tout entier naturel strictement supérieur à $1$ se décompose en facteurs premiers, que la somme des $n$ premiers nombres impairs vaut $n^2$. Aucune affirmation de ce genre ne peut être vérifiée en examinant les cas un à un, car on n’en finirait jamais ; et, ce qui est plus grave, la vérification de nombreux cas, si nombreux soient-ils, ne permet de rien conclure sur les autres. Le problème est donc le suivant : étant donné une propriété $P$ des entiers naturels, par quels principes peut-on démontrer que tout entier naturel la vérifie ?

L’exemple suivant montre à quel point les vérifications peuvent tromper.

La réponse de Dedekind et de Peano consiste à poser comme axiome le principe qui permet de passer du fini à l’infini : si une propriété vaut pour $1$ et se transmet de chaque entier naturel à son successeur, elle vaut pour tous. Il s’ensuit un programme précis, qui est celui de cette unité : définir les opérations de sorte que chaque cas se ramène au précédent, et démontrer par récurrence, ou par l’un des principes équivalents, chacune de leurs propriétés. Or le problème a une seconde face, qui parcourt toute l’unité : celle des opérations réciproques. La soustraction et la division ne sont pas toujours possibles entre entiers naturels, et la question de savoir quand elles le sont conduit à la divisibilité, aux nombres premiers et au plus grand commun diviseur ; la question de savoir comment y remédier conduit à l’unité suivante, qui étend les entiers naturels jusqu’aux nombres complexes.

L’importance des entiers naturels

À l’intérieur de ce cours, les résultats de l’unité reparaissent à chaque instant. La leçon sur les entiers relatifs les construit comme des couples d’entiers naturels, et celle sur les rationnels, comme des couples d’entiers relatifs ; la division des polynômes dans la leçon sur les racines des polynômes de degré supérieur imite la division euclidienne, et le schéma de Horner provient de la numération de position. La majoration tirée du binôme pour $\left(1 + \frac{1}{n}\right)^n$ prépare la leçon sur le nombre $e$. La suite de ce cours, Algèbre et géométrie II, continue de les utiliser : dans son unité sur les nombres complexes sous forme trigonométrique, la formule de Moivre se démontre par récurrence, et dans son unité sur les matrices et les structures algébriques, la leçon sur les structures algébriques fait des restes de la division par $n$ un anneau, qui est un corps exactement lorsque $n$ est premier.

Hors de ce cours, les suites et les sommes d’Analyse I s’étudient avec la notation de sommation et avec la récurrence, et la dérivée d’une puissance s’obtient avec la formule du binôme de Newton. Dans Fondements de la mécanique, la loi que Galilée publia en 1638, selon laquelle un corps qui tombe à partir du repos parcourt en des intervalles de temps égaux des distances proportionnelles aux nombres impairs successifs $1, 3, 5, 7, \ldots$, devient, grâce à la somme des premiers nombres impairs, la proportionnalité entre la distance parcourue et le carré du temps. L’intérêt simple et l’intérêt composé de Mathématiques financières sont des suites arithmétiques et géométriques ; les programmes de Programmation en C++ I représentent les nombres en base $2$, calculent des restes et appliquent l’algorithme d’Euclide, et leur récursivité est la même idée que les définitions par récurrence de l’addition et de la multiplication. Le cours de Logique mathématique I : logique propositionnelle étudie les règles de déduction qu’emploient les démonstrations de l’unité.

Dans la science et la technique, la base $2$ est le langage de tout ordinateur, et l’arithmétique des restes sous-tend les chiffres de contrôle qui permettent de détecter les erreurs de copie des numéros de documents, de comptes ou de livres. Le système cryptographique publié en 1977 par Rivest, Shamir et Adleman, sur lequel repose une bonne part de la sécurité des communications, se fonde sur un contraste que cette unité permet de comprendre : l’algorithme d’Euclide calcule rapidement le plus grand commun diviseur de nombres de plusieurs centaines de chiffres, alors qu’on ne connaît aucun procédé rapide pour les décomposer en facteurs premiers. La combinatoire, enfin, est le fondement du calcul des probabilités, et avec lui de la statistique et d’une bonne part de la physique et de la biologie.