Source: http://culturemath.ens.fr/content/le-m%C3%A9moire-deuler-de-1740-une-premi%C3%A8re-synth%C3%A8se
Timestamp: 2018-08-15 13:42:33+00:00

Document:
﻿ Le mémoire d'Euler de 1740 : une première synthèse | CultureMath
Article principal: Le théorème des restes chinois.
Article rédigé par D. Daumas, M. Guillemot, O. Keller, R. Mizrahi, M. Spiesser (IREM de Toulouse)
Editeur : Eric Vandendriessche (responsable éditorial de CultureMATH)
Paragraphes 4 à 7
Paragraphes 8 et 9
Paragraphes 10 et 11
Paragraphes 12 à 14
Paragraphes 17 à 19
Paragraphes 21à 23
Paragraphes 24 à 27
Encart : Un problème de deux restes simultanés étudié en classe
Leonhard (ou, en français, Léonard) Euler, né à Bâle le 15 avril 1707, mort à Saint-Pétersbourg le 18 septembre 1783, a passé la plus grande partie de sa vie à Berlin et à Saint-Pétersbourg. Ce mathématicien a laissé une oeuvre considérable couvrant la quasi-totalité des domaines mathématiques. Ses Lettres à une princesse d'Allemagne sur divers sujets de physique et de philosophie montrent que de grandes qualités pédagogiques accompagnaient ses talents de chercheur. Le nom d'Euler reste aujourd'hui associé à nombre de théorèmes importants. Dans le domaine de la théorie des nombres, et en particulier de l'arithmétique modulaire à laquelle se rattachent les méthodes et résultats présentés ci-après, nous pouvons mentionner le « théorème d'Euler » qui démontre en le généralisant le « petit théorème de Fermat ».
Le mémoire d'Euler, Solution du problème arithmétique : trouver un nombre qui, divisé par des nombres donnés, donne des restes donnés est spécifiquement consacré au problème qui nous occupe. En précisant qu'on le trouve presque partout, Euler confirme son caractère « baladeur » dans le champ historique des problèmes de restes (voir l'introduction du dossier Le théorème des restes chinois).
Comme Euler le souligne lui-même dans son introduction, aux paragraphes 1 et 2, il est le premier à présenter et démontrer une méthode générale de résolution de ce problème. Cette méthode qu'il met en oeuvre progressivement, pour un seul diviseur, puis pour deux, dans les paragraphes 3 à 9, s'appuie sur l'algorithme d'Euclide qui permet d'obtenir le plus grand commun diviseur de deux entiers. Avant même de discuter des cas dans lesquels le problème a des solutions ou n'en a pas, il conclut au paragraphe 10 en donnant un formulaire qui permet d'obtenir une solution particulière, à partir de laquelle il indique au paragraphe 11 comment les obtenir toutes. Ce n'est qu'ensuite, aux paragraphes 12 à 14, qu'il passe à des exemples.
Ce choix de ne faire intervenir des exemples numériques qu'après l'établissement d'un formulaire, ajouté à sa démarche inductive qui nécessite, avec les notations qui sont les siennes, une multiplication des lettres et des alphabets, rend peu lisible sa méthode et la façon dont fonctionne l'algorithme d'Euclide. Les exercices proposés à des élèves de lycée (Encart) suivent cette méthode et sont donc une bonne introduction à la démonstration d'Euler.
Le cas où le problème n'a pas de solution est traité au paragraphe 15. Le paragraphe 16 donne d'autres formules, toujours basées sur les résultats de l'algorithme d'Euclide, plus faciles à retenir mais ne simplifiant pas nécessairement les calculs. Le souci de simplification des calculs l'amène à étudier toute une série de cas particuliers, dans les paragraphes 17 à 23.
Il l'avait annoncé dans son introduction : la méthode qui permet de trouver les solutions (quand il y en a) dans le cas de deux diviseurs, permet, de proche en proche la résolution des problèmes où il y en a davantage (paragraphe 24). Suivent des exemples numérique (paragraphes 25 à 27), puis la solution d'un problème de chronologie (paragraphe 28).
Cerise sur le gâteau, il reconnaît au paragraphe 29 que les calculs de proche en proche peuvent rapidement devenir compliqués et propose une nouvelle façon de faire intervenir la recherche d'une solution particulière avec deux diviseurs dans les problèmes où il y en a davantage.
Euler a écrit son texte en latin, nous vous en proposons une traduction accompagnée de commentaires.
« Solution du problème arithmétique : trouver un nombre qui, divisé par des nombres donnés, donne des restes donnés [1] »
« 1. Dans les ouvrages courants d’arithmétique, on trouve partout des problèmes de ce genre, mais ils demandent pour les résoudre parfaitement davantage d’études et d’habileté, en vérité plus qu'il ne semble. En effet, bien que la plupart du temps soit jointe la règle, au moyen de laquelle la solution peut être obtenue, soit elle est insuffisante et ne s’applique qu’au seul cas proposé, de telle sorte que lorsque les conditions du problème changent légèrement on ne peut plus s’en servir, soit même, et c’est souvent le cas, elle est fausse.[...] Le problème suivant, où il faut trouver un nombre dont la division par $2$, $3$, $4$, $5$, $6$ laisse $1$ mais qui n’a pas de reste dans la division par $7$, se trouve presque partout sous quelque forme semblable. Nulle part on ne présente une méthode vraiment appropriée à la résolution de ce problème ; en effet la solution donnée là convient dans ce cas seulement et est obtenue plutôt par tâtonnement.
2. Si ces nombres, par lesquels le nombre cherché doit être divisé, sont petits, comme dans cet exemple, le nombre cherché est trouvé sans difficulté par tâtonnement, mais il serait très difficile de trouver de cette piètre manière une solution avec des diviseurs beaucoup plus grands. C'est pourquoi, la méthode pour résoudre les problèmes de cette sorte qui sert aussi bien aux grands diviseurs qu'aux petits n’ayant encore actuellement rien de naturel, je suis sûr de ne pas avoir travaillé en vain en cherchant une méthode qui permette sans tâtonnement de résoudre de tels problèmes même pour les plus grands diviseurs.
3. C'est pourquoi donc je souhaite présenter avec netteté mes réflexions sur ce sujet, en partant du cas le plus simple, où on donne un seul diviseur et on cherche un nombre qui, divisé par celui-ci, ait un reste donné. Ainsi on demande un nombre z qui divisé par le nombre a a laissé p comme reste. La solution de ce problème est très facile ; en effet ce sera $z = ma + p$, où m désigne un nombre quelconque ; au passage, il convient de remarquer cependant que cette solution est universelle et contient tous les nombres solutions. De plus, on comprend aussi à partir de celle-ci que si on a un nombre solution, on peut aussi trouver à partir de lui l’infinité des autres, dans la mesure où ce nombre peut être soit augmenté, soit diminué si c’est possible, d’un quelconque multiple de $a$. De plus $p$ ou si l’on veut $0a+p$ sera la plus petite solution, lui succède $a+p$, viennent ensuite $2a+p$, $3a+p$, $4a+p$ etc., tous les nombres qui constituent une progression arithmétique ayant une différence constante de $a$. »
Commentaire du § 3
Implicitement, Euler considère que $z, a, p,$ sont des entiers strictement positifs, il lui arrivera cependant d’utiliser par commodité, ou quand sa méthode $y$ conduit (il l’envisage dès le § 5), des entiers négatifs. Mais il s’appliquera toujours à donner des solutions positives et en particulier la plus petite solution positive.
« 4. Ceci présenté, suit le cas, qui est le principal et avec lequel sont résolus tous les suivants, où sont proposés deux diviseurs et les restes respectifs. En effet, aussi nombreux que soient les diviseurs proposés, la question peut toujours se ramener à ce cas où on en propose deux, je montrerai comment dans la suite. Il faut donc chercher un nombre $z$ qui, divisé par $a$ ait comme reste $p$, divisé encore par $b$ ait un reste $q$, et que a soit plus grand que $b$. Donc, comme le nombre $z$ cherché doit être tel que divisé par $a$ il ait un reste $p$, il est nécessairement contenu dans la forme $ma + p$ et nous aurons pour cette raison $z = ma + p$. Ensuite par l’autre condition, que $z$ divisé par $b$ doit avoir comme reste $q$, on aura $z = nb+ q$. C’est pourquoi, comme on a $ma + p = nb+ q$, doivent être déterminés les nombres qui substitués à $m$ et à $n$ donnent $ma + p = nb+ q$ ; ceux-ci trouvés, $ma + p$ ou $nb + q$ sera le nombre cherché $z$.
5. Par conséquent, comme $ma + p = nb+ q$, on aura $n = \frac{ma+ p - q}{b}$ et en posant $p – q = v$ on aura $n = \frac{ma+\nu}{b}$. À partir de là il convient de définir un nombre $m$ tel que l’on puisse diviser sans reste $ma+ \nu$ par $b$. Comme $a > b$, on pose [2] $a =\alpha b + c$, on aura $n = m\alpha + \frac{mc +\nu}{b}$ ; il faut donc que $mc + \nu$ soit divisible par $b$ ; mais $\alpha$ et $c$ sont des nombres connus, que l’on obtient à partir de la division de $a$ par $b$ où $\alpha$ sera le quotient et $c$ le reste. Puis on pose $\frac{mc+\nu}{b}= A$ et on aura $m = \frac{Ab - \nu}{c}$ ; c’est pourquoi il faut trouver un nombre tel que $Ab – \nu$ soit divisible par $c$. S’il advient que $\nu$ soit divisible par $c$, alors l’opération peut se terminer : en prenant en effet $A = 0$ on aura $\displaystyle{m =-\frac{\nu}{c}}$ et $\displaystyle{z = - \frac{av}{c}+p}$, cette expression, même si elle était négative est cependant propre à obtenir une infinité de nombres positifs pour $z$.
6. Mais si $\nu$ ne peut pas être divisé par $c$, afin que $\displaystyle{\frac{Ab - \nu}{c}}$ fasse un nombre entier je pose $b = \beta c+d$, où je divise $b$ par $c$ et je dis que le quotient est $\beta$ et le reste $d$. Ceci fait on aura
$\displaystyle{\frac{Ab - \nu}{c}= A \beta + \frac{Ad - \nu}{c}= m}$ et il s’en suit que $\displaystyle{\frac{Ad - \nu}{c}}$ est un nombre entier ; Soit celui-ci $= B$, cela fera $\displaystyle{A =\frac{Bc + \nu}{d}}$. Si maintenant on peut diviser $\nu$ par $d$, je pose $B = 0$ et on aura [3] $\displaystyle{A =\frac{\nu}{d}}$et $\displaystyle{m = \frac{\beta \nu}{d}}$.
Mais si $\nu$ n’est pas divisible par $d$, je pose désormais $c = \gamma d + e$ et on aura $\displaystyle{A = B \gamma + \frac{Be+\nu}{d}}$. Et aussi je pose $\displaystyle{\frac{Be+\nu}{d}= C}$, on aura ainsi $\displaystyle{B =\frac{Cd - \nu}{e}}$ .
Mais si $\displaystyle{\frac{\nu}{e}}$ n’est pas un nombre entier, je pose $d = \delta e + f$ et on aura $\displaystyle{B = C \delta + \frac{Cf - \nu}{e}}$ et je fais $\displaystyle{\frac{Cf - \nu}{e}= D}$, ce qui donne $\displaystyle{C =\frac{De+\nu}{f}}$, où on peut voir que ou bien v est divisible par $f$ ou ne l’est pas, et dans ce cas il faut recommencer l’opération comme au dessus.
7. Mais comme $a > b$ et $b > c$ et $c > d$ etc., la suite $a, b, c, d, e, f$ etc. étant poursuivie continuellement on est descendu aux plus petits nombres, de telle sorte qu’on pourra parvenir à un nombre assez petit pour être partie aliquote c’est-à-dire diviseur de $\nu$ lui-même. Mais $a, b, c, d, e, f$ sont les restes successifs de l’opération ordinaire qui permet de trouver le plus grand diviseur commun de $a$ et $b$, j’adjoins ici cette opération [4]
Commentaires des § 4, 5, 6 et 7
La méthode d’Euler consiste en des changements successifs de problème et d’inconnue, mais pour permettre au lecteur d'en suivre plus aisément les articulations, nous allons suivre sa démarche pas à pas, sur un exemple numérique, celui qu'il va traiter au § 12 avec les formules qu'il dégagera de ses calculs.
Au départ on va donc chercher un entier $z$ vérifiant $\displaystyle{\left\{\begin{array}{l l} z = 103m + 87 \\ z = 50n + 25 \end{array}\right.}$, où $m$ et $n$ sont entiers, ce qui revient à chercher deux entiers $m$ et $n$ tels que $103m + 87 = 57n + 25$, égalité équivalente à $\displaystyle{n =\frac{103m+62}{7}}$, où 62 est la différence des restes (notée $\nu$ par Euler).
Le problème se ramène alors à chercher un entier $m$ tel que $\displaystyle{\frac{103m+62}{57}}$ soit un entier, ou tel que $57$ divise $103m + 62$.
Euler opère la division euclidienne de $103$ par $57$ : $103 = 57 × 1 + 46$, écrit $\displaystyle{\frac{103m+62}{57}}$ sous la forme $\displaystyle{m +\frac{46m+62}{57}}$ et le problème est donc maintenant de chercher un entier $m$ tel que
$\displaystyle{\frac{46m+62}{57}}$ soit un entier $A$.
Mais $\displaystyle{\frac{46m+62}{57}= A }$ équivaut à $\displaystyle{m =\frac{57A - 62}{46}}$, nouvelle transformation de problème : il faut maintenant chercher un entier $A$ tel que $\displaystyle{\frac{57A - 62}{46}}$ soit un entier.
La division euclidienne de $57$ par $46$ : $57 = 46×1 + 11$ donne $\displaystyle{m = A +\frac{11A - 62}{46}}$ . Il faut
donc maintenant chercher un entier $A$ tel que $\displaystyle{\frac{11A - 62}{46}}$ soit un entier $B$.
Mais $\displaystyle{\frac{11A - 62}{46}= B}$ équivaut à $\displaystyle{A =\frac{46B+62}{11}}$ et le problème revient à chercher un entier $B$ tel que $\displaystyle{\frac{46B+62}{11}}$ soit un entier.
Comme $46 = 11×4 + 2$, nous avons $\displaystyle{A = 4B +\frac{2B+62}{11}}$ et il faut chercher un entier $B$ tel que $\displaystyle{\frac{2B+62}{11}}$ soit un entier $C$. Mais $\displaystyle{\frac{2B+62}{11}= C}$ équivaut à $\displaystyle{B =\frac{11C - 62}{2}}$ et on est amené à chercher un entier $C$ tel que $\displaystyle{\frac{11C - 62}{2}}$ soit un entier.
Comme $2$ divise $62$, il suffit de prendre $C = 0$, d’où $B = –31$, puis $A = –124$, puis $m = –155$ et enfin $z = –15 878$ qui est une solution particulière du problème.
Nous observons que les nombres $46, 11, 2$ sont les restes successifs du début de l'algorithme d'Euclide de recherche du PGCD de $103$ et $57$, mais il manque la dernière étape (qui nous aurait permis de conclure que $103$ et $57$ sont premiers entre eux) : nous nous sommes arrêtés à $2$ car il divise $62$ ($\nu$ dans le texte d'Euler).
Euler n'a pas procédé sur un exemple et a mené au contraire des calculs très généraux, avec une accumulation de lettres des alphabets latins et grecs qui rendent la lecture difficile. Mais ses calculs ne sont pas si généraux qu'ils le paraissent : si les nombres $a$ et $b$ sont premiers entre eux, le dernier reste dans l'algorithme d'Euclide est $1$ et on est assuré de trouver dans les restes successifs de l'algorithme un reste qui divise $\nu$. Mais dans le cas où $a$ et $b$ ne sont pas premiers entre eux, le dernier reste non nul peut ne pas diviser $\nu$. Euler n'ignore pas cette difficulté, qui sera l'objet du §15. Nous devons donc considérer qu'implicitement Euler se place dans le cas particulier où sa méthode débouche sur une solution particulière, réservant (par souci pédagogique ?) à plus tard la discussion sur les difficultés.
« 8. Donc cette opération, que nous avons l’habitude d’effectuer jusqu’au plus grand commun diviseur de $a$ et de $b$, doit être poursuivie jusqu’à ce que l’on parvienne à un reste qui divise $\nu$. Ceci fait, nous chercherons ensuite le nombre $m$. Si on peut déjà diviser $\nu$ par $b$, on fera $m = 0$. Si l’on peut effectuer la division de $\nu$ par $c$, on fera $A = 0$ et $\displaystyle{m =\frac{- \nu }{c}}$. Si $\nu$ est divisible par $d$, on fera $B = 0$ et $\displaystyle{A =\frac{\nu}{d}}$ et aussi $\displaystyle{m =\frac{b\nu}{cd}-\frac{\nu}{c}=\frac{\beta \nu}{d}}$ car $b = \beta c + d$. Mais on peut donner ici facilement les valeurs de $m$, on doit exprimer d’abord la valeur de $A$ à l’aide de $B$, puis la valeur de $B$ à l’aide de $C$ et ainsi de suite, c’est de là que vient cette table :
$\displaystyle{m =\frac{Ab - \nu}{c}}$,
$\displaystyle{m =\frac{Bb+ \beta \nu}{d}}$
$\displaystyle{m =\frac{Cb - \nu(1+ \beta \gamma)}{e}}$
$\displaystyle{m =\frac{Db + \nu(\delta + \beta \gamma \delta + \beta)}{f}}$
$\displaystyle{m =\frac{Eb - \nu(\delta \epsilon +\beta \gamma \delta \epsilon + \beta \epsilon + \beta \gamma +1)}{g}}$
$\displaystyle{m =\frac{Fb+ \nu(\delta \epsilon \zeta + \beta \gamma \delta \epsilon \zeta +\beta \epsilon \zeta +\beta \gamma \zeta +\zeta + \delta + \beta \gamma \delta + \beta)}{h}}$, etc.
Il faut noter à propos de ces valeurs que le signe de $\nu$ alterne ainsi – + – + – + etc. Ensuite les coefficients de $\nu$ suivent cette règle.
$\beta \gamma + 1$
$\beta \gamma \delta + \delta+\beta$
$\beta \gamma \delta \epsilon + \delta \epsilon + \beta \epsilon + \beta \gamma + 1,
chaque terme de la progression est la somme du produit du terme précédent par l’indice écrit au dessus et du terme qui le précède.
9. Donc si on peut diviser $\nu$ par $b$, on aura $m = 0$ ; si on peut diviser $\nu$ par $c$, on aura $\displaystyle{m = –\frac{\nu}{c}}$ à cause de $A = 0$ ; si on peut diviser $\nu$ par $d$, que l’on prenne $B = 0$ et on aura $\displaystyle{m =\frac{\nu}{d}\beta}$. De là apparaît la règle qui suit :
Si le nombre est entier On aura
$\displaystyle{\frac{\nu}{b}}$ $m=0$
$\displaystyle{\frac{\nu}{c}}$ $\displaystyle{m=- \frac{\nu}{c}}$
$\displaystyle{\frac{\nu}{d}}$ $\displaystyle{m= + \frac{\nu}{d} \beta}$
$\displaystyle{\frac{\nu}{e}}$ $\displaystyle{m=-\frac{\nu}{e}(\beta \gamma +1)}$
$\displaystyle{\frac{\nu}{f}}$ $\displaystyle{m=+ \frac{\nu}{f}(\beta \gamma \delta + \delta + \beta)}$
$\displaystyle{\frac{\nu}{g}}$ $\displaystyle{m=- \frac{\nu}{g}(\beta \gamma \delta \epsilon + \delta \epsilon + \beta \epsilon + \beta \gamma + 1)}$
$\displaystyle{\frac{\nu}{h}}$ $\displaystyle{m=- \frac{\nu}{h}(\beta \gamma \delta \epsilon \zeta + \delta \epsilon \zeta + \beta \epsilon \zeta + \beta \gamma \zeta + \zeta + \delta + \beta)}$
Si on remplace maintenant ces valeurs de $m$ dans l’équation $z = ma + p$, on obtient ce qui suit [5]:
Si le nombre est un entier on aura
$\displaystyle{\frac{\nu}{b}}$ $\displaystyle{z= q + \frac{b\nu}{b}1 = q + \nu}$
$\displaystyle{\frac{\nu}{c}}$ $\displaystyle{z= q - \frac{b\nu}{c} \alpha}$
$\displaystyle{\frac{\nu}{d}}$ $\displaystyle{z= q + \frac{b\nu}{d}(\alpha \beta +1)}$
$\displaystyle{\frac{\nu}{e}}$ $\displaystyle{z= q - \frac{b\nu}{e}(\alpha \beta \gamma + \beta + \gamma)}$
$\displaystyle{\frac{\nu}{f}}$ $\displaystyle{z= q + \frac{b\nu}{f}(\alpha \beta \gamma \delta + \alpha \beta + \alpha \delta + \gamma \delta + 1)}$
$\displaystyle{\frac{\nu}{g}}$ $\displaystyle{z= q - \frac{b\nu}{g}(\alpha \beta \gamma \delta \epsilon + \alpha \beta \gamma + \alpha \beta \epsilon + \alpha \delta \epsilon + \gamma \delta \epsilon + \alpha + \gamma + \epsilon)}$
Commentaire des § 8-9
Les restes successifs de l'algorithme d'Euclide sont effectivement de plus en plus petits, mais le plus petit reste non nul est le PGCD de $a$ et de $b$ qui ne divise pas nécessairement $\nu$, voir le commentaire précédent et le paragraphe 15.
Les relations entre les quantités successives $n$, $m$, $A$, $B$, $C$, … ne présentent guère de difficulté. Il en est différemment des expressions successives de m et en particulier de l’expression des coefficients successifs fonctions de $\beta$, $\gamma$, $\delta$, $\zeta$, … qui suit une relation de récurrence. Euler obtient cette relation par induction. Aujourd'hui, une démonstration se ferait par récurrence et nécessiterait un changement de notations. Nous ne ferons pas cette démonstration ici, mais il convient de remarquer qu'une démarche purement inductive peut conduire à des résultats erronés. Nous verrons au §16 qu' Euler lui-même n'y a pas échappé.
«10. Par conséquent, pour trouver le nombre $z$, qui divisé par a $a$ comme reste $p$ et divisé par $b$ a comme reste $q$, $p – q = \nu$ étant posé, nous avons la règle suivante :
On construit l’opération qui produit le plus grand diviseur commun de $a$ et de $b$ jusqu’à ce que l’on obtienne un reste qui soit un diviseur de $\nu$ et on prend le quotient de la division de $\nu$ par ce reste où l’opération s’est interrompue, que ce soit $Q$. On écrit ensuite la suite des quotients $\alpha$, $\beta$, $\gamma$, etc. qui viennent de cette division et on construit à partir d’eux une nouvelle suite [6].
$1, \alpha, \alpha\beta + 1, \alpha\beta\gamma + \alpha +\gamma, etc.$
que l’on forme à partir de ces quotients et qu’il faut poursuivre autant qu’il est possible de le faire avec cette suite. Au dessous de cette nouvelle suite on écrit les signes alternés + – + – etc. et on multiplie le dernier terme muni de son signe par Q et par le plus petit des diviseurs proposés $b$, au résultat obtenu on ajoute le reste $q$ de la division par $b$. Ceci étant fait, cette somme sera un nombre cherché [7].
11. Une fois trouvé par ce moyen un nombre $z$ qui répond à la question on obtient aussitôt l’infinité des autres solutions. En effet si la division de $z$ par a donne un reste $p$, et la division par $b$ un reste $q$, tous les nombres $ab + z$, $2ab + z$ et $mab + z$ auront la même propriété. Ce multiple $ab$ peut être ajouté ou retranché continuellement, si $a$ et $b$ sont des nombres premiers entre eux ; si a et $b$ sont des nombres composés, alors il suffit de prendre le plus petit nombre divisé à la fois par les deux [8], un multiple de celui-ci qu’il soit ajouté ou retranché à $z$ donnera des nombres solutions ; que le plus petit commun multiple soi $M$, $mM + z$ contient tous les nombres qui satisfont à la question. C’est pourquoi même si on obtient souvent par cette méthode des valeurs négatives de $z$, en leur ajoutant cependant $M$ ou un multiple on obtiendra un nombre positif.»
Commentaires des § 10-11
Au §10, Euler présente la synthèse de ses calculs sous forme d'une recette qui permet de trouver (si tout va bien) une solution particulière.
§11 : une fois trouvée une solution, les autres s’en déduisent en ajoutant ou retranchant autant de fois que l’on veut le $ppcm$ $M$ de $a$ et de $b$.
Euler démontre que $z$ étant une solution, tous les nombres de la forme $mM + z$ , où $m$ est un entier positif ou négatif sont solutions : en effet $mM$ est divisible par $a$ et par $b$.
Pour conclure que toutes les solutions sont ainsi obtenues, il faudrait encore prouver la réciproque, à savoir que si $Z$ est une solution, il existe un entier $m$ tel que $Z = mM + z$.
Cela ne présente guère de difficulté : si $Z$ est une solution, $Z$ et $z$ ont les mêmes restes respectifs dans les division respectives par $a$ et par $b$. Le nombre $Z – z$ est donc à la fois un multiple de $a$ et de $b$, donc un multiple de leur $ppcm$, $M$.
« 12. Parce qu’on illustrera cette opération par un maximum d’exemples, cherchons un nombre qui divisé par 103 a comme reste 87 et divisé par 57 a comme reste 25. On aura donc
$a = 103$, $b = 57$, $p = 87$ et $q = 25$ et alors $\nu = 62$ ; c’est pourquoi je mets en place l’opération ainsi :
Maintenant on a $–9.31 = –279$ et le nombre cherché $= 25 – 57.279$ ; ceci étant négatif, je lui ajoute $3.57.103$ à savoir $57.309$, de là on obtient $25 + 57.30 = 1735$, qui est le plus petit nombre cherché ; toutes les solutions sont vraiment contenues dans cette forme
$m.103.57 + 1735$.
13. Poursuivons et cherchons un nombre dont le reste dans la division par $41$ soit $10$, dont le reste dans la division par $29$ soit $28$. Dans cet exemple j’emploie un raccourci qui aura une grande utilité dans d’autres calculs semblables ; en effet comme le reste dans la division par $29$ est $28$, il aurait pu rester aussi dans la même division $–1$, en prenant un quotient plus grand d’une unité. Je prends donc $–1$ comme reste de la division par $29$ et on aura $a = 41$, puis $b = 29$, $p = 10$ et $q = –1$, d’où $\nu = 11$. Comme précédemment je mets en place l’opération ainsi :
On aura donc $+17.11 = 187$ et le nombre cherché $= –1 + 29.187$. En retranchant $29.4.41$ on aura $= –1 + 29.23 = 666$. Par conséquent tous les nombres qui satisfont à la question sont contenus dans cette forme $m.41.29 + 666$.
14. De là se révèle l’intérêt d’ajouter à la règle donnée plus haut ce qui consiste en ceci : après que le nombre $Q$ est multiplié par le dernier terme de la suite formée, le produit est divisé par a et le reste employé à la place de ce produit. Évidemment ce reste multiplié par le plus petit diviseur $b$ et augmenté du reste $q$ donnera le nombre cherché. Et le nombre obtenu de cette façon sera la plus petite des solutions. En outre on peut effectuer cette division pour que le reste produit soit positif, même si le dividende était négatif. Ainsi, dans le premier exemple § 12 on avait $–279$, nombre qui, divisé par $103$ en prenant un quotient [9] $= 3$, a comme reste $+30$. À partir de là la plus petite solution est $= 25 + 57.30 = 1735$. »
Commentaire des § 12-13-14
Euler montre sur deux exemples comment on met en oeuvre sa méthode, dans le second on voit comment il peut être plus simple de donner un reste négatif. Il note $Q$ le quotient de $\nu$ par le dernier reste. Dans ses deux exemples, Euler se place dans le cas où les deux diviseurs sont premiers entre eux, ce qui assure l'existence de solutions.
Pour trouver la plus petite solution (positive), on peut appliquer la méthode jusqu'au bout, puis ajouter ou retrancher le PPCM des deux diviseurs selon que la solution particulière obtenue est négative ou positive mais trop grande.
Mais on peut aussi (§14) utiliser, lorsque la valeur de n donnée par son formulaire est négative, le reste positif de la division de cette valeur de $n$ par $a$, le multiplier par $b$ et ajouter $q$ pour obtenir la plus petite solution positive.
« 15. Mais ensuite il peut se faire qu’on propose un exemple de ce genre qui n’ait pas de solution, comme si on cherche un nombre dont le reste soit $13$ dans la division par $24$, et $9$ dans la division par $15$ ; effectivement un tel nombre devrait être divisible par $3$ par l’une des conditions et le contraire par l’autre. Mais en vérité, la règle elle-même montre la même chose ; car jamais en effet on n’arrivera à un reste non nul qui divise $\nu$ à savoir $4$, comme on le voit en menant cette opération :
En vérité on ne peut trouver aucun exemple de ce genre lorsque les diviseurs $a$ et $b$ ne sont pas composés entre eux ; en effet s’ils sont premiers entre eux on peut toujours trouver des solutions. Mais si les diviseurs $a$ et $b$ étaient des nombres composés et que $\nu$ ne puisse pas être divisé par le plus grand diviseur commun de $a$ et de $b$, alors le problème amène toujours à l’absurde. Et là est le critère par lequel on peut déduire si le problème admet une solution, avant d’avoir mené l’opération. »
Commentaire du § 15
C’est là qu’Euler envisage (enfin !) les cas où il n’y a pas de solution. Il le fait à partir d’un exemple puis donne sans plus de justification la règle générale : il n’y a pas de solution lorsque le $pgcd$de $a$ et de $b$ ne divise pas $\nu$.
Lorsque le $pgcd$ de $a$ et de $b$ divise $\nu$, on est assuré qu'un reste de l'algorithme d'Euclide divise $v$, le problème a donc des solutions données par la méthode d'Euler.
Notons $r$ le $pgcd$ de $a$ et de $b$ : $a = ra'$ et $b = rb'$, où $a'$ et $b'$ sont premiers entre eux. Le problème se ramène, rappelons le, à trouver deux entiers $m$ et $n$ tels que $ma + p = nb + q$, ce qui équivaut à $nb – ma = p – q$, et à $r(nb' – ma') = \nu$. Si $r$ ne divise pas $v$, le problème est impossible.
« 16. Voilà exposée la méthode universelle, par laquelle tous les problèmes de cette sorte peuvent facilement se résoudre, mais à partir d’elle on peut former d’autres règles, dont l’usage n’est pas aussi facile mais qui a plus de simplicité en elle-même. Mais il vient celle-ci, lorsque dans le calcul précédent des valeurs de $z$ lui-même (§9) on substitue à $\alpha$, $\beta$, $\gamma$, etc. leurs valeurs à partir des équations $a = \alpha b + c$, $b = \beta c + d$, etc. En vérité si on mène l’opération qui permet de trouver le plus grand commun diviseur de $a$ et de $b$, les restes successifs $c$, $d$, $e$ etc., se font connaître, je dis que le nombre sera
$\displaystyle{z = q + ab \nu (\frac{1}{ab}-\frac{1}{bc}+\frac{1}{cd}-\frac{1}{de}+\frac{1}{ef}- etc.)}$
cette suite étant poursuivie jusqu’à ce que $v$ puisse être divisé par un facteur du dénominateur [10].
Par exemple s’il est demandé un nombre qui ait comme reste $1$ dans la division par $16$, et comme reste $7$ dans la division par $9$, on aura $a = 16$, $b = 9$, $p = 1$, $q = 7$ et $\nu = –6$.
$z = 7 – 6.9.16 (1/9.16 – 1/9.7 + 1/7.2 ) = 7 – 6 + 6.16(2 – 9)/(7.2) = 1 – 3.16 = – 47$.
Seront donc solutions tous les nombres $m.144 – 47$ ou bien $m.144 + 97$ dont le plus petit est 97.
Mais la formule générale donnée plus haut peut s’énoncer ainsi
$\displaystyle{z = q + ab \nu (\frac{1}{ab}-\frac{1}{bc}+\frac{1}{cd}-\frac{1}{de}+\frac{1}{ef}- etc.)}$ où la suite des fractions doit être poursuivie jusqu’à ce que $z$ lui-même soit un nombre entier. »
Commentaire du § 16
La première formule, jusqu’à ce que $\nu$ puisse être divisé par un facteur du dénominateur, est beaucoup plus simple à retenir que la précédente, mais une fois de plus, Euler a vraisemblablement procédé par induction et n’en donne pas la démonstration. C'est risqué …, mais ici nous avons vérifié qu'elle pouvait être menée sans trop de difficulté.
À la fin du paragraphe, Euler présente le résultat différemment : une solution est donnée par $\displaystyle{z = q + ab \nu (\frac{1}{ab}-\frac{1}{bc}+\frac{1}{cd}-\frac{1}{de}+\frac{1}{ef}- etc.)}$ en s’arrêtant lorsqu’on obtient un entier.
La formule $\displaystyle{z = p - ab \nu (\frac{1}{bc}-\frac{1}{cd}+\frac{1}{de}-\frac{1}{ef}+ ...)}$ suppose que l'on peut poursuivre
l'algorithme d'Euclide au-delà du reste $f$ ; elle est équivalente à la formule
$\displaystyle{z = q + ab \nu(\frac{1}{ab}-\frac{1}{bc}+\frac{1}{cd}-\frac{1}{de}+\frac{1}{ef}- etc.)}$
puisqu'il suffit d'effectuer $\displaystyle{ab \nu (\frac{1}{ab}=\nu=p-q}$ dans cette dernière pour obtenir celle qui
précède. Dans ce cas, nous avons vu que si $f$ divise $v$, nous avons un entier.
Mais si $f$ ne divise pas $v$, l'expression $\displaystyle{z = p - abv (\frac{1}{bc}-\frac{1}{cd}+\frac{1}{de}-\frac{1}{ef}+ ...)}$ n'est-elle jamais entière ? C'est ce que sous-entend Euler, mais l'exemple donné précédemment, au §15, prouve que c'est possible.
En effet, prenons $a = 24$ et $p = 13$, $b = 15$ et $q = 9$, d'où $\nu = 4$. Comme le montre Euler l'algorithme d'Euclide fournit les restes successifs $9$, $6$ et $3$ avec le dernier reste non nul $3$ qui ne divise pas $4$. Le problème n'a pas de solution.
Mais $\displaystyle{13-24.15.4 (\frac{1}{15.9} - \frac{1}{9.6} ) = 13 -\frac{32}{3}+\frac{80}{3}= 13+\frac{48}{3}=29}$, donne un entier, et il n'est pas solution !
Même lorsque le problème a une solution, cette solution n'est pas toujours le premier résultat entier obtenu à l'aide de la formule que donne Euler.
Prenons par exemple $a = 24$ et $p = 5$, $b = 15$ et $q = 2$, d'où $\nu = 3$. Le dernier reste $3$ divise $\nu$ et une solution est donnée par $\displaystyle{z=5-24.15.3 (\frac{1}{15.9} - \frac{1}{9.6} +\frac{1}{6.3}) = -43}$.
Pourtant $\displaystyle{5-24.15.3 (\frac{1}{15.9} - \frac{1}{9.6})}$ est un entier, $17$, et n'est pas solution.
Revenons à $\displaystyle{q + ab \nu (\frac{1}{ab}-\frac{1}{bc}+\frac{1}{cd}-\frac{1}{de}+\frac{1}{ef})}$,
c'est aussi $\displaystyle{q + \frac{b \nu}{f}(\alpha \beta \gamma \delta + \alpha \beta + \alpha \delta \gamma \delta +1)}$ qui peut être un entier même si $f$ ne divise pas $ \nu $ : il suffit que $f$ divise $\displaystyle{b \nu(\alpha \beta \gamma \delta + \alpha \beta + \alpha \delta \gamma \delta +1)}$.
La condition : "$\displaystyle{ p - ab \nu (\frac{1}{bc}-\frac{1}{cd}+\frac{1}{de}-\frac{1}{ef}+ ...)}$ est un entier" est nécessaire mais
pas suffisante pour obtenir une solution du problème.
« 17. Je considèrerai maintenant quelques cas particuliers, dans lesquels $a$ et $b$ ont une relation donnée ; et du moins pour commencer, que l’on ait $b = a – 1$ ou plutôt $a = b + 1$, et que les restes de la division des nombres cherchés par $a$ et par $b$ soient comme précédemment $p$ et $q$. On aura donc $c = 1$, d’où d’après la règle précédente $z = p – av = p – ap + aq$.
Cette expression, si $aq + p > ap$, donne le plus petit nombre solution ; mais si $aq + p < ap$, alors le plus petit nombre solution sera $a^2 – a + p – ap + aq$.
En vérité les nombres solutions sont compris dans cette formule générale $ma^2 – ma + p – ap + aq$, ou même dans celle-ci $mb^2 + mb – bp + bq + q$. Maintenant quelque soit $m$, si cette quantité est divisée par $b^2 + b$, le reste sera le plus petit nombre solution.
18. Stifel a enseigné dans le commentaire de l’art de la coss [11] de Rudolf comment trouver par ce calcul, au moyen des restes donnés de la division du nombre inconnu par $b$ et $b + 1$, le nombre inconnu lui-même. Sa règle se présente ainsi : si le reste de la division du nombre inconnu par $b + 1$ a fait $p$ et le reste du même par la division par $b$ a fait $q$, il invite à multiplier $q$ par $b + 1$ et $p$ par $b^2$ et de diviser la somme des résultats par $b^2 + b$ ; il proclame que le reste de la division est le nombre cherché. Mais cette règle découle de notre formule générale, si on pose $m = p$ ; effectivement on a alors $b^2 p + (b + 1)q$, qui divisé par$ b^2 + b$ donne comme reste le plus petit nombre cherché.
19. Cependant, en attendant, on trouve avec moins de peine le plus petit des nombres solution de la façon suivante : on multiplie le reste $q$, qui naît de la division du nombre cherché par $b$, par $b + 1$ et on additionne le résultat au produit de $b$ par ce nombre, c’est-àdire à $b^2 + b$, on retranche de ce résultat le produit de $p$, reste de la division du nombre cherché par$ b + 1$, par $b$ ; si ceci, qui reste, est devenu $< b^2 + b$, il sera lui-même le nombre cherché, sinon il est en vérité devenu $> b^2 + b$, on retranche $b^2 + b$ et le reste sera le nombre cherché. Par exemple si on cherche un nombre qui divisé par $100$ a un reste de $75$, et par $101$ de $37$, on additionne alors $10100$ au produit de $75$ par $101$, soit $7575$, pour avoir $17675$, on retranche de ceci le produit de $37$ par $100$, soit $3700$, il reste $13975$ ; à partir de cela, si on retranche $10100$, sera produit $3875$ qui est le plus petit nombre cherché. »
Commentaire des § 17-18-19
Ces trois paragraphes sont consacrés au cas particulier où $b = a – 1$ (ou $a = b + 1$). Cette catégorie de problèmes a été traitée par des auteurs antérieurs (Euler cite Stifel). Dans ce cas $a$ et $b$ sont premiers entre eux et $a = b + 1$ est l’écriture de la division euclidienne de $a$ par $b$. La règle précédente donne comme solution $\displaystyle{z = q + ab \nu(\frac{1}{ab}-\frac{1}{b})=q + \nu (1 – a)}$, d’où $z = q – b \nu = q + bq – bp$ ou $z = q + \nu – a \nu = p – a \nu = p – ap + aq$,
et toutes les solutions sont données au choix par $z \equiv p – ap + aq \pmod {ab}$, avec $ab = a(a – 1)$
ou par $z \equiv q + bq – bp \pmod {ab}$, avec $ab = (b + 1)b$.
Si $aq + p > ap$, alors $p – ap + aq > 0$ et, $q$ étant le reste d’une division par $b$, on a $q < a – 1$ et donc $p – ap + aq < p(1 – a) + a(a – 1)$, comme $ p(1 – a) < 0$, nous avons $p – ap + aq < a(a – 1) et p – ap + aq$ est la plus petite solution positive.
Sinon, en ajoutant $a(a – 1)$, on obtient $a(a – 1) + p – ap + aq = (a – p)(a – 1) + aq$, qui est positif et donne donc la plus petite solution positive.
Euler pourrait faire un raisonnement analogue pour trouver la plus petite solution positive lorsque les solutions sont données par $z \equiv q + bq – bp \pmod {b(b + 1)}$. Mais il le présente différemment car il veut au §18 faire apparaître la solution de Stifel comme un cas particulier de la sienne.
Effectivement, $b^2p = p(b^2 + b) – bp$ et donc $q(b + 1) + b^2p = p(b^2 + b) + q + bq – bp$.
Il apparaît alors plus simple d’ajouter une fois seulement $b^2 + b$ au lieu de $p$ fois, c’est la solution que donne Euler au §20, avec un exemple à la clef. Est-ce déloyal de remarquer que la formule $q + bq – bp$ conduirait directement au résultat, avec des opérations plus simples : $75 + 100×75 – 100×37 = 7575 – 3700 = 3875$ ?
« 20. Si on cherche un nombre qui divisé par $b$ a comme reste $q$, et divisé par $nb + 1$ a comme reste $p$, on aura à nouveau $c = 1$ et le nombre cherché est $z = p – a \nu = p – ap + aq = (nb +1) q – nbp$ car $a = nb + 1$. Et tous les nombres solutions sont contenus dans cette expression $mnb^2 + mb + (nb +1) q – nbp$, de laquelle en remplaçant $m$ par un nombre quelconque on trouvera le plus petit nombre solution si on divise cette expression par $nb^2 + b$ ; le reste sera effectivement le plus petit nombre solution. »
Commentaire du § 20
C’est une généralisation du problème précédent, au lieu de prendre $a = b + 1$, on prend $a = nb + 1$ ($n$ étant un entier). Il n’y a en effet guère de changement puisque $1$ est toujours le reste de la division euclidienne de a par b. Une solution est donc encore $p – ap + aq$ et toutes les solutions sont données par $z \equiv p – ap + aq \pmod {ab}$, ce qui peut s’écrire sous la forme $z \equiv (nb + 1)q–nbp \pmod {b(nb +1)}$.
Paragraphes 21 à 23
« 21. Un cas mérite d’être noté, celui où les restes $p$ et $q$, qui naissent de la division du nombre cherché par les diviseurs donnés $a$ et $b$, sont égaux entre eux, soit $p = q$. Dans ce cas on a $\nu = 0$ et par là on trouve le nombre cherché $z = p$. Par conséquent si $M$ est le plus petit nombre divisé par $a$ et $b$, tous les nombres solutions sont contenus dans la formule $mM + p$.
Évidemment cette formule est encore valable lorsqu’on a un nombre quelconque de diviseurs $a$, $b$, $c$, $d$, etc., et que le nombre cherché divisé par chacun d’eux a comme reste $p$, si $M$ désigne le plus petit nombre divisé par tous ces diviseurs. Tous les nombres solutions de problèmes de ce type sont donc rassemblés ainsi, car divisés par $M$ ils ont pour reste $p$.
22. À partir de là on peut résoudre le problème assez répandu où l’on cherche un nombre qui divisé par $2$, $3$, $4$, $5$, $6$ a comme reste $1$, et divisé par $7$ n’a aucun reste. En effet tous les nombres qui divisés par $2$, $3$, $4$, $5$, $6$ ont comme reste $1$, ont la propriété d’avoir comme reste $1$ lorsqu’ils sont divisés par $60$, qui est le plus petit nombre divisé à la fois par $2$, $3$, $4$, $5$, $6$.
Le problème se ramène donc à chercher les nombres qui divisés par $60$ ont un reste de $1$, et qui sont divisibles par $7$ ; on aura donc $a = 60$, $b = 7$, $p = 1$, $q = 0$ et $\nu = 1$. Donc, une fois effectuée l’opération
On aura $z = 0 – 119 + 420m$, et si $m = 1$, on aura $z = 301$.
23. On voit qu’il est plus difficile de résoudre le problème où l’on cherche un nombre qui, divisé par les nombres $2$, $3$, $4$, $5$, $6$, a comme restes respectifs $1$, $2$, $3$, $4$, $5$, et qui est divisible par $7$, car les restes proposés sont inégaux. Mais ce problème coïncide avec celui-ci : trouver un nombre qui, divisé par $2$, $3$, $4$, $5$, $6$ a un reste de $–1$, et par $7$ aucun. La forme $60m – 1$
satisfait alors à cette condition. Et comme on cherche un nombre qui divisé par $60$ a un reste de $–1$, et par $7$ aucun, on prend donc $a= 60$, $b = 7$, $p = –1$, $q = 0$ et $\nu = –1$ et par l’opération mise en place plus haut on a $Q = –1$, qui multiplié par $–17$ donne $+17$ ; et ceci multiplié par $b$ donne $119$, le nombre cherché. »
Commentaire des § 21-22-23
Autre cas particulier : celui où les restes sont égaux, avec dans ce cas généralisation à un nombre quelconque de diviseurs. Les solutions sont tous les nombres congrus à ce reste commun modulo le ppcm des diviseurs.
Ce cas permet de ramener le problème classique : rechercher les nombres qui divisés par $2$, $3$, $4$, $5$, $6$ ont comme reste $1$ et qui divisés par $7$ n’ont aucun reste, à la recherche d’un nombre qui divisé par le ppcm de $2$, $3$, $4$, $5$, $6$, donc par $60$, a comme reste $1$ et divisé par $7$ n’a pas de reste : deux diviseurs premiers entre eux, deux restes dont la différence est $1$, la méthode d’Euler fournit les solutions : tous les nombres de la forme $–119 + 420m$, où $m$ est un entier, et la plus petite solution positive $420 – 119 = 301$.
Même chose pour un autre problème tout aussi classique : chercher les nombres qui, divisés par $2$ ont comme reste $1$, par $3$ont comme reste $2$, par $4$ ont comme reste $3$, par $5$ un reste de $4$, par $6$ un reste de $5$ et par $7$ aucun reste. On peut en effet considérer que ces nombres ont le même reste $–1$ dans la division par $2$, $3$, $4$, $5$, $6$, et le reste $0$ dans la division
par $7$. Le problème est donc la recherche des nombres qui divisés par $60$ ont comme reste $–1$ et divisés par $7$ ont comme reste $0$. La méthode d’Euler fournit la plus petite solution positive, à savoir $119$.
« 24. Il est visible à partir de ces deux exemples, que l’on peut résoudre à l’aide des règles données plus haut tout problème de cette sorte, où on propose une quantité quelconque de diviseurs, mais auxquels correspondent seulement deux restes. On réduit effectivement constamment ce problème à celui de deux diviseurs ; quand tous les restes sont égaux, on résout le problème de la même manière que si un seul diviseur était proposé. Et si les restes sont inégaux on peut obtenir la solution en répétant à ce moment là les opérations que nous avons utilisées pour deux diviseurs. Il faut en effet s’acquitter d’abord de deux diviseurs, puis on en prend un troisième, puis un quatrième, jusqu’à ce que l’on se soit acquitté de tous. On expliquera ceci plus clairement à l’aide d’exemples.
25. Cherchons donc un nombre qui, divisé par $7$ a un reste de $6$, par $9$ un reste de $7$, par $11$ un reste de $8$ et par $17$ un reste de $1$. De ces quatre conditions prenons en deux quelconques, par exemple les deux premières, et recherchons tous les nombres qui les remplissent. On aura donc $a = 9$, $b = 7$, $p = 7$, $q = 6$ et $\nu = 1$, c’est pourquoi on met en place l’opération comme il suit
Et on aura $z = 6 + 1.4.7 = 34$.
Tous les nombres qui remplissent ces deux conditions sont contenus dans la forme $63m + 34$, ou seront regroupés comme ceux qui divisés par $63$ ont un reste de $34$.
26. Le problème se réduit donc ici à chercher un nombre qui divisé par $63$ a un reste de $34$, par $11$ a un reste de $8$ et par $17$ a un reste de $1$. De ces trois conditions prenons les deux premières et on aura $a = 63$, $b = 11$, $p = 34$, $q = 8$ et $\nu = 26$, d’où découle l’opération qui suit
D’où $z = m.63.11 + 8 – 13.17.11$.
On découvre à partir de ceci le plus petit nombre solution, on pose $m = 4$ et on aura $z = 8 + 31.11 = 349$.
Tous les nombres solutions sont donc contenus dans la forme $693m + 349$, ou encore ils auront la propriété d’avoir, divisés par $693$, un reste de $349$.
27. Le problème est donc réduit à trouver un nombre qui, divisé par $693$, a un reste de $343$ et divisé par $17$ a un reste de $1$. Je fais donc $a = 693$, $b = 17$, $p = 349$, $q = 1$ et $\nu= 348$, et je dresse l’opération suivante donnée ci-après
$z = 693.17.m + 1 + 41.87.17$.
On obtient à partir de là le plus petit nombre solution, je pose $m = –5$ et on a $z = 1 + 102.17 = 1735$, qui est le plus petit nombre qui remplit les quatre conditions prescrites. Et toutes les solutions sont contenues dans la formule $11781m + 1735$.
On comprend pleinement à partir de cet exemple comment seraient résolus tous les problèmes de ce genre. »
Commentaire des § 24-25-26-27
Euler en vient maintenant aux problèmes les plus généraux : un nombre quelconque de diviseurs et de restes. S’il y a des restes égaux on réduit le problème, comme on l’a vu dans le cas précédent, au cas où tous les restes sont différents. Quand tous les restes sont différents, on va procéder de proche en proche : les deux premiers diviseurs et les deux premiers restes vont donner (s’il y en a, mais Euler ne s’en préoccupe pas) tous les nombres qui ont un reste que l’on peut calculer par sa méthode dans la division par le ppcm des deux premiers diviseurs. Avec un troisième diviseur et le reste correspondant on obtiendra (toujours si le problème a une solution) une nouvelle condition, etc.
Vient immédiatement un exemple pour que tout soit clair, exemple dont la solution est détaillée dans les § 25-26-27. Encore une fois, dans cet exemple, Euler prend des diviseurs premiers entre eux (7, 9, 11, 17), ce qui assure l’existence de solutions.
On notera la nouveauté dans les divisions du § 27 où apparaît un reste négatif dans la division, ce qui évite une division supplémentaire.
Paragraphes 28
« 28. Apparaît ici, parce qu’on la trouve à l’aide de cette règle, la solution, que je donne ciaprès, à ce problème de chronologie assez connu où l’on demande une année après la naissance du Christ à partir des cycles solaires et lunaires donnés et avec l’indiction romaine de cette année. En effet, que le cycle solaire soit le reste qui apparaît dans la division du nombre de l’année augmenté de $9$ par $28$, que le cycle lunaire soit le reste qui apparaît dans la division du nombre de l’année augmenté d’une unité par $19$, que l’indiction romaine soit le reste qui apparaît si on divise le nombre de l’année augmenté de trois par $15$, ce qui suit donne la solution. Soit $p$ le cycle solaire, $q$ le cycle lunaire et $r$ l’indiction romaine ; que l’on multiplie $p$ par $4845$, $q$ par $4200$ et $r$ par $6916$, que l’on regroupe ces trois produits et le nombre $3267$ dans une somme et que l’on divise cela par $7980$ ; ce qui reste est le nombre de l’année demandée. Si on demande une année de la période julienne, alors on mène l’opération de la même manière, sauf qu’il faut négliger le nombre $3267$ ; c’est la règle déjà donnée ci-dessus. »
Commentaire du § 28
Euler applique sa méthode à un problème de chronologie : chercher une année à partir de données sur des cycles solaires, lunaires ou autres. Il qualifie le problème qu’il va résoudre « d’assez connu » (pour un autre exemple, voir notre chapitre 2, § 1.4). Les cycles ou périodes auxquelles Euler fait allusion ne sont guère pratiqués de nos jours, aussi quelques précisions semblent s’imposer.
Indiction romaine (ou pontificale)
L’origine est controversée : cela viendrait pour certains de la période séparant les années où sous l’empereur Auguste, on devait payer le tribut à l’empire ; selon d’autres auteurs la base serait le lustre (5 ans) et 3 lustres donneraient une période plus intéressante ; Ozanam reprend l’explication selon laquelle il s’agit de la période qui sépare l’édit de Constantin de 312, autorisant la religion chrétienne et marquant donc la fin des persécutions, du concile de Nicée qui a condamné en 328 l’hérésie d’Arius et marque donc la fin des premières hérésies. Dans tous les cas il s’agit d’une période de 15 années dont la première est l’an 313. Il en résulte que l’indiction romaine de l’an $313$ est $1$, et comme $313 \equiv 13 \pmod {15}$, l’indiction de l’an $13$ est encore $1$, et celle de l’an $1$ est $4$. Pour avoir l’indiction romaine d’une année donnée du calendrier chrétien il faut donc ajouter $3$ au millésime donné et diviser par $15$, le reste est son indiction romaine (on prendra $15$ si le reste est nul).
C’est le nombre d’années au bout desquelles une date donnée, quelle qu’elle soit, revient le même jour de la semaine. Si les années étaient toujours de $365$ jours il faudrait $7$ ans pour un tel cycle, puisque $365$ jours représentent $52$ semaines et $1$ jour. Dans le calendrier julien, il y a une année bissextile tous les quatre ans, avec un jour supplémentaire, un 29 février, et donc un décalage de $2$ jours dans la semaine au début de l’année suivante. Dans ce calendrier, ne serait-ce que pour retrouver un 29 février tombant le même jour de la semaine, il faut donc $7\times 4$, soit $28$ années pour un cycle solaire. Ce cycle est resté inchangé après la réforme grégorienne, il ne correspond donc plus, dans le calendrier grégorien, à la caractéristique première pour laquelle il faut faire éventuellement une correction pour retrouver le même jour de la semaine. Il s’agit donc d’un cycle de 28 années et le choix du début d’un de ces cycles a fait que l’an 1 s’est retrouvé la 10e année du cycle solaire courant à cette époque. Pour calculer le cycle solaire d’une année donnée, il faut donc ajouter $9$ au millésime de l’année puis diviser par $28$, le reste donne le résultat (on prendra $28$ si le reste est nul).
Cycle lunaire (ou nombre d’or)
C’est la période qui ramène la même phase de la lune aux mêmes jours du mois, c’est une période de $19$ ans, et le choix d’un cycle particulier a fait que l’an 1 de l’ère chrétienne s’est retrouvé la seconde année du cycle lunaire en cours. Pour avoir le cycle lunaire, ou le nombre d’or, d’une année donnée, il faut donc ajouter $1$ au millésime de l’année, diviser par $19$, le reste est le résultat cherché (on prendra $19$ si le reste est nul).
Période julienne
C’est la période qui comprend les trois cycles précédents : comme $15$, $19$ et $28$ sont premiers entre eux, il s’agit d’une période de $15\times19\times28$, c’est-à-dire de $7980$, années. Mais nous avons vu que la première année du calendrier chrétien est la 10ème du cycle solaire, la seconde du cycle lunaire et la 4ème de l’indiction romaine, son rang dans la période julienne, que nous noterons $z$, vérifie donc $\displaystyle{\left\{\begin{array}{l l} z \equiv 10 \pmod {28} \\ z \equiv 2 \pmod {19} \\z \equiv 4 \pmod {15} \end{array}\right.}$.
Pour résoudre ce problème, appliquons la méthode d’Euler :
$\displaystyle{\left\{\begin{array}{l l} z \equiv 10 \pmod {28} \\ z \equiv 2 \pmod {19} \end{array}\right.}$ correspond à $a = 28$, $b = 19$, $p = 10$, $q = 2$, d’où $\nu = 10 – 2 = 8$.
Algorithme d’Euclide :
$19$ $28$ $1$
$9$ $19$ $2$
donc $Q = 8$, puis
$1$ $1$ $3$
$+$ $-$ $+$
d’où les solutions données par
$z \equiv 2 + 19×8×3 \pmod {19×28}$, soit $z \equiv 458 \pmod {532}$.
$\displaystyle{\left\{\begin{array}{l l} z \equiv 458 \pmod {532} \\ z \equiv 4 \pmod {15} \end{array}\right.}$ correspond maintenant à $a = 532$, $b = 15$, $p = 458$, $q = 4$, d’où $\nu = 454$.
$15$ $532$ $35$
$7$ $15$ $2$
donc $Q = 454$, puis
$35$ $2$
$35$ $71$
d’où les solutions, données par
$z \equiv 4 + 15×454×71 \pmod {7980}$, ou $z \equiv 483 514 \pmod {7980}$.
La division euclidienne de 483 514 par 7 980 donne un reste de 4 714.
La première année de l’ère chrétienne est donc la 4 714ème de la période julienne. Si l’on connaît la période julienne d’une année, il faut donc retrancher $4 713$, ou ajouter $7 980 – 4 713$ qui est $3 267$ pour trouver le millésime de l’année.
Nous pouvons maintenant suivre le texte d’Euler : il ajoute $9$ au nombre de l’année pour l’équation liée au cycle solaire, $1$ pour celle qui est liée au cycle lunaire, $3$ pour la dernière, liée à l’indiction romaine. Le résultat est le millésime d’une année, si l’on veut son rang dans
une période julienne, il faut donc retrancher $3 267$, ce qui revient à ne pas le prendre encompte dans l’expression du résultat donné par Euler.
Les données conduisent à un système de trois équations dont l’inconnue $z$ est l’année cherchée :
$\displaystyle{\left\{\begin{array}{l l} z \equiv p - 9 \pmod {28} \\ z \equiv q - 1 \pmod {19}\\z \equiv r - 3 \pmod {15} \end{array}\right.}$, ou encore $\displaystyle{\left\{\begin{array}{l l} z \equiv 10 \pmod {28} \\ z \equiv 2 \pmod {19} \\z \equiv 4 \pmod {15} \end{array}\right.}$.
Commençons par les deux premières : $a = 28$, reste $p – 9$ ; $b = 19$, reste $q – 1$, donc $\nu = p – 9 – q + 1 = p – q – 8$.
donc $Q = p – q – 8$
Une solution est donc $z_0 = q – 1 + 19.3Q = q – 1 + 57(p – q – 8) = 57p – 56q – 457$.
Toutes les solutions sont données par $z \equiv 57p – 56q – 457 (mod 28 \times 19)$.
Il faut donc maintenant résoudre $\displaystyle{\left\{\begin{array}{l l} z \equiv -57p – 56q – 457 \pmod {28 \times 19} \\ z \equiv r - 3 \pmod {15} \end{array}\right.}$.
Nous avons maintenant $a = 532$, un reste de $57p – 56q – 457$ ; $b = 15$, un reste de $r – 3$ ; donc $\nu = 57p – 56q – r – 454$.
donc $Q = 57p – 56q – r – 454$
$1$ $35$ $71$
$\displaystyle{z_1 = r – 3 + 15\frac{57p - 56q - r - 454}{1}71= 60705p – 59640q – 1064r – 483513}$.
Les solutions sont donc données par $z \equiv 60705p – 59640q – 1064r – 483513 \pmod {15 \times 532}$.
Mais comme $15 \times 532 = 7980$, $60705 \equiv 4845 \pmod {7980}$, $– 59640 \equiv 4200 \pmod {7980}$ et enfin $7980 – 1064 = 6916$ et $– 483513 \equiv 3267 \pmod {7980}$, les solutions sont donc données par $z \equiv 4845p + 4200q + 6916r + 3267 \pmod {7980}$.
L’année demandée est la plus petite solution positive (nous sommes encore dans la première période julienne), c’est-à-dire le reste de $4845p + 4200q + 6916r + 3267$ dans la division par $7980$.
« 29. Mais la solution requiert beaucoup de travail pour de nombreux diviseurs si le problème, où le nombre de diviseurs est diminué d’une unité, est réduit sans interruption jusqu’à la fin, comme nous l’avons fait dans l’exemple précédent. Mais une voie plus facile et beaucoup plus courte se produit à partir de cette opération elle-même, qui permet de réduire aussitôt la question proposée au cas de deux diviseurs, quel que soit le nombre des diviseurs ; cette règle se présente ainsi :
Soit à trouver un nombre qui, divisé par $a$, $b$, $c$, $d$, $e$, que je pose premiers entre eux, a comme restes respectifs $p$, $q$, $r,$ $s$, $t$. Le nombre qui suit est solution de ce problème $Ap + Bq + Cr + Ds + Et + mabcde$, expression dans laquelle
$A$ est le nombre qui, divisé par $bcde$ n’a pas de reste et divisé par $a$ a comme reste l’unité ;
$B$ est le nombre qui, divisé par $acde$ n’a pas de reste et divisé par $b$ a comme reste l’unité ;
$C$ est le nombre qui, divisé par $abde$ n’a pas de reste et divisé par $c$ a comme reste l’unité ;
$D$ est le nombre qui divisé par $abce$ n’a pas de reste et divisé par $d$ a comme reste l’unité ;
et $E$ est le nombre qui, divisé par $abcd$ n’a pas de reste et divisé par $e$ a comme reste l’unité ;
ces nombres peuvent donc être trouvés par la règle donnée pour deux diviseurs. »
Commentaire du § 29
Avant de terminer, Euler nous fait part d’une ultime variante, d’une « voie plus facile et beaucoup plus courte », nous faisant regretter d’avoir suivi pas à pas les calculs précédents.
Avant de nous y pencher, nous ne pouvons qu’être fascinés par la tournure d’esprit de ce mathématicien qui après avoir trouvé et exposé une méthode générale n’a de cesse de trouver des variantes permettant de mener les calculs différemment, des formules plus faciles à retenir.
Il vient donc de nous expliquer comment, en présence d’un nombre quelconque de diviseurs, sa méthode pour deux diviseurs continue de s’appliquer en commençant par deux, puis ajoutant un troisième et ainsi de suite jusqu’à épuisement des diviseurs.
Il nous propose maintenant de calculer les nombres $A$, $B$, $C$, $D$, $E$ qui ont respectivement pour reste $1$ dans les divisions respectives par $a$, $b$, $c$, $d$, $e$ et comme reste $0$ dans les divisions respectives par le produit des diviseurs restants (il suppose donc implicitement que les diviseurs $a$, $b$, $c$, $d$, $e$ sont premiers entre eux deux à deux). Il n’est pas difficile de vérifier que le nombre $Ap + Bq + Cr + Ds + Et + mabcde$ répond à la question, à savoir a comme reste $p$ quand il est divisé par $a$, $q$ quand c’est par $b$, $r$ quand c’est par $c$, $s$ par $d$ et $t$ par $e$. Le nombre qui s’écrit $Ap + Bq + Cr + Ds + Et + mabcde$, où $m$ peut prendre toute valeur entière contient donc toutes les solutions. Nous allons voir cependant que cette méthode n’est pas valable pour
En effet, la recherche des valeurs de $A$, $B$, $C$, $D$, $E$ conduit à la résolution de systèmes de deux équations pour lesquelles la différence des restes est $\pm 1$, il faut donc, pour qu’il y ait au moins une solution que chaque diviseur soit premier avec le produit des autres (rappelons qu’il faut arrêter la division euclidienne des deux diviseurs à un reste qui divise la différence des restes), et donc que les diviseurs soient premiers entre eux deux à deux.
Cette restriction faite, on peut effectivement placer dans la colonne des avantages cette différence constante des restes. Mais on peut mettre dans celle des inconvénients le fait qu’il faut résoudre cinq systèmes de deux équations pour trouver chacune des cinq lettres, au lieu de quatre quand on résout le problème de proche en proche.
Remarquons enfin que cette dernière méthode explique les algorithmes donnés sous forme de recettes par des auteurs d'époques et d'origines très diverses permettant d'obtenir des solutions à des problèmes de restes. Euler ne fait aucune référence précise en ce sens, faut-il en voir la trace lorsqu'il évoque dans le premier paragraphe de ce texte « les ouvrages courants d'arithmétique [où] on trouve partout des problèmes de ce genre » ?
[1] Commentaire 36 de l’index d’Enestroem. Commentaires de l’Académie des Sciences de Saint-Pétersbourg 7 (1734/5), 1740, p. 46-66.
[2] Euler le dit plus loin : il effectue ce que nous appelons la division euclidienne, c’est-à-dire qu’avec $b$ strictement positif, on doit avoir $0 \leqslant c < b$. Nous trouverons cependant une exception au paragraphe 27 où apparaît un reste négatif. De plus, ici comme pour les divisions euclidiennes qui suivent, il n'envisage que le cas où les restes ne sont pas nuls. Voir §15 pour les autres cas.
[3] Euler ne donne plus que la valeur de $m$, il reviendra à la valeur correspondante d'une solution $z$ au paragraphe 9.
[4] Dans la colonne centrale, Euler a disposé de manière très esthétique, mais aussi très efficace, les résultats des divisions euclidiennes successives. On trouve dans les lignes successives, de gauche à droite, le diviseur, le dividende et le quotient, sous le dividende, le reste. Les quotients sont représentés par des lettres grecques, les restes par des lettres latines.
[5] En fait les résultats obtenus ne sont pas ceux qui sont annoncés, fonctions de $a$ et $p$ mais sont donnés en fonction de $b$ et $q$, ce qui nécessite des calculs supplémentaires mais donne un résultat qui mobilise tous les quotients successifs des divisions euclidiennes à partir du premier $\alpha$.
[6] La règle de formation de cette suite est identique à celle de la suite construite au §8.
[7] Euler calcule l'entier $n$ pour obtenir une solution particulière à partir de l'équation $z = nb + q$.
[8] C’est le nombre que nous qualifions de plus petit commun multiple. Nous traduirons dorénavant cette expression par "plus petit commun multiple".
[9] On donnerait aujourd’hui comme quotient $–3$ et $–279 = –3.103 + 30$.
[10] Par jusqu’à ce que $\nu$ puisse être divisé par un facteur du dénominateur il faut entendre un facteur parmi les deux qui composent chacun des dénominateurs successifs et qui, rappelons-le, sont les restes successifs de l'algorithme d'Euclide de recherche du $pgcd$ de $a$ et de $b$. Sous cette forme, une solution est en effet beaucoup plus facile à écrire, il suffit de connaître les restes successifs. Pour le calcul, il n’est plus nécessaire de calculer $Q$, mais surtout on évite le calcul récurrent des coefficients de $\nu$… il reste cependant à effectuer des sommes de fractions !
[11] "L’art de la coss" désigne ce que nous appelons "algèbre", la "coss" désigne chez les auteurs allemands du XVIe siècle l’inconnue. La tradition remonte à Al Khwarizmi qui a introduit "shai" (la chose), mot traduit en latin par "res" (Jean de Séville, Gérard de Crémone, Léonard de Pise…), ou en toscan par "cosa".
Retour à l'article: Le théorème des restes chinois.

References: § 3
 § 5
 § 4
 § 12
 §15
 § 8
 §16
 § 10
 §10

§11
 § 12
 § 12
 § 15
 § 16
 §15
 § 17
 §18
 §20
 § 20
 § 21
 § 24
 § 25
 § 27
 § 28
 § 1
 § 29
 §15
 §8