Editeurs : Frédéric Jaëck et Éric Vandendriessche. Toute reproduction pour publication ou à des fins commerciales, de la totalité ou d'une partie de l'article, devra impérativement faire l'objet d'un accord préalable avec l'éditeur (ENS Ulm). Toute reproduction à des fins privées, ou strictement pédagogiques dans le cadre limité d'une formation, de la totalité ou d'une partie de l'article, est autorisée sous réserve de la mention explicite des références éditoriales de l'article.
SOMMAIRE
1. Présentation des Disquisitiones par Gauss
1.1 Dédicace
2. Les sections I et II des Recherches arithmétiques
2.1 Un nouveau type d’équations
2.2 Reprendre l’arithmétique dès son principe
2.3 Résolution des congruences du premier degré
2.3.1 Existence des solutions de (mod m) lorsque a et m sont premiers entre eux
2.3.2 Calcul des solutions de $ax+b\equiv c$ (mod m), a et m premiers entre eux
2.3.3 Cas où a et m ne sont pas premiers entre eux
2.3.4 Méthode particulière dans le cas où le module est composé
2.3.5 Problème des congruences simultanées, ou des « restes chinois »
3. Notes
« […] personne n’ignore quelle est l’étendue de votre libéralité à l’égard de ceux qui semblent portés vers l’étude des sciences, et que votre protection est également accordée à celles qui paraissent le plus abstraites et d’une application moins directe aux usages ordinaires de la vie, parce que dans la profondeur de votre sagesse, habile à profiter de tout ce qui tend au bonheur et à la prospérité de la société, vous avez senti la laison intime et nécessaire qui unit entre elles toutes les sciences. »
Gauss expose ce qu’il entend par arithmétique élémentaire et arithmétique transcendante, puis donne quelques points de vue sur ses prédécesseurs :
« […] En effet, de même que l'on rapporte à l'Analyse toutes les recherches que l'on peut faire sur les affections générales des quantités, la considération des nombres entiers et des fractions, quand ces dernières s'expriment au moyen de nombres entiers, constituent proprement l'objet de l’Arithmétique ; mais on ne donne ordinairement sous ce nom que l'art de former les nombres et de les calculer, c'est-à-dire, l'art de représenter les nombres par des signes convenables (par exemple, suivant le système décimal), et d'exécuter les opérations arithmétiques, en y ajoutant quelques points, dont les uns n'appartiennent pas à l'Arithmétique, comme la théorie des logarithmes et les autres ne sont pas particuliers aux nombres entiers, et ont lieu pour toutes les quantités. On voit par là que l'on doit distinguer deux parties dans l'Arithmétique, et que les considérations dont nous venons de parler se rapportent à l'Arithmétique élémentaire, tandis que les recherches générales sur les affections particulières aux nombres entiers sont revendiquées par l’Arithmétique transcendante.
Ce qu’Euclide a présenté dans le Livre VII de ses Elémentsii, avec l'élégance et la rigueur ordinaires aux anciens, appartient à l'Arithmétique transcendante, mais se borne aux premiers éléments. Le célèbre Ouvrage de Diophanteiii, qui est consacré tout entier aux problèmes indéterminés, contient un grand nombre de questions qui, par leur difficulté et la subtilité des artifices, donnent une grande idée du génie et de la pénétration de l'auteur, surtout quand on considère le peu de ressources qu'il pouvait employer ; mais comme ces problèmes demandent plutôt de l'adresse et des procédés ingénieux que des principes difficiles, et qu'en outre ils sont trop particuliers et conduisent rarement à des conclusions générales, cet Ouvrage semble plutôt avoir fait époque dans l'histoire des Mathématiques, parce qu'il fixe les premiers vestiges de l'Algèbre, qu'avoir enrichi l'Arithmétique transcendante par de nouvelles découvertes. La Science est bien plus redevable aux modernes, parmi lesquels peu d'hommes à la vérité, mais tous dignes d'une gloire immortelle, Fermat, Euler, Lagrange, Legendre (et un petit nombre d'autres), ont ouvert l'entrée de cette science divine, et ont découvert la mine inépuisable de richesses qu'elle renferme. Je n'entre pas ici dans l'énumération des découvertes de ces géomètres, d'autant qu'on peut les connaître par la Préface des Additions dont Lagrange a enrichi l’Algèbre d'Euler, et par celle de l'Ouvrage de Legendreiv, dont nous parlerons bientôt. D'ailleurs nous rendrons hommage à ces différentes découvertes, lorsque l'occasion s'en présentera dans nos Recherches. »
Gauss révèle ensuite le problème qui l’a passionné et lui a fourni l’occasion de renouveler la science des nombres entiers presque dès son principe :
« Mais afin que l'on ne s'étonne pas de voir ici la Science prise presque dès son principe, et que je sois revenu sur des recherches faites déjà par plusieurs autres, j'ai cru qu'il n'était pas inutile d'avertir que, lorsqu'en 1796, j'ai commencé à m'appliquer à ce genre de considérations, je n'avais absolument aucune idée de tout ce qui avait été fait sur ce sujet, même par les modernes, et que j'étais privé de tous les secours que j'aurais pu tirer de leurs travaux. Occupé dans ce temps d'une autre matière, je tombai par hasard sur une vérité importante de l'Arithmétique (c'était, si je ne me trompe, le théorème du n° 108v) ; comme elle me sembla très-belle par elle-même, et que je la soupçonnais liée à d'autres plus importantes, j'employai toute la contention d'esprit dont j'étais susceptible, à découvrir les principes sur lesquels elle s'appuyait, et à en trouver une démonstration rigoureuse ; le succès ayant répondu à mes vœux, je me sentis tellement entraîné par l'attrait de ces questions, qu'il me fut impossible de les abandonner, et comme une vérité me conduisait à une autre, la plus grande partie des quatre premières sectionsvi était déjà terminée avant que j'eusse rien vu des travaux des autres géomètres sur ce sujet. M'étant ensuite trouvé à même de lire les ouvrages de ces hommes de génie, je ne tardai pas à reconnaître que j'avais employé la plus grande partie de mes méditations à des choses faites depuis longtemps ; mais animé d'une nouvelle ardeur, je m'efforçai, en suivant leurs pas, de cultiver plus avant le champ de l'Arithmétique, et telle a été l'origine des sections V, VI et VIIvii. »
Stimulé au départ par un problème particulier très éloigné du problème des restes chinois, il s’agit donc pour Gauss de reprendre toute l’arithmétique. Dans ce cadre, le problème chinois n’est que l’un des nouveaux problèmes qui se posent si l’on décide de mettre au centre de l’arithmétique un nouveau type d’équations, qu’il appelle justement congruences :
« Nous appelons congruence l'expression de deux quantités congrues, à l'instar des équations ; si elle renferme une inconnue, la résoudre, c'est trouver pour cette inconnue une valeur qui satisfasse à la congruence, c'est-à-dire la racine de cette congruence. On conçoit par là ce que c'est qu'une congruence résoluble, et une congruence irrésoluble. On voit enfin que nous emploierons les mêmes distinctions qui ont lieu dans les équations. Nous verrons plus bas des exemples de congruences transcendantes. Quant aux congruences algébriques, elles se divisent selon la plus haute puissance de l'inconnue, en congruences du premier, du second degré, etc. On peut même proposer plusieurs congruences qui renferment plusieurs inconnues, et de l'élimination desquelles nous traiteronsviii. »
Nous aurons donc, par analogie avec les types d’équations, des congruences du premier degré (section II) et des congruences du second degré (section IV). Le problème des restes chinois, qui est du premier degré, est par conséquent traité dans la section II.
Pour reprendre toute l’arithmétique « presque dès son principe » à partir de la relation de congruence, Gauss donne d’abord dans la section I les définitionsix et les propriétés immédiates qu’il prend soin de relier à des problèmes simples bien connus, comme les critères de divisibilité et les preuves par 9 et par 11 :
« Plusieurs des théorèmes que l'on a coutume d'exposer dans les traités d'arithmétique, s'appuient sur ceux que nous avons présentés ; par exemple, la règle pour reconnaître si un nombre est divisible par 9, 11, ou tout autre nombre. Suivant le module 9 toutes les puissances de 10 sont congrues à l'unité ; donc si le nombre est de la forme $a+10b+100c+1000d$ etc., il aura, suivant le module 9, le même résidu minimumx que $a+b+c$ etc. Il est clair d'après cela, que si l'on ajoute les figures du nombre, sans avoir égard au rang qu'elles occupent, la somme que l'on obtiendra, et le nombre proposé auront les mêmes résidus minima ; si donc ce dernier est divisible par 9, la somme des chiffres le sera aussi, et seulement dans ce cas. Il en est de même du diviseur 3. Comme suivant le module 11, $100\equiv +1$, on aura généralement ${{10}^{2k}}\equiv 1$, ${{10}^{2k+1}}\equiv 10\equiv -1$ et le nombre de la forme $a+10b+100c+$ etc., aura le même résidu minimum que $a-b+c-$ etc. ; d'où dérive sur-le-champ la règle connue. On déduira facilement du même principe toutes les règles semblables.
Ce qui précède donne encore la raison des règles que l'on prescrit ordinairement pour la vérification des opérations arithmétiques ; savoir, lorsque de nombres donnés on doit en déduire d'autres par addition, soustraction, multiplication ou élévation aux puissances. On n'a qu'à substituer dans les opérations, à la place des nombres donnés, leurs résidus minima, suivant un module quelconque (ordinairement 9 ou 11, parce que dans le système décimal, comme nous venons de le voir, on trouve facilement les résidus relatifs à ces modules) ; les nombres résultants devront être congrus à ceux qu'on déduirait des nombres donnés, sinon il y aurait un vice dans le calcul.
Mais il serait superflu de nous arrêter plus longtemps sur ces résultats très connus, ainsi que sur ceux du même genrexi. »
Dans la section II, Gauss démontre les théorèmes de base de l’arithmétique. En premier lieu :
|
« Si aucun des deux nombres a et b n'est divisible par un nombre premier p, le produit ab ne le sera pas non plusxii. » |
Dit autrement : si p est premier et si p divise le produit ab, alors p divise a ou divise b. L’importance « algébrique » de ce résultat saute aux yeux si on l’écrit (ce que Gauss ne fait pas) sous la forme : avec un module p premier, $ab\equiv 0$ entraîne $a\equiv 0$ ou $b\equiv 0$. L’auteur ajoute à cette occasion :
« La démonstration de ce théorème a déjà été donnée par Euclide, El. VII, 30xiii. Nous n'avons pas cependant voulu l'omettre, tant parce que plusieurs auteurs modernes ont présenté des raisonnements vagues au lieu de démonstration, ou bien ont négligé ce théorème ; que dans le but de faire mieux saisir, par ce cas très simple, l'esprit de la méthode que nous appliquerons par la suite à des points bien difficilesxiv. »
Puis :
|
« Un nombre composé ne peut se résoudre que d'une seule manière, en facteurs premiersxv. » |
avec, encore une fois, l’arrière pensée de refondation rigoureuse :
« Il est évident par les éléments, que l'on peut toujours décomposer un nombre quelconque en facteurs premiers ; mais on suppose à tort tacitement que cette décomposition ne soit possible que d'une manièrexvi. »
Il en déduit les règles pour obtenir le PGCD et le PPCM de plusieurs nombres à partir de leur décomposition en facteurs premiers, puis le résultat qui sera baptisé « théorème de Gauss » :
|
« Si a est premier avec b, et que ak soit divisible par b, k sera aussi divisible par bxvii. » |
Après l’entrée en matière qui précède, l’auteur passe au problème central de la section II, à savoir la résolution des congruences du premier degré, dont notre problème des restes chinois est un aspect.
Voici la substance de son raisonnement, à partir d’un exemple, le sien : soit à résoudre $6x+5\equiv 13$ (mod 11). Comme 2 et 11 sont premiers entre eux, l’équation équivaut à $3x\equiv 4$ (mod 11). Lorsque $x$ varie de 0 à 10 les restes des divisions de $3x$ par 11 sont nécessairement différents ; si on avait en effet deux valeurs $x_1$ et $x_2$ de $x$, avec par exemple $x_1 > x_2$, telles que $3x_1=11q_1 +r$ et $3x_2 = 11 q_2 +r'$, 11 diviserait $"(x_1 - x_2 )$, et d’après le théorème de Gauss il diviserait aussi $x_1 - x_2$, ce qui est impossible avec $x_1$ et $x_2$ compris entre 0 et 10. Les onze nombres $3x$, si on les divise par 11, auront donc onze restes différents, lesquels sont par conséquent tous les nombres de 0 à 10. Il existe donc bien un $x$ tel que $3x=11q +4$, en l’occurrence $x = 5$. Il est clair que, 3 et 11 étant premiers entre eux, les autres solutions seront congrues à 5 modulo 11.
Si l’équation de départ était, par exemple, $3x\equiv 13$ (mod 11), il faudrait prendre l’équation équivalente $3x\equiv 2$ (mod 11) pour appliquer le raisonnement précédent.
En conclusion, l’équation $ax + b \equiv c$ (mod m), où m est premier avec a, a nécessairement une solution $v$, et la solution générale est $x\equiv v $ (mod m). On peut donc dire que l’équation a une solution unique :
« Comme les résolutions de la congruence par les valeurs de $x$ congrues à $v$, se présentent d'elles-mêmes, et que sous cet aspect les nombres congrus doivent être considérés comme équivalents, nous regarderons ces solutions comme une seule et même. C'est pourquoi nous dirons que la congruence $ax + b \equiv c$, qui n'en admet pas d'autres, ne peut être résolue que d'une seule manière ou n'a qu'une seule racinexviii. »
Après avoir fait remarquer que les solutions dépendent des solutions d’une équation indéterminée du type $ax=by \pm 1$, et que celles-ci sont connues depuis Euler (voir le chapitre III de la brochure), il se contente de quelques indications, tout en inventant au passage une notation, dite aujourd’hui « crochets de Gauss » :
« 27. Il nous reste à donner quelques détails sur la manière de résoudre ces congruences. Observons d'abord que la congruence $ax+t\equiv u$, dans laquelle le module est supposé premier avec a, dépend de celle-ci, $ax\equiv -1$. En effet, si $x\equiv r$ satisfait à celle-ci, $x\equiv \pm r(u-t)$ satisfera à la première ; mais en désignant le module par b, la congruence $ax\equiv \pm 1$ équivaut à l'équation indéterminée $ax=by\pm 1$, dont la solution est connue ; aussi nous nous contenterons de donner ici l'algorithme du calcul.
Si les quantités A, B, C, etc. dépendent de $\alpha, \beta, \gamma$ etc. de manière qu'on ait $A=\alpha $, $B=\beta A+1$, $C=\gamma B+A$, $D=\delta C+B$ etc. ; nous les représenteronsxix pour abréger, par $A=[ \alpha ]$, $B=[ \alpha ,\beta ]$, $C=[ \alpha ,\beta ,\gamma ] $, $D=[ \alpha ,\beta ,\gamma ,\delta ]$ etcxx. Soit maintenant l'équation $ax=by\pm 1$ où a et b sont positifs. Supposons, ce qui est permis, que a n'est pas < b. Alors en opérant comme on le fait ordinairementxxi pour la recherche du plus grand diviseur commun, on formera par la division les équations
$a=\alpha b+c\text{, }b=\beta c+d\text{, }c=\gamma d+e$
dans lesquelles $\alpha, \beta, \gamma, \delta$, etc., sont entiers et positifs : et b, c, d, etc. vont en diminuant continuellement jusqu'à ce qu'on parvienne à$m=\mu n+1$ ; ce qui doit toujours arriver.
Il en résultera $a=\left[ n,\mu \ldots \gamma ,\beta ,\alpha \right]$ ; $b=\left[ n,\mu \ldots \gamma ,\beta \right] $ ; et si l’on prend $x=\left[ \mu \ldots \gamma ,\beta \right] $, $y=\left[ \mu \ldots \gamma ,\beta ,\alpha \right] $, on aura $ax=by+1$ quand le nombre des lettres $ \alpha, \beta, \gamma, \dots \mu, n$ est pair et $ax=by-1$ quand il est impairxxii.
28. Euler est le premier qui ait donné la résolution de ces équations (Comment. de Petersb. T. VII, p. 46xxiii). La méthode qu’il a employéexxiv consiste à substituer d’autres inconnues à la place de x et de y, elle est d’ailleurs assez connue. Lagrange a traité le problème d’une manière un peu différente. Il observe que si l’on réduit la fraction b/axxv en fraction continue :
$\displaystyle \frac{1}{\alpha +\displaystyle\frac{1}{\beta +\displaystyle\frac{1}{\gamma +\dots\displaystyle \frac{1}{\mu +\frac{1}{n}}}}}$
et qu’après avoir effacé sa dernière partie $\frac{1}{n}$, on la ramène à une fraction ordinaire $\frac{x}{y}$, on auraxxvi $ax=by\pm 1$. Au reste les deux méthodes conduisent au même algorithme. Les recherches de Lagrange se trouvent dans l’Histoire de l’Académie de Berlin, année 1767, p. 175, et avec d’autres, dans les Additions à l’Algèbre d’Euler. »
2.3.3 Cas où a et m ne sont pas premiers entre eux
On se ramène au cas précédent :
« 29. La congruence $ax+t\equiv u$, dans laquelle le module n'est pas premier avec a, se ramène facilement au cas précédent. Soit m le module et $\delta $ le plus grand diviseur commun entre a et m ; il est clair d'abord que toute valeur de $x$ qui satisfera à la congruence suivant le module m, y satisfera aussi suivant le module $\delta $ (n° 5). Puisque $\delta$ divise a, on a toujours $ax\equiv 0$ (mod $\delta$) ; donc on doit avoir $t\equiv u$ (mod $\delta$), ou $t-u$ divisible par $\delta$, pour que la congruence soit résoluble.
Posons donc $a=\delta e$, $m=\delta f$, $t-u=\delta k$ ; e et f seront premiers entr'eux, et la congruence proposée $\delta ex+\delta k\equiv 0$ (mod $\delta f$), équivaudra à celle-ci, $ex+k\equiv 0$ (mod f) ; c'est-à-dire, que toute valeur de x qui satisfera à la seconde, satisfera aussi à la première, et vice versa. En effet, ex+k sera divisible par f, quand $\delta ex+\delta k$ le sera par $\delta f$ et réciproquement. Mais nous avons résolu la congruence $ex+k\equiv 0$ (mod f) ; il suit de là que si $\nu$ est une des valeurs de $x$, la congruence $x\equiv \nu $ (mod f) , donne la résolution complète de la proposée. »
Nous la donnons à partir de l’exemple que Gauss lui-même a choisi (§30).
Soit à résoudre l’équation $ 19 x\equiv 1 $ (mod 140). On la résout d’abord suivant le module 2, diviseur de 140, ce qui donne $ x\equiv 1 $ (mod 2), d’où $ x=1+2x' $. Mais si toute solution de $ 19x\equiv 1 $ (mod 140) est solution de $ 19x \equiv 1 $ (mod 2), la réciproque est fausse. Il faut donc trouver $ x' $ tel que $ x = 1+2 x' $ soit solution de $ 19 x \equiv 1 $ (mod 140), ce qui donne, après substitution, l’équation $ 38 x' \equiv -18 $ (mod 140), d’où $19x'v\equiv -9 $ (mod 70).
A son tour, cette dernière équation se résout d’abord suivant le module 2, diviseur de 70. On trouve $x'\equiv 1$ (mod 2), c’est-à-dire $x'=1+2x''$, et comme précédemment il faut trouver $x’'' $ tel que $x’$ soit solution de $19x'\equiv -9$ (mod 70). On obtient l’équation $38x''\equiv -28$ (mod 70), d’où $19x''\equiv -14$ (mod 35).
Cette équation résolue suivant le module 5, diviseur de 35, donne $x''\equiv 4$ (mod 5), c’est-à-dire $x''=4+5x'''$, et il faut comme précédemment trouver $x'''$ tel que $x''$ soit solution de $19x''\equiv -14$ (mod 35). On obtient l’équation $95x'''\equiv -90$ (mod 35), i.e. $19x'''\equiv -18$ (mod 7). On trouve $x'''\equiv 2$ (mod 7), d’où $x'''=2+7k$.
En remontant jusqu’à x, on trouve qui est la solution cherchée.
Après la résolution des congruences du premier degré, on passe enfin à la résolution de systèmes de congruences du premier degré. Nous donnons le texte complet de Gauss (section II, § 32 à 36), auquel nous avons ajouté des sous-titres.
« 32. On peut facilement, au moyen de ce qui précède, trouver tous les nombres qui ont des résidus donnés, suivant des modules quelconques ; problème qui sera d’un fréquent usage dans la suite. Soient d’abord deux modules A et B, suivant lesquels le nombre cherché z doit être congru aux nombres a et b. Toutes les valeurs de z sont nécessairement renfermées dans la formule $Ax+a$, où x est indéterminé, mais tel que $Ax+a\equiv b$ (mod B), de sorte que si $\delta$ est le plus grand diviseur commun de A et de B, la résolution complète de cette congruence prendra cette formexxvii$x\equiv \nu $ (mod $\frac{B}{\delta }$) ; ou ce qui revient au même $x=\nu +\frac{KB}{\delta }$, K étant un nombre entier indéterminé ; donc la formule $a+A\nu +\frac{KAB}{\delta }$ renferme toutes les valeurs de z, ce qui revient à $z\equiv a+A\nu $ (mod $\frac{AB}{\delta }$). S’il y avait un troisième module C, suivant lequel le nombre cherché dût être $\equiv c$, on suivrait la même démarche, après avoir réuni les deux premières conditions en une seule. Ainsi soit $\varepsilon$ le plus grand commun diviseur des nombres $\frac{AB}{\delta }$ et C, on obtiendra la congruence $\frac{AB}{\delta }x+a+A\nu \equiv c$ (mod C), qui sera résolue par une congruence de la forme $x\equiv w$ (mod $\frac{C}{\varepsilon }$)xxviii, et le problème le sera par la congruence $z\equiv \frac{AB}{\delta }w+a+A\nu $ (mod $\frac{ABC}{\delta \varepsilon }$) ; on procéderait de même, quelque fût le nombre des modules. Il convient d’observer que $\frac{AB}{\delta }$ et $\frac{ABC}{\delta \varepsilon }$ sont respectivement les plus petits nombres divisibles à la fois par A et B, ou par A, B et C, et l’on en conclut facilement, quelque soit le nombre des modules A, B, C, etc., que si l’on représente par M le plus petit nombre divisible par chacun d’eux, on aura la résolution complète, en prenant $z\equiv r$ (mod M). Au reste, si l’une des congruences n’est pas résoluble, il faut en conclure que le problème est impossible ; mais il est évident que cela ne peut arriver si les nombres A, B, C, etc. sont premiers entre euxxxix.
Soient par exemplexxx A = 504, B = 35, C = 16, a = 17, b = -4, c = 33 ; ici les deux conditions que $z\equiv 17$ (mod 504), et $\equiv -4$ (mod 35), se réduisent à une seule $z\equiv 521$ (mod 2520), qui, jointe à la troisième $z\equiv 33$ (mod 16), donnera enfin $z\equiv 3401$ (mod 5040). »
« 33. Quand tous les nombres A, B, C, etc. sont premiers entre eux, leur produit est le plus petit nombre divisible par chacun d’entre eux ; et dans ce cas il est évidentxxxi que toutes les congruences $z\equiv a$ (mod A), $z\equiv b$(mod B), etc. se ramèneront à une seule $z\equiv r$ (mod R) qui leur équivaudra, R étant le produit des nombres A, B, C, etc. : il suit de là réciproquement qu’une seule condition $z\equiv r$ (mod R) peut être décomposée en plusieurs $z\equiv r$ (mod A), $z\equiv r$ (mod B), $z\equiv r$ (mod C), etc. si A, B, C, etc. sont les différents facteurs premiers entre eux qui composent R. Cette observation nous donne non seulement de découvrir l’impossibilité lorsqu’elle existe, mais encore une méthode plus commode et plus élégante pour déterminer les racines.
34. Soient comme ci-dessus les conditions $z\equiv a$ (mod A), $z\equiv b$ (mod B), $z\equiv c$ (mod C), etc. On résoudra tous les modules en facteurs premiers entre eux ; A en A’A’’A’’’ etc. ; B en B’B’’B’’’ etc. ; de manière que les nombres A’, A’’, etc., B’, B’’, etc. soient premiers ou puissances de nombres premiers ; si l’un des nombres A, B, C, etc. était premier lui-même ou puissance d’un nombre premier, il n’y aurait, pour lui, aucune décomposition à faire. Alors, ce qui précèdexxxii fait voir que l’on peut, aux conditions données substituer les suivantes $z\equiv a$ (mod A’), $z\equiv a$ (mod A’’), $z\equiv a$ (mod A’’’), etc. ; $z\equiv b$ (mod B’), $z\equiv b$ (mod B’’), etc., etc. Or, à moins que tous les nombres A, B, C, etc. ne fussent premiers entre eux ; par exemple si A n’est pas premier avec B, il est évident que tous les diviseurs premiers ne peuvent être différents dans A et dans B, mais qu’il doit y avoir quelqu’un des diviseurs A’, A’’ etc., qui trouve son égal, son multiple, ou son sous-multiple parmi les diviseurs B’, B’’, etc. Soit d’abord A’ = B’, les conditions $z\equiv a$ (mod A’), $z\equiv b$ (mod B’) doivent être identiques, et l’on doit avoir $a\equiv b$ (mod A’ ou B’) ; ainsi l’une ou l’autre de ces conditions peut être rejetée ; mais si l’on n’a pas $a\equiv b$, le problème est impossible. Soit ensuite B’ un multiple de A’, la condition $z\equiv a$ (mod A’) doit être contenue dans celle-ci $z\equiv b$ (mod B’), ou bien celle-ci $z\equiv b$ (mod A’), qui se déduit de la dernière, doit être équivalente à la première ; d’où il suit que la condition $z\equiv a$ (mod A’), peut être rejetée, si elle ne contrarie pas l’autre, auquel cas le problème serait impossiblexxxiii. Quand toutes les conditions superflues sont ainsi rejetées, il est évident que tous les modules qui restent sont premiers entre eux ; on est sûr alors de la possibilité du problème, et on peut procéder de la manière enseignée plus haut.
35. Si nous supposons comme au n°32 $z\equiv 17$ (mod 504), $\equiv -4$ (mod 35), $\equiv 33$ (mod 16) ; ces conditions peuvent se décomposer en celles qui suivent : $z\equiv 17$ (mod 8), $\equiv 17$ (mod 9), $\equiv 17$ (mod 7) ; $z\equiv -4$ (mod 5), $\equiv -4$ (mod 7) ; $z\equiv 33$ (mod 16). De ces conditions on peut rejeter $z \equiv 17$ (mod 8) et $z\equiv 17$ (mod 7) car la première est renfermée dans la condition $z\equiv 33$ (mod 16)xxxiv et la seconde est équivalente à $z\equiv -4$ (mod 7) : il reste ainsi
$z\equiv \left\{ \begin{array}{rl} 17 & \mbox{(mod 9)} \\ -4& \mbox{(mod 5)} \\ -4 & \mbox{(mod 7)} \\ 33 & \mbox{(mod 16)} \end{array} \right.$ d’où l’on tire $z\equiv 3041$ (mod 5040).
Au reste il est clair qu’il sera plus souvent plus commode de ramener à une seule les conditions qui restent et qui proviennent de la même, ce qui se fera sans peine. Par exemple, quand on a rejeté quelques unes des conditions $z\equiv a$ (mod A’), $z\equiv a$ (mod A’’), etc. celle qui se composera des conditions restantes sera $z\equiv a$, suivant le module formé par le produit de tous les modules qui restent. Ainsi dans notre exemple les conditions $z\equiv -\text{ }4$ (mod 5), $z\equiv -\text{ }4$ (mod 7) ; on tire sur le champ la condition $z\equiv -\text{ }4$ (mod 35), d’où elles dérivent ; il s’en suit qu’il n’est pas indifférent, quant à la brièveté du calcul, de rejeter l’une ou l’autre des conditions équivalentes ; mais il n’entre pas dans notre plan de parler de ces détails ni d’autres artifices pratiques que l’usage apprend mieux que les préceptes. »
« 36. Quand tous les modules A, B, C, etc. sont premiers entre eux, il est préférable le plus souvent d’employer la méthode suivante. On déterminera un nombre $\alpha$ congru à l’unité suivant A, et à 0 suivant le produit des autres modules ; c’est-à-dire, que $\alpha$ sera une valeur de l’expression $\frac{\text{1}}{BCD\text{ etc}\text{.}}$ (mod A), multipliée par BCDxxxv etc. (n°32) ; mais il vaut mieux prendre la plus petite de ces valeurs. Soit de même $\beta \equiv 1$ (mod B), et $\equiv 0$ (mod ACD etc.) $\gamma \equiv 1$ (mod C) et $\equiv 0$(mod ABD etc.). Alors si l’on cherche un nombre z qui soit congru aux nombres a, b, c, etc. suivant les modules A, B, C, etc. respectivement, on pourra poser $z\equiv \alpha a+\beta b+\gamma c$ etc. (mod ABCD etc.) ; en effet on a évidemment $\alpha a\equiv a$(mod A), et les autres termes sont $\equiv $0 (mod A) ; donc $z\equiv a$ (mod A). La démonstration est la même pour les autres modules. Cette solution est préférable à la première quand on a à résoudre plusieurs problèmes du même genre, pour lesquels les valeurs de A, B, C, etc. sont les mêmes, car alors on trouve pour $\alpha, \beta$, etc. des valeurs constantes. Ceci s’applique au problème de la chronologie dans lequel on cherche le quantième de l’année dans la période juliennexxxvi pour laquelle l’indiction, le nombre d’or et le cycle solaire sont donnésxxxvii. Ici A = 15, B = 19, C = 28 ; ainsi comme la valeur de l’expression $\frac{1}{19\times 28}$ (mod 15), ou $\frac{1}{532}$ (mod 15) est 13, on aura $\alpha = 6916$ ; on trouvera de même $\beta = 4200$, $\gamma = 4845$. Donc le nombre cherché sera le résidu minimumxxxviii du nombre $6916a+4200b+4845c$ où a représente l’indiction, b le nombre d’or, et c le cycle solaire. »
Avec ce paragraphe qui clôt nos extraits des Recherches arithmétiques ainsi que notre choix de textes sur le « problème des restes chinois », la méthode de Maître Sunxxxix, apparue quelque seize siècles avant Gauss, est enfin intégrée dans un véritable traité de théorie des nombres, de surcroît texte fondateur de l’arithmétique moderne.
i Titre exact : Epitre dédicatoire de l’auteur. A son Altesse Sérénissime, Monseigneur Charles-Guillaume-Ferdinand, Duc de Brunswick et de Lunebourg.
ii Le livre VII est le premier des livres arithmétiques des Éléments d’Euclide.
iii Il s’agit des Arithmétiques de Diophante d’Alexandrie (IIIe siècle après J.-C. ?).
iv Adrien-Marie Legendre : Essai sur la théorie des nombres (1798).
v La « vérité importante de l’arithmétique » est énoncée dans la section IV intitulée Des congruences du second degré : « -1 est résidu [quadratique] de tous les nombres premiers de la forme $4n+1$, et non résidu [quadratique] de tous les nombres premiers de la forme $4n+3$ ». Ce qui signifie : si p est un nombre premier de la forme $4n+1$, il existe un nombre a tel que $a^2\equiv -1$ (mod p). Si p est un nombre premier de la forme 4n+3, il n’existe pas de nombre a tel que $a^2\equiv -1$ (mod p).
vi Section I : Des nombres congrus en général. Section II : Des congruences du premier degré. Section III : Des résidus des puissances. Section IV : Des congruences du second degré.
vii Section V : Des formes et des équations du second degré. Section VI : Applications des recherches précédentes. Section VII : Des équations qui déterminent les divisions du cercle. A propos de la section VII, Gauss dit dans sa préface : « La théorie de la division du cercle, ou des polygones réguliers, qui compose la section VII, n'appartient pas par elle-même à l'Arithmétique, mais ses principes ne peuvent être puisés que dans l'Arithmétique transcendante. Ce résultat pourra sembler aux géomètres, aussi inattendu que les vérités nouvelles qui en dérivent, et qu'ils verront, j'espère, avec plaisir. »
viii Section II, §25.
ix Gauss introduit en particulier le signe « » qu’il justifie ainsi : « Nous avons adopté ce signe à cause de la grande analogie qui existe entre l'égalité et la congruence. C'est pour la même raison que Legendre, dans des mémoires que nous aurons souvent occasion de citer, a employé le signe même de l'égalité, pour désigner la congruence ; nous en avons préféré un autre, pour prévenir toute ambiguïté. »
x Deux nombres a et b sont résidus l’un de l’autre modulo m si et seulement si a et b sont congrus modulo m. Le résidu minimal de a modulo m correspond ici au reste de la division euclidienne de a par m.
xi Section I, §12.
xii Section II, §14.
xiii Selon la traduction de Bernard Vitrac, la proposition VII-30 d’Euclide est la suivante : « Si deux nombres se multipliant l’un l’autre produisent un certain nombre et si un certain nombre premier mesure leur produit, il mesurera aussi l’un des nombres initiaux ». Euclide, Les Éléments, vol. 2, PUF.
xiv Section II, §14.
xv Section II, §16.
xvi Id.
xvii Section II, § 19.
xviii Section II, § 26.
xix La notation qui suit s’appelle « crochets de Gauss ». Son inconvénient pour nous est qu’elle entre en concurrence avec la notation actuelle des fractions continues. On vérifie en effet que $\frac{D}{C}=\delta +\displaystyle \frac{1}{\gamma+{\displaystyle \frac{1}{\beta+\frac{1}{\alpha}}}}$, fraction qui s’écrit dans la notation actuelle : $[\delta, \gamma, \beta, \alpha].$ ${\frac{C}{B}}$ est la fraction $[\gamma, \beta, \alpha]$, $\frac{B}{A}$ la fraction $[ \beta, \alpha ]$, d’où le calcul de D de proche en proche.
xx « On peut considérer cette relation de quantités d'une manière plus générale, ainsi que nous pourrons le faire dans une autre occasion. Nous ajouterons seulement ici deux propositions qui trouvent leur application dans la question présente, savoir : $[ \alpha, \beta, \gamma, \dots , \lambda, \mu ] . [\beta, \gamma, \dots, \lambda] – [\alpha, \beta, \gamma, \dots , \lambda ] . [\beta, \gamma, \dots , \lambda, \mu ]=\pm 1$, où l'on prendra le signe supérieur, lorsque le nombre des quantités $\alpha, \beta, \gamma, \dots , \lambda, \mu $ sera pair, et le signe inférieur dans le cas contraire. Et on peut renverser l'ordre des quantités $\alpha, \beta, \gamma$, etc. de sorte que $[\alpha, \beta, \gamma, \dots , \lambda, \mu ]=[\mu, \lambda, \dots , \gamma, \beta, \alpha ]$. Nous supprimons ici les démonstrations qui n'offrent aucune difficulté. » Note de Gauss.
xxi La méthode « ordinaire » est la méthode des divisions successives, objet de la proposition II du livre VII des Éléments d’Euclide. La méthode donnée par Gauss (section II, §18) est une application de la décomposition en facteurs premiers.
xxii D’après les formules données dans la note 22 ci-dessus.
xxiii Il s’agit des Commentaires de l’académie des sciences de Saint-Pétersbourg, dont nous avons donné des extraits dans le chapitre III.
xxiv Voir le chapitre III de la présente brochure.
xxv La traduction française de Poullet-Delisle donne par erreur a/b.
xxvi Puisqu’en termes de crochets de Gauss on a $x = [\mu, \dots , \gamma, \beta]$ et $y = [\mu, \dots , \gamma, \beta, \alpha]$, on aura en termes de fraction continue (voir note 21) $\frac{y}{x}= [\alpha, \beta, \gamma, \dots, \mu ]$, et par conséquent $\frac{y}{x}$ est bien la fraction donnée par Gauss, après « effacement » de n, avec x au numérateur et y au dénominateur.
xxvii D’après le §29 de Gauss.
xxviii La traduction française de Poullet-Delisle donne par erreur $\frac{C}{\delta}.$
xxix Il est clair que par « premiers entre eux », il faut entendre « premiers entre eux deux à deux ».
xxx Cet exemple sera repris au paragraphe 35 avec une méthode « plus simple et plus élégante ».
xxxi D’après le § 32 de Gauss.
xxxii C’est à dire le § 30 consacré aux « modules composés ».
xxxiii Comme B’ est un multiple de A’, $z\equiv b$ (mod B’) entraîne $z\equiv b$ (mod A’). On doit donc avoir à la fois $z\equiv a$ (mod A’) et $z\equiv b$ (mod A’). L’une des deux conditions est donc superflue, à moins qu’elles ne se contrarient, c’est-à-dire que a ne soit pas congru à b modulo A’, auquel cas le problème n’a pas de solution.
xxxiv En effet $z\equiv 33$ (mod 16) équivaut à $z\equiv 17$ (mod 16), qui à son tour entraîne $z\equiv 17$ (mod 8).
xxxv Dans un passage (section II §31) que nous n’avons pas reproduit ici, Gauss propose de noter $\frac{b}{a}$ (mod m) la solution de $ax\equiv b$ (mod m). Comme ici $\alpha$ est congru à 1 modulo A et à 0 modulo BCD, on a $\alpha =kBCD=1+k'A$, donc $kBCD\equiv 1$ (mod A), d’où $k=\frac{1}{BCD}$ (mod A) et enfin $\alpha=BCD\times (\frac{1}{BCD} \mbox{(mod A)}).$.
xxxvi Dans sa traduction en français, Poullet-Delisle a omis « dans la période julienne ». Voir la note suivante.
xxxvii C’est le problème déjà posé par Euler dans le §28 du texte que nous avons donné dans le chapitre III de la présente brochure. Rappelons que l’indiction est la place de l’année dans un cycle de 15, et que l’année 1 de l’ère chrétienne a pour indiction 4 ; par suite, l’indiction a de l’année z est le reste de la division de z+3 par 15. Par des considérations du même genre, on montre que le nombre d’or b de l’année z est le reste de la division de z+1 par 19, et que la place c de l’année z dans le cycle solaire est le reste de la division de z+9 par 28. Si a, b et c sont donnés, l’année z est donc solution de $z\equiv a-3$ (mod 15), $z\equiv b-1$ (mod 19) et $z\equiv c-9$ (mod 28). Avec la formule de Gauss, on obtient $z\equiv \alpha ( a-3)+\beta ( b-1)+ \gamma (c-9)$ mod (15x19x28) ; d’après les conditions imposées à $\alpha$, $\beta$ et $\gamma$, il vient $\alpha = 6916$, $\beta = 4200$, $\gamma = 4845$. Après substitution, l’équation devient $z\equiv \alpha a + \beta b + \gamma c - 68553$ (mod 7980) qui équivaut à $z\equiv \alpha a + \beta b + \gamma c - 4713$ (mod 7980), ou à $z\equiv \alpha a + \beta b + \gamma c+ 3267$ (mod 7980). Le millésime chrétien de l’année cherchée est donc le reste de la division de $ \alpha a + \beta b + \gamma c +3267$ par 7980, tandis que son millésime julien, cycle de 7980 années qui débute par une convention compréhensible en - 4713, est le reste de la division de $ \alpha a + \beta b + \gamma c $ par 7980. C’est ce dernier résultat qui est donné par Gauss, alors qu’Euler indique les deux possibilités.
xxxviii Voir la note 12 ci-dessus.
xxxix Voir l’introduction historique et le chapitre 1.