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 le nombre premier et et je dis qu’on ne pourra
trouver aucun nombre positif plus petit que qui rende
En effet, s’il peut y en avoir, supposons que ce soient les nombres
tous plus petits que ensorte qu’on ait soit le plus petit de tous, desorte
qu’on n’en puisse supposer un plus petit que on aura évidemment car si on aurait et partant non divisible par Or comme nombre premier ne peut être divisé par
mais tombera entre deux multiples de Soit
sera positif et Or nous avons supposé on aura donc et retranchant de
on aura donc devrait être mis au rang
des nombres et serait plus petit que le plus petit de
tous, ce qui est contre la supposition.
14. Si aucun des deux nombres n’est divisible par un nombre premier le produit ne le sera pas non plus.
Soient et les résidus minima positifs des nombres et suivant le module aucun d’eux ne sera nul par hypothèse. Or si
l’on avait comme on aurait 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 etc. n’est divisible par le nombre premier le produit etc. ne le sera pas non plus.
Suivant l’article précédent, n’est pas divisible par donc il en est de même de 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é é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 puisque quelqu’autre que ce fût ne pourrait diviser qui est composé des premiers. De même aucun des nombres
premiers ne peut y manquer, car sans cela il ne diviserait pas (No15) ; la différence ne peut donc porter que sur les
exposans. Or soit un nombre premier qui ait dans l’un des systèmes l’exposant et dans l’autre l’exposant étant divisons de part et d’autre par restera dans l’un affecté de l’exposant et disparaîtra de l’autre, donc pourrait se décomposer de deux manières, dans l’une desquelles 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 est le produit de il s’ensuit que les nombres ne peuvent avoir de facteurs
premiers différens de ceux de et que chacun de ces facteurs doit
se trouver autant de fois dans les nombres pris ensemble, que dans On déduit de là le caractère pour reconnaître
si le nombre divise ou non un autre nombre Il le divisera s’il
ne contient aucun facteur premier étranger à ni aucune puissance plus grande d’un des facteurs premiers de Si une de ces
conditions manque, ne divisera pas
À l’aide du calcul des combinaisons, on verra aisément que si étant comme ci-dessus des nombres premiers différens, le nombre des diviseurs différens de en
y comprenant et , est
18. Si donc et si tous
les facteurs diffèrent des facteurs , etc. ; et
n’auront d’autre diviseur commun que ou bien seront premiers
entr’eux.
Le plus grand commun diviseur entre plusieurs nombres donnés
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 (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 on donne à chaque facteur le plus petit des exposans qu’il a dans 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 on prendrait tous les nombres
premiers qui diviseraient quelqu’un des nombres
et on donnerait à chacun d’eux le plus haut exposant qu’il ait dans
les nombres Le produit de toutes ces puissances
serait le nombre cherché.
Soient, par exemple,
Pour trouver le plus grand diviseur commun, on a les facteurs
premiers et qui doivent être affectés des exposans et d’où il
vient Quant au plus petit nombre divisible par
il sera
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 ne sont point donnés tout décomposés en facteurs.
19. Si les nombres sont premiers avec leur produit l’est aussi.
En effet, puisqu’aucun des nombres n’a de facteurs premiers communs avec 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
Si les nombres sont premiers entr’eux, et que soit divisible par chacun d’eux, il le sera aussi par leur produit.
C’est une suite des nos 17 et 18. Soit en effet un diviseur premier
quelconque du produit et qu’il ait l’exposant quelqu’un
des nombres sera divisible par parconséquent
qui est divisible par ce nombre, le sera aussi par il en sera de
même des autres diviseurs du produit.
Donc, si deux nombres sont congrus suivant plusieurs modules premiers entr’eux, ils le seront aussi suivant leur produit. En effet, puisque est divisible par chacun des nombres il le sera aussi par leur produit.
Enfin, si est premier avec et que soit divisible par sera aussi divisible par En effet, puisque est divisible par
et par il le sera par leur produit ; donc sera un entier.
20. Quand ( étant des nombres premiers inégaux), est une puissance parfaite, par exemple, quand tous les exposans etc. sont divisibles par
En effet, le nombre n’est pas divisible par d’autres nombres
premiers que soit l’exposant de dans dans ce
sera donc et est un entier. On démontrera de même
que sont des nombres entiers.
21. Quand etc. sont premiers entr’eux, et que le produit
etc. est une puissance parfaite chaque nombre etc. est une puissance semblable.
Soit étant des nombres premiers différens, dont aucun par hypothèse ne divise les nombres
puisque le produit est divisible par on se convaincra, comme dans l’article précédent, que sont
divisibles par et partant que est entier. Il en sera de même
pour
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 et divisibles par sont congrus suivant le module premier avec sont congrus suivant le même module.
En effet est évidemment divisible par et, suivant l’hypothèse, par donc sera divisible par (19), c’est-à-dire,
que
Mais si, toutes choses d’ailleurs égales, et ont un diviseur commun on aura car sont premiers
entr’eux ; mais est divisible par et par donc est divisible par et par et par conséquent par c’est-à-dire que est divisible par ou que
23. Si est premier avec que et soient des nombres incongrus suivant le module et seront aussi incongrus.
Cette proposition est l’inverse de celle du no précédent.
Il est évident d’après cela, que si l’on multiplie par tous les
nombres entiers, depuis jusqu’à et qu’on cherche les restes
minima des produits, suivant le module ils seront tous inégaux ;
mais le nombre de ces résidus est et comme aucun d’eux
n’est ils se trouveront tous dans la série depuis jusqu’à
24. L’expression étant des nombres donnés et
un nombre indéterminé ou variable, peut devenir congrue à un
nombre donné quelconque, suivant le module premier avec
Soit le nombre auquel l’expression doit être congrue, et
le résidu minimum positif de Par le no précédent on trouvera
nécessairement une valeur de telle que le résidu minimum
du produit suivant le module soit . Nommons cette valeur, on aura donc
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é se résout toujours par le no 24, quand le module est premier avec et si est
la valeur convenable de ou la racine de la congruence, il est
évident que tous les nombres congrus à suivant le module de la
congruence, seront aussi des racines (no 9). Il n’est pas moins évident que toutes les racines doivent être congrues à en effet, si
est une autre racine, on aura donc et partant On peut conclure de là que la congruence
donne la résolution complète de la congruence
Comme les résolutions de la congruence par les valeurs de congrues à 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 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
n’admet pas d’autres racines que celles qui
sont 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
dans laquelle le module est supposé premier avec dépend de celle-ci, En effet, si satisfait à celle-ci, satisfera à la première ; mais en désignant le module par la congruence équivaut à l’équation indéterminée dont la solution est connue ; aussi nous nous
contenterons de donner ici l’algorithme du calcul.
Si les quantités etc. dépendent de etc. de manière qu’on ait nous les représenterons pour abréger, par [1]. Soit maintenant l’équation où sont positifs. Supposons, ce qui est
permis, que n’est pas Alors en opérant comme on le fait ordinairement pour la recherche du plus grand diviseur commun, on formera par la division les équations
dans lesquelles sont entiers et positifs : et vont en diminuant continuellement jusqu’à ce qu’on
parvienne à ce qui doit toujours arriver. Il en
résultera et si l’on
prend on aura
quand le nombre des lettres est pair, et
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
et de , 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 en fraction continue
|
|
|
|
et qu’après avoir effacé sa dernière partie , on la ramène à une fraction ordinaire , on aura 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 , dans laquelle le module n’est pas
premier avec , se ramène facilement au cas précédent. Soit le
module et le plus grand diviseur commun entre et ; il est
clair d’abord que toute valeur de qui satisfera à la congruence,
suivant le module , y satisfera aussi suivant le module (no 5 ).
Mais puisque divise , on a toujours ; donc on
doit avoir , ou divisible par , pour que la
congruence soit résoluble.
Posons donc , , ; et seront premiers entre eux, et la congruence proposée ,
équivaudra à celle-ci, ; c’est-à-dire, que toute
valeur de qui satisfera à la seconde, satisfera aussi à la première,
et vice versa. En effet, sera divisible par , quand le
sera par et réciproquement. Mais nous avons résolu la congruence
; il suit de là que si est une des valeurs de ,
la congruence , 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 , et la congruence proposée . Résolvons d’abord la congruence suivant le module , et supposons qu’elle soit satisfaite si ; étant le plus grand
commun diviseur des nombres et . Or il est évident que toute
valeur de qui satisfera à la congruence , satisfera aussi à la congruence , et que partant elle sera
comprise dans la formule , désignant un nombre indéterminé. La réciproque de cette proposition n’est pas vraie ; doit donc
être déterminé de manière à rendre , racine de la congruence
; on aura donc
ou . Il suit de là que la résolution d’une congruence quelconque du premier degré, suivant le module , peut
se ramener à celle de deux congruences, suivant les modules et .
On voit facilement que si est lui-même le produit de deux
facteurs, la solution de la congruence, suivant le module , 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 ; si on la résout d’abord suivant le module , on aura ; en faisant
, il viendra ou . Si l’on résout celle-ci encore suivant le module , on
aura , et en posant , on aura ou . Cette congruence résolue suivant
le module , donne ; prenant , il vient
ou , qui donne , d’où . Or en remontant à la valeur de ,
on trouve ; donc .
31. De la même manière que la racine de l’équation ,
s’exprime par , nous désignerons par la racine d’une congruence
, en y joignant le module pour la spécifier. Ainsi
représente un nombre quelconque qui est , et qui,
par analogie, peut s’exprimer par .
Il suit de là généralement que le symbole ne signifie
rien de réel, ou si l’on aime mieux, est une expression imaginaire,
si et ont un diviseur commun qui ne divise pas ; mais, ce cas
excepté, l’expression a toujours des valeurs réelles, et
en a même une infinité : elles seront toutes congrues suivant , si
est premier avec et suivant quand est le plus grand commun
diviseur de et de .
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.
1o. Si , suivant le module , les expressions ,
sont équivalentes.
2o. et sont équivalentes.
3o. et , sont équivalentes quand est
premier avec .
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, suivant lesquels le nombre
cherché doit être congru aux nombres et Toutes les valeurs
de sont nécessairement renfermées dans la formule où
est indéterminé, mais tel que de sorte que
si est le plus grand diviseur commun de et de la résolution
complète de cette congruence prendra cette forme
ou ce qui revient au même, étant un nombre entier
indéterminé ; donc la formule renferme toutes les valeurs de ce qui revient à S’il y avait
un troisième module suivant lequel le nombre cherché dût
être on suivrait la même marche, après avoir réuni les deux
premières conditions en une seule. Ainsi soit le plus grand commun diviseur des nombres et on obtiendra la congruence
qui sera résolue par une congruence de la forme et le problème le sera par la congruence
on procéderait de même , quel que
fût le nombre des modules. Il convient d’observer que
sont respectivement les plus petits nombres divisibles à la fois par
ou par et l’on en conclut facilement, quel que
soit le nombre des modules que si l’on représente
par le plus petit nombre divisible par chacun d’eux, on aura la
résolution complète, en prenant 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 sont premiers entre eux.
Soient par exemple ici les deux conditions que
et se réduisent à une seule qui,
jointe à la troisième donnera enfin
33. Quand tous les nombres 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 ,
etc. se ramèneront à une seule qui
leur équivaudra, étant le produit des nombres etc. :
il suit de là réciproquement qu’une seule condition
peut être décomposée en plusieurs , ;
etc. si etc, sont les différens facteurs
premiers entr’eux qui composent . 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 ,
, , etc. On résoudra tous les modules en
facteurs premiers entr’eux ; en etc. ; en etc. ;
de manière que les nombres , etc., , etc. soient premiers ou puissances de nombres premiers ; si l’un des nombres
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 , , , etc. ; , , etc., etc.
Or, à moins que tous les nombres , etc, ne fussent premiers
entr’eux ; par exemple, si n’est pas premier avec , il est évident que tous les diviseurs premiers ne peuvent être différens dans
et dans , mais qu’il doit y avoir quelqu’un des diviseurs , , etc.,
qui trouve son égal, son multiple, ou son soumultiple parmi les
diviseurs , , etc. Soit d’abord , les conditions , , doivent être identiques, et l’on
doit avoir ou ; ainsi l’une ou l’autre
de ces deux conditions peut être rejetée ; mais si l’on n’a pas , le problème est impossible. Soit ensuite un multiple de , la condition doit être contenue dans
celle-ci, , ou bien celle-ci, ,
qui se déduit de la dernière, doit être équivalente à la première ;
d’où il suit que la condition , 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 no 32 , , ; ces conditions peuvent se décomposer en celles qui suivent : , ,
; , ; .
De ces conditions on peut rejeter et ,
car la première est renfermée dans la condition ,
et la seconde est équivalente à : il reste ainsi
|
|
|
|
|
|
d’où l’on tire
|
|
|
|
|
|
|
|
|
|
|
|
|
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 , , etc.
celle qui se composera des conditions restantes sera , suivant
le module formé par le produit de tous les modules qui restent.
Ainsi dans notre exemple des conditions ,
; on tire sur-le-champ la condition , 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 , , , etc. sont premiers entr’eux,
il est préférable le plus souvent d’employer la méthode suivante.
On déterminera un nombre congru à l’unité suivant , et à
suivant le produit des autres modules ; c’est-à-dire, que sera une
valeur quelconque de l’expression , multipliée
par etc. (no 52) ; mais il vaut mieux prendre la plus petite
de ces valeurs. Soit de même , et ;
, et . Alors si l’on cherche
un nombre qui soit congru aux nombres suivant les
modules respectivement, on pourra poser ; en effet on a évidemment et les autres termes sont
donc 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 sont les mêmes ; car alors on trouve pour
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
ainsi comme la valeur de l’expression
, ou est on aura on
trouvera de même . Donc le nombre cherché
sera le résidu minimum du nombre représentant l’indiction, le nombre d’or, et 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.
1o. De même que dans les équations, on voit qu’il faut avoir
autant de congruences qu’il y a d’inconnues à déterminer.
2o. Soient donc proposées les congruences
|
|
|
|
|
|
……… |
(A) |
|
|
|
|
|
|
|
…………………… |
(A' ) |
|
|
|
|
|
|
|
…………………… |
(A" ) |
|
etc.
|
en même nombre que les inconnues
On déterminera les nombres de manière qu’on ait :
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 de
manière qu’on ait
|
|
|
|
|
|
|
|
etc. |
|
|
|
3o. Il est évident que si l’on multiplie les congruences , , , etc., d’abord par , , , etc. ensuite par , , , etc. etc.,
et qu’on les ajoute, on obtiendra les congruences suivantes :
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
etc. |
|
|
|
que, pour abréger, nous représenterons ainsi :
4o. Il y a plusieurs cas à distinguer en premier lieu quand les
coefficiens des inconnues, c’est-à-dire quand ,
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
, , etc.[2]. Si l’on propose, par
exemple, les congruences
on trouvera donc
donc et partant . De la même manière on trouvera , et de là,
5o. Si tous les coefficiens
ne sont pas premiers avec le module, soient
les plus grands diviseurs communs de
et de
,
,
respectivement ; et il est évident que le problème est impossible, si
ne divisent aussi
respectivement ; mais quand ces conditions auront lieu, le problème sera résolu complètement par des congruences telles que
ou si l’on aime mieux,
on aura valeurs différentes pour savoir : valeurs pour valeurs pour 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 valeurs de avec celles
de et celles de 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
on aura ici
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
d’où d’où l’on tire quatre valeurs de savoir,
une seule de quatre de savoir,
. Or pour découvrir quelles combinaisons
des valeurs de et de on peut admettre, substituons à la place de
ce qui change les congruences proposées
en et ,
congruences qui reviennent à , . Chacune d’elles sera évidemment satisfaite, si . Concluons de là que les valeurs de , , et que l’on obtient en faisant successivement
, , , , doivent être combinées respectivement avec les
valeurs , , , de ; desorte qu’il y a quatre solutions.
À 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é , et premiers avec lui ? Désignons, pour abréger, le nombre cherché par le caractère placé avant le nombre donné ; le nombre cherché sera .
1o. Quand est premier, il est évident que tous les nombres,
depuis jusqu’à , sont premiers avec , et partant, dans ce
cas, on
2o. Quand est une puissance d’un nombre premier , par
exemple ; tous les nombres divisibles par ne seront pas premiers
avec , les autres le seront ; c’est pourquoi de nombres, il
faut rejeter ceux-ci :
Il en restera donc
donc …
3o. Les autres cas se ramènent facilement à ceux-ci, au moyen
de la proposition suivante : Si on décompose en facteurs , , , etc. premiers entr’eux, on aura , etc.,
qui se démontre ainsi qu’il suit. Soient , , , etc. les nombres
premiers avec et plus petits que lui. Soient de même , , , etc.,
, , , etc., etc. les nombres premiers avec , , etc.
, , , etc., etc. les nombres premiers avec , , , etc. respectivement, et plus petits qu’eux ; il est évident que tous les nombres
premiers avec le seront aussi avec les facteurs , , , etc.,
et réciproquement (no 19), et que tous les nombres qui seront congrus à l’un quelconque des nombres , etc. suivant le module , seront premiers avec ; de même pour , , etc. La
question est donc réduite à déterminer combien il y a de nombres
au dessous de , qui soient congrus à quelqu’un des nombres
, , etc. suivant le module , à quelqu’un des nombres
, , etc. suivant le module , etc. ; mais (no 52) tous les
nombres qui ont des résidus donnés suivant chacun des modules
etc. doivent être congrus suivant leur produit , et
parconséquent il ne peut y en avoir qu’un seul congru à des résidus donnés suivant les modules , , , etc., et qui soit plus
petit que . Ainsi le nombre cherché sera égal au nombre des
combinaisons des différens nombres , , , etc. avec les nombres
, , , etc. et les nombres , , , etc., etc. Or par la théorie
des combinaisons, ce nombre est . etc.
4o. On voit facilement comment on peut appliquer cette proposition au cas dont il s’agit. On décomposera en facteurs premiers ; c’est-à-dire, qu’on le réduira à la forme etc.,
, , , etc. étant des nombres premiers différens. Alors on aura
qui peut se mettre sous la forme plus élégante
etc.
Exemple : Soit on aura Ces nombres premiers avec 60, sont : , , , , , , , , , , , , , , .
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 est déterminée de manière
à ce que exprime combien il y a de nombres premiers avec
et non plus grands que alors on n’aura plus mais
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 etc. sont tous les diviseurs de , l’unité et y
compris, on aura . Par exemple, si ,
on aura
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
.
|
Démonstration. Si l’on multiplie tous les nombres premiers
avec et non plus grands que lui par , de même tous les nombres
premiers avec par , etc. ; on aura
nombres tous non plus grands que ; mais
1o. Tous ces nombres seront inégaux ; car il est évident que ceux
qui proviennent du même diviseur de sont tous inégaux. D’ailleurs
s’il en résultait deux égaux provenant de diviseurs différens et ,
et de nombres et qui leur soient respectivement premiers ;
c’est-à-dire, si l’on avait , ou bien ; en posant
, (ce qui est permis ), il s’ensuivrait, puisque est premier
avec et qu’il divise qu’il devrait aussi diviser , ce qui est
absurde.
2o. Entre ces nombres on trouvera tous ceux qui composent la
suite . En effet, soit un nombre quelconque qui
ne surpasse pas , et le plus grand commun diviseur entre
et , sera le diviseur de avec lequel sera premier. Donc
le nombre se trouvera parmi ceux qui ont été produits par le
diviseur ;
3o. Il suit de là que le nombre total en est ; donc
40. Si est le plus grand diviseur commun des nombres etc. on peut toujours déterminer les nombres etc. de manière qu’on ait etc.
Considérons d’abord deux nombres et seulement, et soit
leur plus grand diviseur commun. Alors la congruence
sera résoluble (no 30). Soit la racine , et que l’on
fasse , on aura ,
S’il y a un troisième nombre , soit le plus grand diviseur
commun de et de , il sera en même temps celui des trois
nombres , , ,[3]. On déterminera les nombres et de manière qu’on ait , et l’on aura .
S’il y a un quatrième nombre soit le plus grand diviseur
commun de et de , il sera en même temps celui des quatre
nombres , , , . On fera , et partant on aura
.
On procéderait de la même manière s’il y avait plus de nombres.
Si les nombres , , , etc. n’avaient pas de diviseur commun,
il est clair qu’on aurait .
41. Si est un nombre premier, et qu’on ait 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
Par exemple, cinq choses 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
choses, il y en ait égales à , égales à , égales à , etc.,
desorte qu’on ait , les nombres , , etc.
pouvant aussi désigner l’unité. Le nombre des permutations sera
; or le numérateur est évidemment divisible par le dénominateur, puisque le nombre des permutations
est entier ; mais il est divisible par , tandis que le dénominateur, qui est composé de facteurs plus petits que , n’est pas divisible par (no 15) ; donc le nombre des permutations sera divisible par .
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
et , et seront semblables.
Or comme chaque permutation est composée de choses, il est
clair qu’on pourra en trouver , 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 à fois le
nombre des permutations dissemblables, et conséquemment sera
divisible par . Supposons que deux permutations semblables
, puissent être identiques,
et que qui occupe la première place dans la première, occupe
la ème dans la seconde : on aura dans la dernière série le
ème terme égal au 1er, le ème égal au 2ème, etc.,
d’où résulte que le ème est encore égal au premier, et parconséquent le ème, et généralement le ème égal au
ème (où quand il faut imaginer qu’on reprenne toujours par le commencement, la série à moins
qu’on ne retranche de le multiple de qui en approche
le plus en moins). Cela posé, si on détermine de manière que
, ce qui peut toujours se faire, puisque est
premier, il suivra de là que généralement le ème terme serait égal au
è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 etc., etc., de deux fonctions de la forme
|
|
|
|
,
|
|
|
|
|
|
sont tous rationnels, mais non pas tous entiers, et que le produit soit les coefficiens etc., ne peuvent être tous entiers.
En effet, réduisons à leur plus simple expression toutes les fractions qui peuvent se trouver parmi les nombres etc. ;
etc. ; et choisissons un nombre premier qui divise
un ou plusieurs des dénominateurs de ces fractions. Supposons
que divise le dénominateur d’un coefficient fractionnaire
de il est clair qu’en divisant par on aura aussi
dans au moins un coefficient fractionnaire dont le dénominateur sera divisible par (le coefficient du premier terme par
exemple). Or on voit facilement qu’on pourra toujours trouver un
terme fractionnaire de dont le dénominateur contienne
é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 et l’exposant de dans le dénominateur. On trouvera un terme pareil dans que nous supposerons être
l’exposant de dans le dénominateur, étant on aura au moins
Cela posé, le terme du produit de par
aura un coefficient fractionnaire dont le dénominateur renfermera élevé à la puissance
En effet, soient etc., les termes qui précèdent
dans etc. ceux qui le suivent. Soient
de même dans etc., les termes qui précèdent et etc. ceux qui le suivent. Dans
le produit de par le coefficient de sera évidemment
|
|
|
|
|
|
|
|
Le premier terme sera une fraction qui, réduite à sa plus
simple expression, aura son dénominateur divisible par Si les
autres termes sont fractionnaires, leurs dénominateurs ne contiendront que des puissances de moindres que puisque chacun
d’eux est le produit de deux facteurs, dont l’un ne contient qu’une
puissance de plus petite que ou et l’autre une puissance
non plus grande que ou Ainsi sera de la forme , et le reste de la forme et étant indépendans de Donc la somme sera dont le numérateur
n’est pas divisible par et dont parconséquent le dénominateur ne peut être ramené à renfermer une puissance de moindre
que Donc le coefficient du terme dans le produit de
par sera c’est-à-dire une fraction dont le dénominateur renferme la puissance de
43. La congruence du degré
dont le module est un nombre premier qui ne divise pas , ne peut pas être résolue de plus de manières, ou n’a pas plus de racines incongrues suivant
En effet, supposons, s’il est possible, qu’on donne des congruences
de différens degrés , etc., qui aient plus de , etc. racines ;
soit le plus petit des nombres , , etc. ; desorte que toutes
les congruences d’un degré inférieur à s’accordent avec notre
proposition. Comme elle est démontrée plus haut (no 26) pour
le premier degré, sera ou . Admettons donc que la congruence……
ait au moins
racines etc. ; et supposons que tous les
nombres etc., sont positifs et plus petits que , ce qui
est permis, et en outre que soit le plus petit. Faisons dans la
congruence proposée elle deviendra
Or il est évident que cette congruence sera satisfaite si ou
ou etc., racines toutes différentes, et en nombre
mais de ce que est une racine, il suit que est
divisible par on aura donc
congruence qui sera satisfaite, en y substituant à la place de
une quelconque des valeurs : etc., qui sont
toutes et Parconséquent, dans ces differens cas,
deviendra (no 22) ; c’est-à-dire
que la congruence qui du
degré aurait 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 à y satisfissent ; ce qui est
absurde.
44. Nous avons supposé ici que le module 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 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 à 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 ne pouvait pas avoir plus de 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.