Recherches arithmétiques/Section seconde

Carl Friedrich Gauss

Recherches arithmétiques

Traduction par A.-C.-M. Poullet-Delisle.
Courcier, 1807 (p. 6-30).

SECTION SECONDE.

Des Congruences du premier degré.

13. Théorème. Le produit de deux nombres positifs plus petits qu’un nombre premier donné, ne peut être divisé par ce nombre premier.

Soit $p$ le nombre premier et $a<p$ et $>0\ ;$ je dis qu’on ne pourra trouver aucun nombre positif $b,$ plus petit que $p,$ qui rende

$ab\equiv 0\ {\text{(module}}\ p{\text{)}}.$

En effet, s’il peut y en avoir, supposons que ce soient les nombres $b,\ c,\ d,\,{\text{etc.}},$ tous plus petits que $p,$ ensorte qu’on ait $ab\equiv 0,\,ac\equiv 0,\,{\text{etc.}},{\pmod {p}},$ soit $b$ le plus petit de tous, desorte qu’on n’en puisse supposer un plus petit que $b,$ on aura évidemment $b>1,$ car si $b=1,$ on aurait $ab=a<p$ et partant non divisible par $p.$ Or $p$ comme nombre premier ne peut être divisé par $b,$ mais tombera entre deux multiples de $b,\ mb\ et\ (m+1)b.$ Soit $p-mb=b^{\prime },\ b^{\prime }$ sera positif et $<b.$ Or nous avons supposé $ab\equiv 0{\pmod {p}},$ on aura donc $mab\equiv 0\ ;$ et retranchant de $ap\equiv 0$ on aura $a(p-mb)=ab^{\prime }\equiv 0\ ;$ donc $b^{\prime }$ devrait être mis au rang des nombres $b,c,d,\ {\text{etc.}},$ et serait plus petit que le plus petit de tous, ce qui est contre la supposition.

14. Si aucun des deux nombres $a\ et\ b$ n’est divisible par un nombre premier $p,$ le produit $ab$ ne le sera pas non plus.

Soient $\alpha$ et $\beta$ les résidus minima positifs des nombres $a$ et $b,$ suivant le module $p,$ aucun d’eux ne sera nul par hypothèse. Or si l’on avait $ab\equiv 0,$ comme $ab\equiv \alpha \beta ,$ on aurait $\alpha \beta \equiv 0,$ ce qui serait contraire au théorème précédent.

La démonstration de ce théorème a déjà été donnée par Euclide, Él. vii, 32. Nous n’avons pas cependant voulu l’omettre, tant parceque 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 difficiles.

15. Si aucun des nombres $\mathrm {a,b,c,d} ,$ etc. n’est divisible par le nombre premier $p,$ le produit $\mathrm {abcd} ,$ etc. ne le sera pas non plus.

Suivant l’article précédent, $ab$ n’est pas divisible par $p\ ;$ donc il en est de même de $abc,$ et ainsi de suite.

16. Théorème. Un nombre composé ne peut se résoudre que d’une seule manière, en facteurs premiers.

Il est évident par les élémens, 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ère. Imaginons qu’un nombre composé $A=a^{\alpha }b^{\beta }c^{\gamma }\ {\text{etc.}},\ a,\ b,\ c,\ {\text{etc.}}$ étant des nombres premiers inégaux, soit encore décomposable d’une autre manière en facteurs premiers. Il est d’abord manifeste que dans ce second système de facteurs il ne peut entrer d’autres nombres premiers que $a,\ b,\ c,{\text{etc.}},$ puisque quelqu’autre que ce fût ne pourrait diviser $A,$ qui est composé des premiers. De même aucun des nombres premiers $a,\ b,\ c,\ {\text{etc.}}$ ne peut y manquer, car sans cela il ne diviserait pas $A$ (N^o15) ; la différence ne peut donc porter que sur les exposans. Or soit un nombre premier $p,$ qui ait dans l’un des systèmes l’exposant $m,$ et dans l’autre l’exposant $n,m$ étant $>n:$ divisons de part et d’autre par $p^{n},\ p$ restera dans l’un affecté de l’exposant $m-n,$ et disparaîtra de l’autre, donc ${\frac {A}{p^{n}}}$ pourrait se décomposer de deux manières, dans l’une desquelles $p$ n’entrerait pas, tandis qu’il resterait dans l’autre, ce qui est contre ce que nous avons démontré.

17. Si donc le nombre $A$ est le produit de $B,\ C,\ D,\ {\text{etc.}},$ il s’ensuit que les nombres $B,\ C,\ D,{\text{etc.}}$ ne peuvent avoir de facteurs premiers différens de ceux de $A,$ et que chacun de ces facteurs doit se trouver autant de fois dans les nombres $B,\ C,\ D,\ {\text{etc.}},$ pris ensemble, que dans $A.$ On déduit de là le caractère pour reconnaître si le nombre $B$ divise ou non un autre nombre $A.$ Il le divisera s’il ne contient aucun facteur premier étranger à $A,$ ni aucune puissance plus grande d’un des facteurs premiers de $A.$ Si une de ces conditions manque, $B$ ne divisera pas $A.$

À l’aide du calcul des combinaisons, on verra aisément que si $A=a^{\alpha }b^{\beta }c^{\gamma }\ {\text{etc.}},\ a,\ b,\ c,\ {\text{etc.}}$ étant comme ci-dessus des nombres premiers différens, le nombre des diviseurs différens de $A,$ en y comprenant $1$ et $A$, est $(\alpha +1)(\beta +1)(\gamma +1)\ {\text{etc.}}$

18. Si donc $A=a^{\alpha }b^{\beta }c^{\gamma }\ {\text{etc.}},$ $K=k^{\kappa }l^{\lambda }m^{\mu }\ {\text{etc.}},$ et si tous les facteurs $a,\ b,\ c,\ {\text{etc.}}$ diffèrent des facteurs $k,\ l,\ m$, etc. ; $A$ et $K$ n’auront d’autre diviseur commun que $1,$ ou bien seront premiers entr’eux.

Le plus grand commun diviseur entre plusieurs nombres donnés $A,\ B,\ C,\ {\text{etc.}}$ se trouve de la manière suivante : On décompose les nombres en facteurs premiers, et l’on prend ceux qui sont communs à tous les nombres $A,\ B,\ C,\ {\text{etc.}}$ (s’il n’y en avait pas de tels, les nombres donnés n’auraient pas de commun diviseur) ; alors on remarque quels sont les exposans de ces facteurs, dans chacun des nombres $A,B,C,\ {\text{etc.}}\ ;$ on donne à chaque facteur le plus petit des exposans qu’il a dans $A,\ B,\ C,\ {\text{etc.}},$ et l’on compose un produit des puissances qui en résultent ; ce sera le plus grand commun diviseur cherché.

Si l’on cherchait au contraire le plus petit nombre divisible à-la-fois, par les nombres $A,\ B,\ C,\ {\text{etc.}},$ on prendrait tous les nombres premiers qui diviseraient quelqu’un des nombres $A,\ B,\ C,\ {\text{etc.}},$ et on donnerait à chacun d’eux le plus haut exposant qu’il ait dans les nombres $A,\ B,\ C,\ {\text{etc.}}$ Le produit de toutes ces puissances serait le nombre cherché.

Soient, par exemple,

$A=504=2^{3}.3^{2}.7\ ;\;\;B=2880=2^{6}.3^{2}.5\ ;\;\;C=864=2^{5}.3^{3}.$

Pour trouver le plus grand diviseur commun, on a les facteurs premiers $2$ et $3,$ qui doivent être affectés des exposans $3$ et $2,$ d’où il vient $2^{3}.3^{2}=72.$ Quant au plus petit nombre divisible par $A,\ B,\ C,$ il sera $2^{6}.3^{3}.5.7=60480.$

Nous omettons les démonstrations à cause de leur facilité ; d’ailleurs on sait par les élémens comment on résout ces problèmes, quand les nombres $A,\ B,\ C,\ {\text{etc}}.$ ne sont point donnés tout décomposés en facteurs.

19. Si les nombres $\mathrm {a,\ b,\ c,\ {\text{etc}}.}$ sont premiers avec $\mathrm {k} ,$ leur produit l’est aussi.

En effet, puisqu’aucun des nombres $\mathrm {a,\ b,\ c,{\text{etc}}.}$ n’a de facteurs premiers communs avec $k,$ et que le produit de ces nombres ne peut avoir de facteurs premiers qui n’appartiennent à quelqu’un d’entr’eux, ce produit n’aura non plus aucun facteur premier commun avec $k.$

Si les nombres $\mathrm {a,\ b,\ c,\ {\text{etc}}.}$ sont premiers entr’eux, et que $\mathrm {k}$ soit divisible par chacun d’eux, il le sera aussi par leur produit.

C’est une suite des n^os 17 et 18. Soit en effet $p$ un diviseur premier quelconque du produit $abc\ etc.$ et qu’il ait l’exposant $\pi ,$ quelqu’un des nombres $a,\ b,\ c,\ etc.$ sera divisible par $p^{\pi },$ parconséquent $k,$ qui est divisible par ce nombre, le sera aussi par $p^{\pi }:$ il en sera de même des autres diviseurs du produit.

Donc, si deux nombres $\mathrm {m,\ n}$ sont congrus suivant plusieurs modules $\mathrm {a,\ b,\ c,\ {\text{etc}}.}$ premiers entr’eux, ils le seront aussi suivant leur produit. En effet, puisque $m-n$ est divisible par chacun des nombres $a,\ b,\ c,\ {\text{etc}}.,$ il le sera aussi par leur produit.

Enfin, si $\mathrm {a}$ est premier avec $\mathrm {b} ,$ et que $\mathrm {ak}$ soit divisible par $\mathrm {b,\,k}$ sera aussi divisible par $\mathrm {b} .$ En effet, puisque $ak$ est divisible par $a$ et par $b,$ il le sera par leur produit ; donc ${\frac {ak}{ab}}={\frac {k}{b}}$ sera un entier.

20. Quand $\mathrm {A=a^{\alpha }b^{\beta }c^{\gamma }\ {\text{etc}}.}$ ($\mathrm {a,\ b,\ c,\ {\text{etc}}.}$ étant des nombres premiers inégaux), est une puissance parfaite, par exemple, quand $\mathrm {A=k^{n},}$ tous les exposans $\alpha ,\ \beta ,\ \gamma ,$ etc. sont divisibles par $\mathrm {n.}$

En effet, le nombre $k$ n’est pas divisible par d’autres nombres premiers que $a,\ b,\ c,\ {\text{etc}}.\ ;$ soit $\alpha ^{\prime }$ l’exposant de $a$ dans $k^{n},$ dans $k^{n}$ ce sera $n\alpha ^{\prime }\ ;$ donc $n\alpha ^{\prime }=\alpha$ et ${\frac {\alpha }{n}}$ est un entier. On démontrera de même que ${\frac {\beta }{n}},\ {\frac {\delta }{n}}\ {\text{etc}}.$ sont des nombres entiers.

21. Quand $\mathrm {a,\ b,\ c,}$ etc. sont premiers entr’eux, et que le produit $\mathrm {abc}$ etc. est une puissance parfaite $\mathrm {k^{n},}$ chaque nombre $\mathrm {a,\ b,\ c,}$ etc. est une puissance semblable.

Soit $a=l^{\lambda }m^{\mu }p^{\pi }{\text{etc.}},\ l,\ m,\ p,\ {\text{etc.}}$ étant des nombres premiers différens, dont aucun par hypothèse ne divise les nombres $b,\ c,\ {\text{etc}}.,$ puisque le produit $abc\ {\text{etc}}.$ est divisible par $l^{\lambda }m^{\mu }p^{\pi }\ {\text{etc.}},$ on se convaincra, comme dans l’article précédent, que $\lambda ,\ \mu ,\ \pi ,\ {\text{etc}}.$ sont divisibles par $n,$ et partant que ${\sqrt[{n}]{a}}$ est entier. Il en sera de même pour $b,\ c,\ {\text{etc.}}$

Après ces notions nécessaires sur les nombres premiers, nous allons nous occuper de ce qui peut nous conduire plus directement à notre but.

22. Si les nombres $\mathrm {a}$ et $\mathrm {b}$ divisibles par $k$ sont congrus suivant le module $m$ premier avec $\mathrm {k,\ {\frac {a}{k}}\ et{\frac {b}{k}}}$ sont congrus suivant le même module.

En effet $a-b$ est évidemment divisible par $k,$ et, suivant l’hypothèse, par $m\ ;$ donc ${\frac {a-b}{k}}$ sera divisible par $m$ (19), c’est-à-dire, que ${\frac {a}{k}}\equiv {\frac {b}{k}}{\pmod {m}}.$

Mais si, toutes choses d’ailleurs égales, $m$ et $k$ ont un diviseur commun $e,$ on aura ${\frac {a}{k}}\equiv {\frac {b}{k}}{\pmod {\frac {m}{e}}}\ ;$ car ${\frac {k}{e}}\ et\ {\frac {m}{e}}$ sont premiers entr’eux ; mais $a-b$ est divisible par $k$ et par $m\ ;$ donc ${\frac {a-b}{e}}$ est divisible par ${\frac {k}{e}}$ et par ${\frac {m}{e}}$ et par conséquent par ${\frac {mk}{e^{2}}}\ ;$ c’est-à-dire que ${\frac {a-b}{k}}$ est divisible par ${\frac {m}{e}},$ ou que ${\frac {a}{k}}\equiv {\frac {b}{k}}{\pmod {\frac {m}{e}}}.$

23. Si $\mathrm {a}$ est premier avec $\mathrm {m,}$ que $\mathrm {e}$ et $\mathrm {f}$ soient des nombres incongrus suivant le module $\mathrm {m,}$ $\mathrm {ae}$ et $\mathrm {af}$ seront aussi incongrus.

Cette proposition est l’inverse de celle du n^o précédent.

Il est évident d’après cela, que si l’on multiplie $a$ par tous les nombres entiers, depuis $0$ jusqu’à $m-1,$ et qu’on cherche les restes minima des produits, suivant le module $m,$ ils seront tous inégaux ; mais le nombre de ces résidus est $m,$ et comme aucun d’eux n’est $>m,$ ils se trouveront tous dans la série depuis $0$ jusqu’à $m.$

24. L’expression $ax+b,\ a\ et\ b$ étant des nombres donnés et $x$ un nombre indéterminé ou variable, peut devenir congrue à un nombre donné quelconque, suivant le module $m,$ premier avec $a.$ Soit $c$ le nombre auquel l’expression $ax+b$ doit être congrue, et $e$ le résidu minimum positif de $c-b.$ Par le n^o précédent on trouvera nécessairement une valeur de $x<m,$ telle que le résidu minimum du produit $ax,$ suivant le module $m,$ soit $e$. Nommons $v$ cette valeur, on aura $av\equiv e\equiv c-b\ ;$ donc $av+b\equiv c{\pmod {m}}.$

25. 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 traiterons.

26. La congruence du premier degré $ax+b\equiv c$ se résout toujours par le n^o 24, quand le module est premier avec $a$ et si $v$ est la valeur convenable de $x,$ ou la racine de la congruence, il est évident que tous les nombres congrus à $v,$ suivant le module de la congruence, seront aussi des racines (n^o 9). Il n’est pas moins évident que toutes les racines doivent être congrues à $v\ :$ en effet, si $t$ est une autre racine, on aura $av+b\equiv at+b\ ;$ donc $av\equiv at,$ et partant $v\equiv t.$ On peut conclure de là que la congruence $x\equiv v{\pmod {m}},$ donne la résolution complète de la congruence $ax+b\equiv c.$

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 équivalens, 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 racine. Ainsi, par exemple, la congruence $6x+5\equiv 13{\pmod {11}},$ n’admet pas d’autres racines que celles qui sont $\equiv 5{\pmod {11}}.$ La même chose n’a pas lieu dans les congruences des degrés supérieurs, et dans celles du premier degré où le coefficient de l’inconnue n’est pas premier avec le module.

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 \pm 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,\,{\text{etc.}}\,;$ nous les représenterons pour abréger, par $A=[\alpha ],\,B=[\alpha ,\beta ],$ $C=[\alpha ,\beta ,\gamma ],$ $D=[\alpha ,\beta ,\gamma ,\delta ],\,{\text{etc.}}$^[1]. 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 ordinairement pour la recherche du plus grand diviseur commun, on formera par la division les équations

$a=\alpha b+c,\quad b=\beta c+d,\quad c=\gamma d+e,\quad {\text{etc.}}$

dans lesquelles $\alpha ,\,\beta ,\,\gamma ,\,\delta ,\,{\text{etc.}},$ sont entiers et positifs : et $b,\,c,\,d,\,{\text{etc.}}$ vont en diminuant continuellement jusqu’à ce qu’on parvienne à $m=\mu n+1\,;$ ce qui doit toujours arriver. Il en résultera $a=[n,\mu ,\dots \gamma ,\beta ,\alpha ]\,;$ $b=[n,\mu ,\dots \gamma ,\beta ]\,;$ et si l’on prend $x=[\mu ,\dots \gamma ,\beta ],$ $y=[\mu ,\dots \gamma ,\beta ,\alpha ],$ 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 impair.

28. Euler est le premier qui ait donné la résolution de ces équations (Comment. de Petersb. T. VII, p. 46). La méthode qu’il a employée 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 ${\frac {a}{b}}$ en fraction continue

${\cfrac {1}{\alpha +{\cfrac {1}{\beta +{\cfrac {1}{\gamma +\ {\text{etc.}}}}}}}}$
	$+{\cfrac {1}{\mu +{\cfrac {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 aura $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, pag. 175, et avec d’autres, dans les Additions à l’Algèbre d’Euler.

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^o 5 ). Mais puisque $\delta$ divise $a$, on a toujours $ax\equiv 0{\pmod {\delta }}$ ; donc on doit avoir $t\equiv u{\pmod {\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 entre eux, et la congruence proposée $\delta ex+\delta k\equiv 0{\pmod {\delta f}}$, équivaudra à celle-ci, $ex+k\equiv 0{\pmod {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{\pmod {f}}$ ; il suit de là que si $\nu$ est une des valeurs de $x$, la congruence $x\equiv \nu {\pmod {f}}$, donne la résolution complète de la proposée.

30. Quand le module est composé, il est toujours avantageux d’employer la méthode suivante :

Soit le module $=mn$, et la congruence proposée $ax\equiv b$. Résolvons d’abord la congruence suivant le module $m$, et supposons qu’elle soit satisfaite si $x\equiv \nu {\pmod {\frac {m}{\delta }}}$ ; $\delta$ étant le plus grand commun diviseur des nombres $m$ et $a$. Or il est évident que toute valeur de $x$ qui satisfera à la congruence $ax\equiv b{\pmod {mn}}$, satisfera aussi à la congruence $ax\equiv b{\pmod {m}}$, et que partant elle sera comprise dans la formule $\nu +{\frac {m}{\delta }}x'$, $x'$ désignant un nombre indéterminé. La réciproque de cette proposition n’est pas vraie ; $x'$ doit donc être déterminé de manière à rendre $\nu +{\frac {m}{\delta }}x'$, racine de la congruence $ax\equiv b{\pmod {mn}}$ ; on aura donc ${\frac {amx'}{\delta }}+a\nu \equiv b{\pmod {mn}}$ ou ${\frac {am}{\delta }}x'\equiv {\frac {b-a\nu }{m}}{\pmod {n}}$. Il suit de là que la résolution d’une congruence quelconque du premier degré, suivant le module $mn$, peut se ramener à celle de deux congruences, suivant les modules $m$ et $n$. On voit facilement que si $n$ est lui-même le produit de deux facteurs, la solution de la congruence, suivant le module $n$, dépend de la solution de deux congruences dont ces facteurs sont les modules ; et généralement, que la résolution d’une congruence suivant un module composé quelconque, dépend de la résolution d’autres congruences, dont les modules sont les facteurs du premier. Ces modules peuvent être choisis de manière à être des nombres premiers, si on le trouve plus commode.

Soit par exemple la congruence $19x\equiv 1{\pmod {140}}$ ; si on la résout d’abord suivant le module $2$, on aura $x\equiv 1{\pmod {2}}$ ; en faisant $x=1+2x'$, il viendra $38x'\equiv -18{\pmod {140}}$ ou $19x'\equiv -9{\pmod {70}}$. Si l’on résout celle-ci encore suivant le module $2$, on aura $x'\equiv 1{\pmod {2}}$, et en posant $x'=1+2x''$, on aura $38x''\equiv -28{\pmod {70}}$ ou $19x''\equiv -14{\pmod {35}}$. Cette congruence résolue suivant le module $5$, donne $x''\equiv 4{\pmod {5}}$ ; prenant $x''=4+5x'''$, il vient $95x'''\equiv -90{\pmod {35}}$ ou $19x'''\equiv -18{\pmod {7}}$, qui donne $x'''\equiv 4{\pmod {7}}$, d’où $x'''=2+7x^{IV}$. Or en remontant à la valeur de $x$, on trouve $x=59+140x^{IV}$ ; donc $x\equiv {59}$.

31. De la même manière que la racine de l’équation $ax=b$, s’exprime par ${\frac {b}{a}}$, nous désignerons par ${\frac {b}{a}}$ la racine d’une congruence $ax\equiv b$, en y joignant le module pour la spécifier. Ainsi ${\frac {19}{17}}{\pmod {12}}$ représente un nombre quelconque qui est $\equiv 11{\pmod {12}}$, et qui, par analogie, peut s’exprimer par ${\frac {11}{1}}{\pmod {12}}$.

Il suit de là généralement que le symbole ${\frac {b}{a}}{\pmod {c}}$ ne signifie rien de réel, ou si l’on aime mieux, est une expression imaginaire, si $a$ et $c$ ont un diviseur commun qui ne divise pas $b$ ; mais, ce cas excepté, l’expression ${\frac {b}{a}}{\pmod {c}}$ a toujours des valeurs réelles, et en a même une infinité : elles seront toutes congrues suivant $c$, si $c$ est premier avec $a$ et suivant ${\frac {c}{\delta }}$ quand $\delta$ est le plus grand commun diviseur de $a$ et de $c$.

Ces expressions se calculent presque de même que les fractions ordinaires, et voici quelques propriétés qui se déduisent facilement de ce qu’on a vu.

1^o. Si $a\equiv \alpha$, $b\equiv \beta$ suivant le module $c$, les expressions ${\frac {a}{b}}{\pmod {c}}$, ${\frac {\alpha }{\beta }}{\pmod {c}}$ sont équivalentes.

2^o. ${\frac {a\delta }{b\delta }}{\pmod {c\delta }}$ et ${\frac {a}{b}}{\pmod {c}}$ sont équivalentes.

3^o. ${\frac {ak}{bk}}{\pmod {c}}$ et ${\frac {a}{b}}{\pmod {c}}$, sont équivalentes quand $k$ est premier avec $c$.

Nous pourrions rapporter plusieurs propositions semblables ; mais comme elles n’ont aucune difficulté, et qu’elles sont inutiles pour ce qui suivra, nous passerons à autre chose.

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,\ 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{\pmod {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 forme $x\equiv v{\pmod {\frac {B}{\delta }}}\ ;$ ou ce qui revient au même, $x=v+{\frac {KB}{\delta }},\ K$ étant un nombre entier indéterminé ; donc la formule $a+Av+{\frac {KAB}{\delta }}$ renferme toutes les valeurs de $z,$ ce qui revient à $z\equiv a+AV{\pmod {\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 marche, après avoir réuni les deux premières conditions en une seule. Ainsi soit $\epsilon$ le plus grand commun diviseur des nombres ${\frac {AB}{\delta }}$ et $\ C,$ on obtiendra la congruence ${\frac {AB}{\delta }}x+a+Av\equiv c{\pmod {C}},$ qui sera résolue par une congruence de la forme $x\equiv w{\pmod {\frac {C}{\delta }}},$ et le problème le sera par la congruence $z\equiv {\frac {AB}{\delta }}w+a+Av{\pmod {\frac {ABC}{\delta \epsilon }}}\ ;$ on procéderait de même , quel que fût le nombre des modules. Il convient d’observer que ${\frac {AB}{\delta }}\ et{\frac {ABC}{\delta \epsilon }},$ 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, quel que 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{\pmod {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 eux.

Soient par exemple $A=504,$ $B=35,$ $C=16,$ $a=17,$ $b=-4,$ $c=33\ ;$ ici les deux conditions que $z\equiv 17{\pmod {504}},$ et $\equiv -4{\pmod {35}},$ se réduisent à une seule $z\equiv 521{\pmod {2520}},$ qui, jointe à la troisième $z\equiv 33{\pmod {16}},$ donnera enfin $z\equiv 3041{\pmod {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’eux ; et dans ce cas il est évident que toutes les congruences $z\equiv a{\pmod {A}}$, $z\equiv b{\pmod {B}}$ etc. se ramèneront à une seule $z\equiv r{\pmod {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{\pmod {R}}$ peut être décomposée en plusieurs $z\equiv r{\pmod {A}}$, $z\equiv r{\pmod {B}}$ ; $z\equiv r{\pmod {C}}$ etc. si $A,\ B,\ C,$ etc, sont les différens facteurs premiers entr’eux qui composent $R$. Cette observation nous donne non-seulement le moyen 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{\pmod {A}}$, $z\equiv b{\pmod {B}}$, $z\equiv c{\pmod {C}}$, etc. On résoudra tous les modules en facteurs premiers entr’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ède fait voir que l’on peut, aux conditions données, substituer les suivantes $z\equiv a{\pmod {A'}}$, $z\equiv a{\pmod {A''}}$, $z\equiv a{\pmod {A'''}}$, etc. ; $z\equiv b{\pmod {B'}}$, $z\equiv b{\pmod {B''}}$, etc., etc. Or, à moins que tous les nombres $A,\ B,\ C$, etc, ne fussent premiers entr’eux ; par exemple, si $A$ n’est pas premier avec $B$, il est évident que tous les diviseurs premiers ne peuvent être différens 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 soumultiple parmi les diviseurs $B'$, $B''$, etc. Soit d’abord $A'=B'$, les conditions $z\equiv a{\pmod {A'}}$, $z\equiv b{\pmod {B'}}$, doivent être identiques, et l’on doit avoir $z\equiv b{\pmod {A'}}$ ou ${\pmod {B'}}$ ; ainsi l’une ou l’autre de ces deux conditions peut être rejetée ; mais si l’on n’a pas $a\equiv b{\pmod {A'}}$, le problème est impossible. Soit ensuite $B'$ un multiple de $A'$, la condition $z\equiv a{\pmod {A'}}$ doit être contenue dans celle-ci, $z\equiv b{\pmod {B'}}$, ou bien celle-ci, $z\equiv b{\pmod {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{\pmod {A'}}$, peut être rejetée, si elle ne contrarie pas l’autre, auquel cas le problème serait

impossible. Quand toutes les conditions superflues sont ainsi rejetées, il est évident que tous les modules qui restent sont premiers entr’eux ; on est sûr alors de la possibilité du problême, et on peut procéder d’après la manière enseignée plus haut.

35. Si nous supposons comme au n^o 32 $z\equiv 17{\pmod {504}}$, $\equiv -4{\pmod {35}}$, $\equiv 33{\pmod {16}}$ ; ces conditions peuvent se décomposer en celles qui suivent : $z\equiv 17{\pmod {8}}$, $\equiv 17{\pmod {9}}$, $\equiv 17{\pmod {7}}$ ; $z\equiv {-4}{\pmod {5}}$, $\equiv -4{\pmod {7}}$ ; $z\equiv 33{\pmod {16}}$. De ces conditions on peut rejeter $z\equiv 17{\pmod {8}}$ et $z\equiv 17{\pmod {7}}$, car la première est renfermée dans la condition $z\equiv 33{\pmod {16}}$, et la seconde est équivalente à $z\equiv -4{\pmod {7}}$ : il reste ainsi

$z\equiv$	$\left.{\begin{matrix}\ \\\ \\\ \\\ \\\ \end{matrix}}\right\{$		$17$	${\pmod {\;\,9}}$	$\left.{\begin{matrix}\ \\\ \\\ \\\ \\\ \end{matrix}}\right\}$	d’où l’on tire $z\equiv 3041{\pmod {5040}}.$
		$-$	$4$	${\pmod {\;\,5}}$
		$-$	$4$	${\pmod {\;\,7}}$
			$33$	${\pmod {16}}$

Au reste il est clair qu’il sera 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{\pmod {A'}}$, $z\equiv a{\pmod {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 des conditions $z\equiv -4{\pmod {5}}$, $z\equiv -4{\pmod {7}}$ ; on tire sur-le-champ la condition $z\equiv -4{\pmod {35}}$, d’où elles dérivent ; il s’ensuit 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 entr’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 quelconque de l’expression ${\frac {1}{BCD\ {\text{etc.}}}}{\pmod {A}}$, multipliée par $BCD$ etc. (n^o 52) ; mais il vaut mieux prendre la plus petite de ces valeurs. Soit de même $\beta \equiv 1{\pmod {B}}$, et $\equiv 0{\pmod {ACD\ {\text{etc.}}}}$ ; $\gamma \equiv 1{\pmod {C}}$, et $\equiv 0{\pmod {ABD\,{\text{etc.}}}}$. Alors si l’on cherche un nombre $z$ qui soit congru aux nombres $a,\,b,\,c,\,{\text{etc.}}$ suivant les modules $A,\,B,\,C,\,{\text{etc.}}$ respectivement, on pourra poser $z\equiv \alpha a+\beta b+\gamma c+{\text{etc.}}{\pmod {ABCD\ {\text{etc.}}}}$ ; en effet on a évidemment $\alpha a\equiv a{\pmod {A}},$ et les autres termes sont $\equiv 0{\pmod {A}}\,;$ donc $z\equiv a{\pmod {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,\,{\text{etc.}}$ sont les mêmes ; car alors on trouve pour $\alpha ,\,\beta ,\,{\text{etc.}}$ des valeurs constantes. Ceci s’applique au problème de chronologie dans lequel on cherche le quantième de l’année pour laquelle l’indiction, le nombre d’or et le cycle solaire sont donnés. Ici $A=15,\,B=19,\,C=28\,;$ ainsi comme la valeur de l’expression $\ {\frac {1}{19.28}}{\pmod {15}}$, ou $\ {\frac {1}{532}}{\pmod {15}}$ est $13,$ on aura $\alpha =6916\,;$ on trouvera de même $\beta =4200,\,\gamma =4845$. Donc le nombre cherché sera le résidu minimum du nombre $6916a+4200b+4845c,\,a$ représentant l’indiction, $b$ le nombre d’or, et $c$ le cycle solaire.

37. Nous n’en dirons pas davantage sur les congruences du premier degré, qui ne renferment qu’une seule inconnue ; il nous reste à parler des congruences qui renferment plusieurs inconnues ; mais, comme il faudrait donner trop d’extension à ce chapitre, si nous voulions exposer chaque chose en toute rigueur, et notre projet n’étant pas d’épuiser ici la matière, mais seulement de présenter ce qui est le plus digne d’attention ; nous bornerons notre recherche à un petit nombre d’observations, réservant l’exposition complète pour une autre occasion.

1^o. De même que dans les équations, on voit qu’il faut avoir autant de congruences qu’il y a d’inconnues à déterminer.

2^o. Soient donc proposées les congruences

$ax$	$+$	$by$	$+$	$cz$	$\equiv f$	${\pmod {m}}$………	(A)
$a'x$	$+$	$b'y$	$+$	$c'z$	$\equiv f'$	……………………	(A' )
$a''x$	$+$	$b''y$	$+$	$c''z$	$\equiv f''$	……………………	(A" )
etc.

en même nombre que les inconnues $x,\,y,\,z,\,{\text{etc.}}$

On déterminera les nombres $\xi ,\,\xi ',\,\xi '',\,{\text{etc.}}$ de manière qu’on ait :

$b\xi +b'\xi '+b'\xi ''+\,{\text{etc.}}=0,\qquad c\xi +c'\xi '+b''\xi ''+\,{\text{etc.}}=0,\,{\text{etc.}}$

et que ces nombres soient entiers et n’aient aucun diviseur commun à tous, ce qui est toujours possible par la théorie des équations linéaires.

On déterminera de même $\nu ,\,\nu ',\,\nu '',\,{\text{etc.}},\,\zeta ,\,\zeta ',\,\zeta '',\,{\text{etc.}},\,{\text{etc.}},$ de manière qu’on ait

$a\nu +a'\nu '+a''\nu ''$	$+\,{\text{etc.}}=0\qquad$	$c\nu +c'\nu '+c''\nu ''$	$+\,{\text{etc.}}=0,\,{\text{etc.}}$
$a\zeta +a'\zeta '+a''\zeta ''$	$+\,{\text{etc.}}=0\qquad$	$b\zeta +b'\zeta '+b''\zeta ''$	$+\,{\text{etc.}}=0,\,{\text{etc.}}$
etc.

3^o. Il est évident que si l’on multiplie les congruences $A$, $A'$, $A''$, etc., d’abord par $\xi$, $\xi '$, $\xi ''$, etc. ensuite par $\nu$, $\nu '$, $\nu '',\,{\text{etc.}}\,{\text{etc.}}$, etc. etc., et qu’on les ajoute, on obtiendra les congruences suivantes :

$(a\xi +a'\xi '+a''\xi ''\ +\,{\text{etc.}})$	$x$	$\equiv$	$f\xi +f'\xi '+f''\xi ''$	$+\,{\text{etc.}}$
$(b\nu +b'\nu '+b''\nu '\ +\,{\text{etc.}})$	$y$	$\equiv$	$f\nu +f'\nu '+f''\nu ''$	$+\,{\text{etc.}}$
$(c\zeta +c'\zeta '+b''\zeta ''\ +\,{\text{etc.}})$	$z$	$\equiv$	$f\zeta +f'\zeta '+f''\zeta ''$	$+\,{\text{etc.}}$
etc.

que, pour abréger, nous représenterons ainsi :

$x.\sum (a\xi )\equiv \sum (f\xi ),\quad y.\sum (b\nu )\equiv \sum (f\nu ),\quad z.\sum (c\zeta )\equiv \sum (f\zeta ),\,{\text{etc.}}$

4^o. Il y a plusieurs cas à distinguer en premier lieu quand les coefficiens des inconnues, c’est-à-dire quand $\sum (a\xi )$, $\sum (b\nu ),\,{\text{etc.}}$ sont premiers avec le module des congruences, ces congruences peuvent être résolues par les méthodes déjà exposées, et la solution complète du problème s’obtient par des congruences de cette forme $x\equiv p{\pmod {m}}$, $y\equiv q{\pmod {m}}$, etc.^[2]. Si l’on propose, par exemple, les congruences

$x+3y+z\equiv 1,\quad 4x+y+5z\equiv 7,\quad 2x+2y+z\equiv 3{\pmod {8}},$

on trouvera $\xi =9,\,\xi '=1,\,\xi ''=-14\,;$ donc

$\sum \left(a\xi \right)=-15,\qquad \sum \left(f\xi \right)=-26\,;$

donc $-15x\equiv -26,$ et partant $x\equiv -2,{\pmod {8}}$. De la même manière on trouvera $15y\equiv -4,\,15z\equiv 1$, et de là, $y\equiv 4,\,z\equiv 7{\pmod {8}}.$

5^o. Si tous les coefficiens $\textstyle \sum \left(a\xi \right),\,\sum \left(b\nu \right),\,{\text{etc.}}$ ne sont pas premiers avec le module, soient $\alpha ,\,\beta ,\,\gamma ,\,{\text{etc.}}$ les plus grands diviseurs communs de $m$ et de $\textstyle \sum \left(a\xi \right)$, $\textstyle \sum \left(b\nu \right)$, $\textstyle \sum \left(c\zeta \right),\,{\text{etc.}}$ respectivement ; et il est évident que le problème est impossible, si $\alpha ,\,\beta ,\,\gamma ,\,{\text{etc.}}$ ne divisent aussi $\textstyle \sum \left(f\xi \right),\,\sum \left(f\nu \right),\,\sum \left(f\zeta \right),\,{\text{etc.}}$ respectivement ; mais quand ces conditions auront lieu, le problème sera résolu complètement par des congruences telles que

$x\equiv p{\pmod {\frac {m}{\alpha }}},\quad y\equiv q{\pmod {\frac {m}{\beta }}},\quad z\equiv r{\pmod {\frac {m}{\gamma }}},\quad {\text{etc.}}$

ou si l’on aime mieux, on aura $\alpha$ valeurs différentes pour $x,$ savoir : $p,\ p+{\frac {m}{\alpha }},\dots \ p+{\frac {(\alpha -1)m}{\alpha }},\beta$ valeurs pour $y,$ $\gamma$ valeurs pour $z,\,{\text{etc.}}$ qui satisferont aux congruences. Toutes les solutions de la question, s’il y en a quelques-unes, devront se trouver parmi celles que nous venons d’indiquer ; mais il n’est pas permis de renverser la conclusion ; car souvent toutes les combinaisons des $\alpha$ valeurs de $x,$ avec celles de $y$ et celles de $z,$ etc. ne satisfont pas au problème, mais seulement quelques-unes dont la liaison s’exprime au moyen d’une ou de plusieurs équations de condition. Au reste comme la solution complète de ce problème n’est pas nécessaire pour la suite, nous ne nous étendrons pas davantage ici sur ce sujet, et nous nous contenterons d’en donner une idée par un exemple.

Soient proposées les congruences

$3x+5y+z\equiv 4,\quad 2x+3y+2z\equiv 7,\quad 5x+y+3z\equiv 6{\pmod {12}},$

on aura ici

$\xi$	$=$	$1,$	$\qquad \xi '$	$=$	$-2,$	$\qquad \xi ''$	$=$	$1\,;$
$\nu$	$=$	$1,$	$\qquad \nu '$	$=$	$1,$	$\qquad \nu ''$	$=$	$-1\,;$
$\zeta$	$=$	$-13,$	$\qquad \zeta '$	$=$	$22,$	$\qquad \zeta ''$	$=$	$-1\,;$

d’où $4x\equiv -4,\,7y\equiv 5,\,28z\equiv 96\,;$ d’où l’on tire quatre valeurs de $x,$ savoir, $x\equiv 2,\,5,\,8,\,11\,;$ une seule de $y,\,y\equiv 11\,;$ quatre de $z,$ savoir, $z\equiv 0,\,3,\,6,\,9{\pmod {12}}$. Or pour découvrir quelles combinaisons des valeurs de $x$ et de $z$ on peut admettre, substituons à la place de $x,\,y,\,z,\,2+3t,\,11,\,3u,$ ce qui change les congruences proposées en $57+9t+3u\equiv 0,\,30+6t+6u\equiv 0$ et $15+15t+9u\equiv 0{\pmod {12}}$, congruences qui reviennent à $19t+3t+u\equiv 0$, $10+2t+2u\equiv 0,$ $5+5t+3u\equiv 0{\pmod {4}}$. Chacune d’elles sera évidemment satisfaite, si $u\equiv t+1{\pmod {4}}$. Concluons de là que les valeurs de $x\equiv 2$, $5$, $8$ et $11$ que l’on obtient en faisant successivement $t=0$, $1$, $2$, $3$, doivent être combinées respectivement avec les valeurs $3$, $6$, $9$, $0$ de $z$ ; desorte qu’il y a quatre solutions.

$x\equiv 2,\ 5,\ 8,\ 11\dots ,\;y\equiv 11,\ 11,\ 11,\ 11\dots ,\;z\equiv 3,\ 6,\ 9,\ 0{\pmod {12}}.$

À ces recherches qui remplissent la tâche que nous nous étions proposée dans ce chapitre, nous joindrons quelques propositions qui se rapportent aux mêmes principes, et qui seront d’un fréquent usage par la suite.

38. Problème. Trouver combien il y a de nombres plus petits qu’un nombre donné $\mathrm {A}$, et premiers avec lui ? Désignons, pour abréger, le nombre cherché par le caractère $\varphi$ placé avant le nombre donné ; le nombre cherché sera $\varphi A$.

1^o. Quand $A$ est premier, il est évident que tous les nombres, depuis $1$ jusqu’à $A-1$, sont premiers avec $A$, et partant, dans ce cas, on $\varphi A=A-1.$

2^o. Quand $A$ est une puissance d’un nombre premier $p$, $p^{m}$ par exemple ; tous les nombres divisibles par $p$ ne seront pas premiers avec $A$, les autres le seront ; c’est pourquoi de $p^{m}-1$ nombres, il faut rejeter ceux-ci :

$p,\,2p,\,3p\dots \,(p^{m-1}-1)p.$

Il en restera donc $p^{m}-1-(p^{m-1}-1)=p^{m}-p^{m-1}=p^{m-1}(p-1)$ donc …

$\varphi p^{m}=p^{m-1}.(p-1).$

3^o. Les autres cas se ramènent facilement à ceux-ci, au moyen de la proposition suivante : Si on décompose $\mathrm {A}$ en facteurs $\mathrm {M}$, $\mathrm {N}$, $\mathrm {P}$, etc. premiers entr’eux, on aura $\varphi \mathrm {A} =\varphi \mathrm {M} .\varphi \mathrm {N} .\varphi \mathrm {P} .$, etc., qui se démontre ainsi qu’il suit. Soient $m$, $m'$, $m''$, etc. les nombres premiers avec $M$ et plus petits que lui. Soient de même $n$, $n'$, $n''$, etc., $p$, $p'$, $p''$, etc., etc. les nombres premiers avec $N$, $P$, etc. $p$, $p'$, $p''$, etc., etc. les nombres premiers avec $M$, $N$, $P$, etc. respectivement, et plus petits qu’eux ; il est évident que tous les nombres premiers avec $A$ le seront aussi avec les facteurs $M$, $N$, $P$, etc., et réciproquement (n^o 19), et que tous les nombres qui seront congrus à l’un quelconque des nombres $m$, $m'$ etc. suivant le module $M$, seront premiers avec $M$ ; de même pour $N$, $P$, etc. La question est donc réduite à déterminer combien il y a de nombres au dessous de $A$, qui soient congrus à quelqu’un des nombres $m$, $m'$, etc. suivant le module $M$, à quelqu’un des nombres $n$, $n'$, etc. suivant le module $N$, etc. ; mais (n^o 52) tous les nombres qui ont des résidus donnés suivant chacun des modules $M,$ $N,$ $P,$ etc. doivent être congrus suivant leur produit $A$, et parconséquent il ne peut y en avoir qu’un seul congru à des résidus donnés suivant les modules $M$, $N$, $P$, etc., et qui soit plus petit que $A$. Ainsi le nombre cherché sera égal au nombre des combinaisons des différens nombres $m$, $m'$, $m''$, etc. avec les nombres $n$, $n'$, $n''$, etc. et les nombres $p$, $p'$, $p''$, etc., etc. Or par la théorie des combinaisons, ce nombre est $\varphi (M).\varphi (N).\varphi (P)$. etc.

4^o. On voit facilement comment on peut appliquer cette proposition au cas dont il s’agit. On décomposera $A$ en facteurs premiers ; c’est-à-dire, qu’on le réduira à la forme $a^{\alpha }b^{\beta }c^{\gamma }$ etc., $a$, $b$, $c$, etc. étant des nombres premiers différens. Alors on aura $\varphi A=\varphi a^{\alpha }\varphi b^{\beta }\varphi c^{\gamma }.\ {\text{etc}}.\ =a^{\alpha -1}(a-1).b^{\beta -1}(b-1).c^{\gamma -1}(c-1)\ {\text{etc}}.,$ qui peut se mettre sous la forme plus élégante

$\varphi A=A.{\frac {a-1}{a}}.{\frac {b-1}{b}}.{\frac {c-1}{c}}$ etc.

Exemple : Soit $A=60=2^{2}.3.5,$ on aura $\varphi A=60.{\frac {1}{2}}.{\frac {2}{3}}.{\frac {4}{5}}=16.$ Ces nombres premiers avec 60, sont : $1,$ $7$, $11$, $13$, $17$, $19$, $23$, $29$, $31$, $37$, $41$, $43$, $47$, $49$, $53$, $59$.

La première solution de ce problème se trouve dans le Mémoire d’Euler, intitulé : Theoremata arithmetica novâ methodo demonstrata. (Comment. nov. acc. Petrop. VIII, pag, 74). La démonstration en a été donnée encore dans une autre dissertation intitulée : Speculationes circa quasdam insignes proprietates numerorum. (Acta Petrop, VIII, p. 17).

39. Si la signification du caractère $\varphi$ est déterminée de manière à ce que $\varphi A$ exprime combien il y a de nombres premiers avec $A,$ et non plus grands que $A\ ;$ alors on n’aura plus $\varphi 1=0,$ mais $=1\ ;$ mais dans tous les autres cas il n’y aura rien de changé. En adoptant cette définition, nous aurons le théorème suivant :

Si $\mathrm {a,\,a',\,a'',}$ etc. sont tous les diviseurs de $\mathrm {A}$, l’unité et $\mathrm {A}$ y compris, on aura $\varphi a+\varphi a'+\varphi a''+{\text{etc}}.=\mathrm {A}$. Par exemple, si $A=30$, on aura

	$\varphi 1+$	$\varphi 2+$	$\varphi 3+$	$\varphi 5+$	$\varphi 6+$	$\varphi 10+$	$\varphi 15+$	$\varphi 30$
$=$	$1\;+$	$1\;+$	$2\;+$	$4\;+$	$2\;+$	$4\;\;+$	$8\;\;+$	$8\;\;$
$=$	$30$.

Démonstration. Si l’on multiplie tous les nombres premiers avec $a$ et non plus grands que lui par ${\frac {A}{a}}$, de même tous les nombres $A$ premiers avec $a'$ par ${\frac {A}{a'}}$, etc. ; on aura $\varphi a+\varphi a'+\varphi a''+{\text{etc}}.$ nombres tous non plus grands que $A$ ; mais

1^o. Tous ces nombres seront inégaux ; car il est évident que ceux qui proviennent du même diviseur de $A$ sont tous inégaux. D’ailleurs s’il en résultait deux égaux provenant de diviseurs différens $M$ et $N$, et de nombres $\mu$ et $\nu$ qui leur soient respectivement premiers ; c’est-à-dire, si l’on avait ${\frac {A}{M}}\mu ={\frac {A}{N}}$, ou bien $N\mu =M\nu$ ; en posant $M>N$, (ce qui est permis ), il s’ensuivrait, puisque $M$ est premier avec $\mu$ et qu’il divise $N\mu$ qu’il devrait aussi diviser $N$, ce qui est absurde.

2^o. Entre ces nombres on trouvera tous ceux qui composent la suite $1,2,3...A$. En effet, soit $t$ un nombre quelconque qui ne surpasse pas $A$, et le plus grand commun diviseur entre $A$ et $t$, ${\frac {A}{\delta }}$ sera le diviseur de $A$ avec lequel ${\frac {t}{\delta }}$ sera premier. Donc le nombre $t$ se trouvera parmi ceux qui ont été produits par le diviseur ${\frac {A}{\delta }}$ ;

3^o. Il suit de là que le nombre total en est $A$ ; donc $\varphi a+\varphi a'+\varphi a''+{\text{etc}}.$

40. Si $\mu$ est le plus grand diviseur commun des nombres $\mathrm {A} ,$ $\mathrm {B} ,$ $\mathrm {C} ,$ $\mathrm {D} ,$ etc. on peut toujours déterminer les nombres $\mathrm {a,\ b,\ c,\ d,}$ etc. de manière qu’on ait $\mathrm {aA+bB+cC+}$ etc. $=\mu .$

Considérons d’abord deux nombres $A$ et $B$ seulement, et soit $\lambda$ leur plus grand diviseur commun. Alors la congruence $Ax\equiv \lambda {\pmod {B}}$ sera résoluble (n^o 30). Soit la racine $\equiv \alpha$, et que l’on fasse ${\frac {\lambda -A\alpha }{B}}=\beta$, on aura $\alpha A+\beta B=\lambda$,

S’il y a un troisième nombre $C$, soit $\lambda '$ le plus grand diviseur commun de $\lambda$ et de $C$, il sera en même temps celui des trois nombres $A$, $B$, $C$,^[3]. On déterminera les nombres $k$ et $\gamma$ de manière qu’on ait $k\lambda +\gamma C=\lambda '$, et l’on aura $k\alpha A\lambda +k\beta B+\gamma C=\lambda '$.

S’il y a un quatrième nombre $D$ soit $\lambda ''$ le plus grand diviseur commun de $\lambda '$ et de $D$, il sera en même temps celui des quatre nombres $A$, $B$, $C$, $D$. On fera $k'\lambda '+\delta D=\lambda ''$, et partant on aura $k'k\alpha A+k'k\beta B+k''\gamma +\delta D=\lambda ''$.

On procéderait de la même manière s’il y avait plus de nombres.

Si les nombres $A$, $B$, $C$, etc. n’avaient pas de diviseur commun, il est clair qu’on aurait $aA+bB+cC+\ {\text{etc}}.\ =\ 1$.

41. Si $\mathrm {p}$ est un nombre premier, et qu’on ait $\mathrm {p}$ choses parmi lesquelles il peut s’en trouver un certain nombre d’égales entr’elles, pourvu que toutes ne le soient pas : le nombre des permutations de ces choses sera divisible par $\mathrm {p} .$

Par exemple, cinq choses $A,\ A,\ A,\ B,\ B$ peuvent se disposer de dix manières différentes.

La démonstration de ce théorème se déduit facilement de la théorie connue des permutations. En effet, supposons que, parmi ces $p$ choses, il y en ait $a$ égales à $A$, $b$ égales à $B$, $c$ égales à $C$, etc., desorte qu’on ait $a+b+c+\ {\text{etc}}.=p$, les nombres $a$, $b$, $c$ etc. pouvant aussi désigner l’unité. Le nombre des permutations sera ${\frac {1.2.3...p}{1.2...a.1.2...b.1.2...c.\ {\text{etc}}.}}$ ; or le numérateur est évidemment divisible par le dénominateur, puisque le nombre des permutations est entier ; mais il est divisible par $p$, tandis que le dénominateur, qui est composé de facteurs plus petits que $p$, n’est pas divisible par $p$ (n^o 15) ; donc le nombre des permutations sera divisible par $p$.

Nous espérons cependant que la démonstration suivante ne déplaira pas à quelques lecteurs.

Lorsque dans deux permutations l’ordre des choses ne différera qu’en ce que celle qui tient la première place dans l’une, en occupe une différente dans l’autre, mais que du reste toutes les autres choses, à partir de celle-là, suivent le même ordre dans chacune des permutations, de manière que la dernière de l’une se trouve placée immédiatement avant la première dans l’autre ; nous les appellerons permutations semblables^[4]. Ainsi $ABCDE$ et $DEABC$, $ABAAB$ et $ABABA$ seront semblables.

Or comme chaque permutation est composée de $p$ choses, il est clair qu’on pourra en trouver $p-1$, semblables à une quelconque d’entre elles, si l’on met successivement à la seconde, à la troisième place, etc., la chose qui occupait la première ; donc si aucunes de ces permutations semblables ne sont identiques, il est évident que le nombre total des permutations sera égal à $p$ fois le nombre des permutations dissemblables, et conséquemment sera divisible par $p$. Supposons que deux permutations semblables $PQ\dots TV\dots YZ$, $V\dots YZPQ\dots T$ puissent être identiques, et que $P$ qui occupe la première place dans la première, occupe la $n+1$^ème dans la seconde : on aura dans la dernière série le $n+1$^ème terme égal au 1^er, le $n+2$^ème égal au 2^ème, etc., d’où résulte que le $2n+1$^ème est encore égal au premier, et parconséquent le $3n+1$^ème, et généralement le $kn+m$^ème égal au $m$^ème (où quand $kn+m>p,$ il faut imaginer qu’on reprenne toujours par le commencement, la série $V\dots YZPQ\dots T,$ à moins qu’on ne retranche de le multiple de $p$ qui en approche le plus en moins). Cela posé, si on détermine $k$ de manière que $kn\equiv 1{\pmod {p}}$, ce qui peut toujours se faire, puisque $p$ est premier, il suivra de là que généralement le $m$^ème terme serait égal au $m+1$^ème, c’est-à-dire qu’un terme quelconque serait égal au suivant, ou que tous les termes seraient égaux entre eux, ce qui est contre l’hypothèse.

42. Si les coefficiens $\mathrm {a,\,b,\,c,}$ etc., $\mathrm {n} \,;$ $\mathrm {a',\,b',\,c',}$ etc., $\mathrm {n'} \,;$ de deux fonctions de la forme

$x^{m}+$	$ax^{m-1}+$	$bx^{m-2}$	$+\dots \ +n$	$\dots \ (P)$,
$x^{m'}+$	$ax^{m'-1}+$	$b'x^{m'-2}$	$+\dots \ +n'$	$\dots \ (Q)$

sont tous rationnels, mais non pas tous entiers, et que le produit soit $\mathrm {x^{m+m'}+Ax^{m+m'-1}+\dots \ +N,}$ les coefficiens $\mathrm {A} ,$ $\mathrm {B} ,$ $\mathrm {C} ,$ etc., $\mathrm {N}$ ne peuvent être tous entiers.

En effet, réduisons à leur plus simple expression toutes les fractions qui peuvent se trouver parmi les nombres $a,$ $b,$ $c,$ etc. ; $a',$ $b',$ $c',$ etc. ; et choisissons un nombre premier $p$ qui divise un ou plusieurs des dénominateurs de ces fractions. Supposons que $p$ divise le dénominateur d’un coefficient fractionnaire de $(P),$ il est clair qu’en divisant $(Q)$ par $p,$ on aura aussi dans ${\frac {(Q)}{p}}$ au moins un coefficient fractionnaire dont le dénominateur sera divisible par $p$ (le coefficient du premier terme ${\frac {1}{p}},$ par exemple). Or on voit facilement qu’on pourra toujours trouver un terme fractionnaire de $(P)$ dont le dénominateur contienne $p$ élevé à une puissance plus grande que dans tous les termes qui précèdent, et non moindre que dans tous ceux qui suivent. Soit ce terme $Gx^{g}$ et $t$ l’exposant de $p$ dans le dénominateur. On trouvera un terme pareil dans ${\frac {(Q)}{p}},$ que nous supposerons être $\Gamma x^{\gamma },$ l’exposant de $p$ dans le dénominateur, étant $\tau \,;$ on aura au moins $t+\tau =2.$ Cela posé, le terme $x^{g+\gamma }$ du produit de $(P)$ par $(Q)$ aura un coefficient fractionnaire dont le dénominateur renfermera $p$ élevé à la puissance $t+\tau -1.$

En effet, soient $'Gx^{g+1},$ $''Gx^{g+2},$ etc., les termes qui précèdent $Gx^{g}$ dans $(P)\,;$ $G'x^{g-1},$ $G''x^{g-2},$ etc. ceux qui le suivent. Soient de même dans ${\frac {(Q)}{p}},$ $'\Gamma x^{\gamma +1},$ $''\Gamma x^{\gamma +2},$ etc., les termes qui précèdent $\Gamma x^{\gamma }\,;$ et $\Gamma 'x^{\gamma -1},$ $\Gamma ''x^{\gamma -2},$ etc. ceux qui le suivent. Dans le produit de $(P)$ par ${\frac {(Q)}{p}}$ le coefficient de $x^{g+\gamma }$ sera évidemment

$G\Gamma$	$+'G\Gamma '+$	$''G\Gamma ''$	$+\ {\text{etc}}.$
	$+'\Gamma G'+$	$''\Gamma G''$	$+\ {\text{etc}}.$

Le premier terme $G\Gamma$ sera une fraction qui, réduite à sa plus simple expression, aura son dénominateur divisible par $p^{t+\tau }.$ Si les autres termes sont fractionnaires, leurs dénominateurs ne contiendront que des puissances de $p$ moindres que $p^{t+\tau },$ puisque chacun d’eux est le produit de deux facteurs, dont l’un ne contient qu’une puissance de $p$ plus petite que $p^{t}$ ou $p^{\tau },$ et l’autre une puissance non plus grande que $p^{t}$ ou $p^{\tau }.$ Ainsi $GT$ sera de la forme ${\frac {e}{fp^{t+\tau }}}$, et le reste de la forme ${\frac {e'}{f'p^{t+\tau -\delta }}},$ $e,$ $f$ et $f'$ étant indépendans de $p.$ Donc la somme sera ${\frac {ef'+e'fp^{\delta }}{ff'p^{t+\tau }}}$ dont le numérateur n’est pas divisible par $p,$ et dont parconséquent le dénominateur ne peut être ramené à renfermer une puissance de $p$ moindre que $p^{t+\tau }.$ Donc le coefficient du terme dans le produit de $(P)$ par $(Q)$ sera ${\frac {ef'+e'fp^{\delta }}{ff'p^{t+\tau -1}}},$ c’est-à-dire une fraction dont le dénominateur renferme la puissance $t+\tau -1$ de $p.$

43. La congruence du degré $m$

$Ax^{m}+Bx^{m-1}+Cx^{m-2}+\ {\text{etc}}.\ +Mx+N\equiv 0,$

dont le module est un nombre premier $\mathrm {p}$ qui ne divise pas $\mathrm {A}$, ne peut pas être résolue de plus de $\mathrm {m}$ manières, ou n’a pas plus de $\mathrm {m}$ racines incongrues suivant $\mathrm {p} .$

En effet, supposons, s’il est possible, qu’on donne des congruences de différens degrés $m,\ n$, etc., qui aient plus de $m,\ n$, etc. racines ; soit $m$ le plus petit des nombres $m$, $n$, etc. ; desorte que toutes les congruences d’un degré inférieur à $m$ s’accordent avec notre proposition. Comme elle est démontrée plus haut (n^o 26) pour le premier degré, $m$ sera $=2$ ou $>2$. Admettons donc que la congruence……
$Ax^{m}+Bx^{m-1}+Cx^{m-2}+\ {\text{etc.}}\ +Mx+N\equiv 0,$ ait au moins $m+1$ racines $x\equiv \alpha ,$ $x\equiv \beta ,$ $x\equiv \gamma ,$ etc. ; et supposons que tous les nombres $\alpha ,$ $\beta ,$ $\gamma ,$ etc., sont positifs et plus petits que $p$, ce qui est permis, et en outre que $\alpha$ soit le plus petit. Faisons dans la congruence proposée $x\equiv y+\alpha ,$ elle deviendra

$Ay^{m}+B'y^{m-1}+\,{\text{etc.}}\ +M'y+N'\equiv 0.$

Or il est évident que cette congruence sera satisfaite si $y\equiv 0$ ou $\equiv \beta -\alpha ,$ ou $\equiv \gamma -\alpha ,$ etc., racines toutes différentes, et en nombre $m+1\,;$ mais de ce que $y\equiv 0$ est une racine, il suit que $N'$ est divisible par $p,$ on aura donc

$y(Ay^{m-1}+B'y^{m-2}+\ {\text{etc.}}\ +M')\equiv 0{\pmod {p}},$

congruence qui sera satisfaite, en y substituant à la place de $y$ une quelconque des $m$ valeurs : $\beta -\alpha ,$ $\gamma -\alpha ,$ etc., qui sont toutes $>0$ et $<p.$ Parconséquent, dans ces differens cas, $Ay^{m-1}+B'y^{m-2}+\,{\text{etc.}}\ +M'$ deviendra $\equiv 0$ (n^o 22) ; c’est-à-dire que la congruence $Ay^{m-1}+B'y^{m-2}+\ {\text{etc.}}\ +M'\equiv 0$ qui du degré $m-1,$ aurait $m$ racines ; ce qui ne s’accorde pas avec notre théorème, quoique nous ayons supposé que toutes les congruences d’un degré inférieur à $m,$ y satisfissent ; ce qui est absurde.

44. Nous avons supposé ici que le module $p$ ne divisait pas le coefficient du premier terme ; mais le théorème n’est pas restreint à ce seul cas. En effet, si le premier coefficient, et même quelques-uns des suivans étaient divisibles par $p,$ on pourrait les négliger sans erreur, la congruence serait réduite à un degré inférieur, et le coefficient du premier terme ne serait plus divisible par $p,$ à moins que tous les coefficiens ne le fussent, auquel cas la congruence deviendrait identique, et l’inconnue serait absolument indéterminée.

Lagrange est le premier qui ait proposé et démontré ce théorème (Mémoires de l’Académie de Berlin, ann. 1768, p. 192). Il se trouve aussi dans la Dissertation de Legendre, intitulée Recherches d’Analyse indéterminée (Histoire de l’Académie de Paris, 1785, p. 466). Euler dans les Nouveaux Commentaires Académiques. Pétersb. XVIII, p. 93, a démontré que la congruence $x^{n}-1\equiv 0$ ne pouvait pas avoir plus de $n$ racines. Quoique ce ne soit qu’un cas particulier, la méthode dont ce célèbre Géomètre s’est servi, peut s’appliquer facilement à toutes les congruences. Il s’était déjà occupé d’un cas plus particulier (Comment. Ac. Pétersb. V. p. 6 ) ; mais cette méthode ne peut s’employer généralement. Dans la section VIII, nous démontrerons ce théorème d’une autre manière ; mais quoique toutes ces méthodes puissent paraître différentes au premier aspect, les gens instruits qui voudront les comparer, s’assureront aisément qu’elles partent toutes du même principe. Au reste ce théorème ne devant être considéré ici que comme un lemme, et l’exposition complète n’appartenant pas à cette section, nous ne nous arrêterons pas à parler des modules composés.

---

1. 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 :

   1^o. $[\alpha ,\beta ,\gamma ,\dots \lambda ,\mu ].[\beta ,\gamma ,\ldots \lambda ]-[\alpha ,\beta ,\gamma ,\ldots \lambda ].[\beta ,\gamma ,\dots \lambda ,\mu ]=\pm 1\,;$ où l’on prendra le signe supérieur, lorsque le nombre des quantités $\alpha$ sera pair, et le signe inférieur dans le cas contraire.

   2^o. On peut renverser l’ordre des quantités $\alpha ,\beta ,\gamma ,\,{\text{etc.}}$, etc. ; de sorte que $[\alpha ,\beta ,\gamma ,\ldots \lambda ,\mu ]=[\mu ,\lambda ,\ldots \gamma ,\beta ,\alpha ]$

   Nous supprimons ici les démonstrations qui n’offrent aucune difficulté.

2. Il faut observer que cette conclusion manque de démonstration que nous supprimons ici ; car il ne suit rigoureusement rien autre chose de notre analyse, si ce n’est que les congruences proposées ne peuvent être résolues par d’autres valeurs de $x$, $y$, $z,\,{\text{etc.}}$ mais non pas que celles-ci satisfassent ; il serait même possible qu’il n’y eût aucune solution. Le même paralogisme se présente dans la solution des équations linéaires.
3. En effet si $\lambda '$ n’était pas le plus grand commun diviseur de $A$, $B$, $C$, il y en aurait un plus grand que $\lambda '$. Or celui-ci divisera $A$ et $B$, partant il divisera $\alpha A+\beta B$ ou $\lambda$, ce qui est absurde.
4. Si l’on écrivait en cercle les permutations semblables, de manière que la dernière chose touchât à la première, il n’y aurait aucune différence entre elles, parcequ’aucune place ne peut s’appeler la première ni la dernière