C. 11., i. XII, p. 8(3 (lo mai i8',i). f Suite

§ H. — Sur la résolution des équations indéterminées du premier degré

en nombres entiers.

Supposons qu'il s'agisse de résoudre, en nombres entiers, une équation indéterminée du premier degré à plusieurs inconnues. Si ces inconnues se réduisent à deux

l'équation indéterminée sera de la forme

a, b, /-désignant trois quantités entières, et ne pourra être résolue que dans le cas où le plus grand commun diviseur de a et de h divisera k. Mais alors on pourra diviser les deux membres de l'équation (i) par ce plus grand commun diviseur, et, comme on pourra, en outre, si a est négatif, cbanger les signes de tous les termes, il est clair que l'équation (i) pourra être réduite à la forme

(•^) mjc±ny=:±l

/, m, //désignant trois nombres entiers, et//^ n étant premiers entre eux.

VEuvres de C. — S. I, t. VI. , •-.

Observons maintenant que l'équation (2) coïncide avec l'équivalence

mx^±l (mod/i) ou

(3) x^±— (mod/O,

et qu'en vertu de la formule

— = ^ X — (modn), m ni

la résolution de l'équivalence (3) peut être réduite à celle de la suivante :

(4) x^ — (mod/i).

D'autre part, si n est un nombre premier, on aura, d'après un tbéorème connu de Fermât,

(5) m«-*=i (mod/0,

par conséquent

— = /n"-2 (mod/<).

Donc alors rn!'-'^ sera une des valeurs de x propres à vérifier l'équivalence (4), de sorte qu'on résoudra cette équivalence en posant

(6) n^m"^-- (mod/0-

Telle est la conclusion très simple à laquelle M. Libri et M. Binet sont parvenus pour le cas où le module n est un nombre premier. Pour étendre cette même solution à tous les cas possibles, il suffirait de substituer au théorème de Fermât le théorème d'Euler suivant lequel, n étant un module quelconque et m un entier premier à 71, on aura généralement

(7) m^' = I (mod/i)

si l'exposant N renferme autant d'unités qu'il y a de nombres entiers

inférieurs à // et premiers à n (' ). En efiet, l'écf nation (7) étant admise,

on en conclura

et, par conséquent,

/«■^"' (mod/i)

ni ^ '

sera l'une des valeurs de x propres à vérifier l'équivalence (4), de sorte qu'on résoudra cette équivalence en prenant

(8) x^^m'^-'^ (mod/0-

L'équivalence (4), étant résolue comme on vient de le dire, entraînera la résolution de l'équivalence (3) qui coïncide avec l'équation (2), et, par suite, la résolution de l'équation (1), dans le cas où le plus grand commun diviseur de a et de h divisera k. On résoudra, en particulier, l'équivalence (3) en prenant

(9) x^^zni^-H (mod«).

(') Al. Poinsot nous a dit avoir remis autrefois à M. Legendro une Note manuscrite dans laquelle il avait ainsi étendu à des modules quelconques la solution présentée par AI. Binet, et relative au cas où N est un nombre premier. Dans cette môme Note, M. Poinsot donnait du théorème d'Euler la démonstration suivante, analogue à celle qui, dans le Mémoire de M. Binet, se trouve appliquée au théorème de Fermât.

Soient

la suite des entiers inférieurs à //, mais premiers à //; N le nombre de ces entiers, et /?i lun quelconque d'entre eux. La suite

///. aiii, uni, cm,

se composera encore de termes, premiers à n, mais qui, divisés par //, donneront des restes différents. Donc chaque terme de la seconde suite sera équivalent, suivant le module //, à un seul terme de la première, et l'on aura

ï.a.b.c. . . s^ m.am .bin.cin. .. ^si. a. b.c. . ./«^' (mod/0

ou, ce qui revient au même,

i.a.b.c. . .(ni^ — i) es o (mod«),

puis on en conclura

in'^ — I == 0 ou in^ ss i (modn).

En résumé, l'on pourra énoncer la proposition suivante :

TiiKORKME ]. — a, h, k désignant trois quantités entières, on pourra résoudre en nombres entiers l'équation indéterminée

(i) ax -\- by = /.-,

si le plus grand commun diviseur de a et de h divise k. Supposons d'ailleurs qu'en divisant a, h, c par ce plus grand commun diviseur, et c/iangeant s il est nécessaire les signes de tous les termes de l'équation ainsi obtenue, on la réduise à la suivante

( 2 ) m X ± ny t=.± l, ou, ce qui revient au même, à l'équivalence

(3) ^ ==± (mod n),

l, m, n désignant trois nombres entiers, et m, n étant premiers entre eu.r. Pour x^érifier V équivalence (3), il suffira déposer

N désignant le nombre des entiers inférieurs à n, mais premiers à n. Corollaire I. — L'équation indéterminée

ax -\- by z= A

est toujours résoluble en nombres entiers, non seulement lorsque les coefficients a, b des deux inconnues sont premiers entre eux, mais aussi lorsque la valeur numérique du terme tout connu k est égale au plus grand commun diviseur de a, b, ou divisible par ce plus grand commun diviseur. Par suite, le plus grand commun diviseur de deux (juantités entières a, b peut toujours être présenté sous la forme

ax -\- by,

X, y désignant encore des quantités entières.

EXTRAIT iV 123. 117

Corollaire IL — /, m, n désignant trois nombres entiers, et m, n étant premiers entre eux, on peut toujours satisfaire par des valeurs entières de a^, y -à l'équation

7)1 X — Il y =z± l.

D'ailleurs les diverses valeurs de r propres à vérifier cette équation ou, ce qui revient au même, l'équivalence

jc -,= ± — (mod /i) m

sont toujours équivalentes entre elles suivant ce module /i; en sorte que, l'une d'elles étant désignée par E, on aura généralement

z- désignant une quantité entière positive ou négative.

On déduit aisément du théorème I celui que nous allons énoncer :

'Théorème II. — Soient

un module dëcomposable en deux facteurs n^, n^^ premiers entre eux; rl'un quelconque des entiers inférieurs à n, mais premiers à n, et

les restes qu'on obtient quand on divise r par le premier ou le second des (leur facteurs

Nbn seulement à chaque valeur de r correspondra un seul système de valeurs de r , /;^, mais réciproquement, à chaque système de valeurs de /;, /;,, correspondra une seule valeur de r.

Démonstration. — D'abord /;, étant le reste de la division de /• par //, sera complètement déterminé quand on connaîtra /•, et l'on pourra en dire autant de r,. De plus, à deux valeurs données de

correspondra une valeur de /qui devra être de chacune des formes

X, y désignant deux quantités entières. Or les deux équations

entraîneront la formule ou

et les valeurs de x, propres à vérifier cette formule, seront de la forme

; désignant l'une quelconque de ces mêmes valeurs, et z une quantité entière, positive ou négative. Cela posé, si l'on fait, pour abrégei',

/•,+ «,; = cil,

l'équation donnera

/• = Jl 4- «; «, -^

ou, ce qui revient au même,

Or, puisque les diverses valeurs de rque déterminerait cette dernière équation, si la quantité entière z restait arbitraire, sont équivalentes entre elles suivant le module n, il est clair qu'une seule sera positive et inférieure à n. Donc, à des valeurs données de r , /;, correspondra une seule valeur de r, positive et inférieure à n. Si l'on étend le théorème II au cas où le module n est décomposable en plus de deux facteurs, on obtiendra la proposition suivante :

Théouème III. — Soient u/i module décomposable en plusieurs fadeurs

«/. fi:P n,r •••

qui soient tous premiers entre eux ; r l'un quelconque des entiers inférieurs à n, et

les restes quon obtient quand on divise rparVun des facteurs

Non seulement à chaque valeur de r correspondra un seul système de valeurs de /;, /;,, /; , . . ., mais réciproquement, à chaque système de valeurs de r , /;^, r , . . . correspondra une seule valeur de r.

Démonstration. — En raisonnant comme dans le cas où les facteurs n^, /î,„ ... se réduisent à deux, on prouvera d'abord qu'à chaque valeur de r répond un seul système de valeurs de/;, /;,, /;,, Soit d'ailleurs

le produit des facteurs de n différents de /?,, en sorte qu'on ait

et nommons r' le reste de la division de /• par n' . En vertu du théorème 1, si les facteurs n,, n^^, n^^^ se rétluisent à trois, on verra correspondre une seule valeur de r à chaque système de valeurs de /;,, /„, et une seule valeur de r à chaque système de valeurs de /;, /', par couséquent à chaque système de valeurs de /;. /;,, /;,. Ainsi l'on passe facilement du cas où le nombre des facteurs de n est i au cas où ce nombre devient égal à 3. On passera de la même manière du cas où il existe trois facteurs de n premiers entre eux au cas où il en existe quatre, et ainsi de suite. Donc le théorème lll est généralement exact, quel que soit le nombre des facteurs premiers de n.

Corollaire. — Le module

étant décomposable en facteurs

qui soient premiers entre eux, nommons toujours

/• l'un quolcoiique des enlicrs inféiieurs à n , mais premiers à ti ; /•^ l'ini (|LieIcoiique des entiers inférieurs à n^, mais premiers à n^; i\^ l'un quelconque des entiers inférieurs à n^^^ mais premiers à «,,; >

et soient, en outre,

N le nombre des valeurs de /• ; N/ le nombre des valeurs de /y, N\ le nombre des valeurs de r^;.

Les systèmes de valeurs que l'on pourra former, en combinant une valeur de /; avec une valeur de /;, avec une valeur de r^^, . .., seront évidemment en nombre égal au produit

Donc, puisqu'il cliacun de ces systèmes correspond une seule valeur de /', et réciproquement, on aura

Il sera facile maintenant de résoudre la question que nous allons énoncer.

Problèmj: L — Déterminer le nombre"^ des entiers inférieurs à un module donné n et premiers à ce module.

Solution. — Pour résoudre aisément ce problème, il sera bon de considérer successivement les divers cas qui peuvent se présenter, suivant que le module n est un nombre premier, ou une puissance d'un nombre premier, ou un nombre composé quelconque.

Or : I" si le module n est un nombre premier, alors les entiers

non supérieurs au module n, étant tous, à l'exception de n, premiers ;i ce module, on aura évidemment

EXTRAIT N" 123. VQ/^,p 121

Alors aussi, la solution que fournira lo théorème I, pour une équation indéterminée, ne différera pas de la solution donnée par M. Libri et par M. Binet.

2" Si le module

se réduit à une certaine puissance d'un nombre premier v, alors, parmi

les entiers

dont le nombre est ji, les uns, divisibles par v, seront le produit de v par les entiers

dont le nombre est "; les autres, premiers à v, ou, ce qui revient au même, à n, seront évidemment en nombre égal à la différence

On aura donc

3« Si le module n est un nombre entier quelconque, on pourra toujours le décomposer en facteurs dont chacun se réduise à un nombre premier ou à une puissance d'un nombre premier. Nommons

ces mêmes facteurs, en sorte qu'on ait

et

V,, V , V , ... désignant des nombres premiers distincts les uns des autres. Représentons d'ailleurs par

i\, le nombre des entiers inférieurs et premiers à //, , N, le nombre des entiers inférieurs et premiers à // , N^,^ le nombre des entiers inférieurs et premiers à //,^,

CF.uvrcs de C. — S. 1. 1. ^ I.

Le corollaire du théorème III donnera

(lo) N = N,N,,N,...,

puis on en conclura, eu égard à la formule (i i),

OU, ce qui revient au même,

(i4) N = vr' v^'v-». . . (V,- I) (V,- I) (V,,- .)....

Corollaire. — Lorsque le module n se réduit au nombre 2, ou plus généralement à une puissance 2=* de ce même nombre, la valeur de X, en vertu de la formule (10) ou (i i), se réduit à l'unité ou plus généralement à 2''"', en sorte qu'on a

Revenons maintenant au théorème I. On peut évidemment, dans ce théorème et dans les formules (8), (9), remplacer le nombre N des entiers inférieurs au module ji, mais premiers à n, par l'une quelconque des valeurs de «pour lesquelles se vérifie l'équivalence

(i5) ni^^EBi (mod/^).

Or parmi ces valeurs il en existe une, inférieure à toutes les autres, et qui, pour ce motif, doit être employée de préférence. D'ailleurs cette valeur particulière de /jouit de propriétés remarquables qui peuvent servir à la faire reconnaître et calculer. Entrons à ce sujet dans quelques détails.

Les nombres entiers m, n étant supposés premiers entre eux, l'unité sera c^rtainement, dans la progression géométrique

le premier terme qui se trouve équivalent, selon le module n, à l'un des termes suivants. En effet, une équivalence de la forme

EXTUAIT N" 123. 123

dans laquelle 1 eU" seraient entiers et positifs, entraînera nécessairement une autre équivalence de la forme

i^m' (mod/i),

dans laquelle le terme m' de la progression se trouverait remplacé par l'unité. Ajoutons que, si m' représente la moins élevée des puissances entières et positives de m, équivalentes à l'unité suivant le module n, le reste que l'on obtiendra en divisant par n les termes de la proi^ression

formera une suite périodique, dans laquelle les / premiers termes seront différents les uns des autres. Représentons par

I, m , ni.

ces premiers termes. Comme, dans la progression dont il s'agit, deux termes seront équivalents entre eux suivant le module n quand ils répondront à des exposants de la base m équivalents entre eux suivant le module i, on aura évidemment

\ ni^ EE /;i'+' ^:E^ m-'+^ ^EB .. — ni, j (»6) 'ni- ^ni'^"- ~ni-i^--~.. .^ni', , (mod/O-

//i' -• SE /«-'-' EE /«^'-l ^ . . . SS/?l(' 1)

I/exposant de la puissance à laquelle il faut élever la hase //?, pour obtenir un nombre équivalent suivant le module n à un reste donné, est ce qu'on nomme V indice de ce nombre ou de ce reste. Cela posé, il est clair que, dans les formules (i6), les indices correspondants au reste i seront représentés par les exposants

o, /, ii, ...,

les indices correspondants au reste m' par les exposants

les indices correspondants au reste m" par les exposants

eniin les indices correspondants au reste m''~'^ par les exposants

/ — I , ii — 1 , 3 < — I , .... Donc, puisque les restes

seront tous inégaux entre eux, les seuls indices positifs de l'unité seront les divers multiples de i, et le plus petit de ces indices ou le nombre i montrera combien la suite périodique des restes, indéfiniment prolongée, renferme de restes différents. L'étendue de la période formée avec ces restes

se trouvera donc indiquée par le plus petit des indices de l'unité, auquel nous donnerons, pour cette raison, le nom iV indicateur. Cela posé, on pourra évidemment énoncer la proposition suivante :

Théorème IV. — m, /i désignant deux nombres entiers, et m étant premier à n, les seules puissances entières et positives de m qui seront équivalentes à l'unité, suivant le module n, seront celles qui offriront pour exposants l'indicateur i correspojidant à la base m et ses divers multiples.

On déduit immédiatement du théorème IV celui que nous allons énoncer :

Théorème A'. — Si le module n est décomposable en divers facteurs n^, n^^, ..., en sorte qu'on ait

n :rr n^ Il ^ . . .

et SI, la base m étant un nombi^e premier à n, on nomme les indicateur correspondants aux modules

l'indicateur i, correspondant au module n, sera le plus petit nombre entier qui soit divisible par chacun des indicateurs i^, i^^, ....

Démonstration. — En effet, l'indicateiiri correspondant au module /t sera la plus petite des valeurs de / pour lesquelles se vérifiera la formule

ni^^i (modn).

D'ailleurs, n étant égal au produit des facteurs n^, n^^, ..., cette formule entraînera les suivantes :

m' = i (mod/i^), 7n'^i (mod/?J, ....

Donc, en vertu du théorème précédent, i devra être à la fois un des

multiples de //,, un des multiples de n^^ Donc la valeur cherchée

de «sera la plus petite de celles qui seront h la fois divisibles par//,, par n^^, ....

L'indicateur i, correspondant à un module donné n, varie généralement avec la base m; mais cette variation s'effectue suivant certaines lois, et l'on peut énoncer à ce sujet les propositions suivantes:

TiiKORKME Vf. — Si la base m est décomposable en deux fadeurs

ni^, 1)1. ,

auxquels correspondent des indicateurs

premiers entre eux, dans le cas où le nombre n est pris pour module, on aura, non seulement

mais encore, en désignant par i Vindicateur correspondant à la base m et

au module n,

Démonstration. — L'indicateur i relatif à la base m vérifiera la formule

m'=i (moûn),

de laquelle on tirera

//<-'e^ i, ni^'^ I, . . .

ot, généralement, si l'on désigne par / un multiple quelconque de î,

(17) 7w-/e=i (mod/i)

ou, ce qui revient au même,

(i8) mhni^i (mod«).

D'autre part, les indicateurs / , i^^, relatifs aux bases m., m^^, vérifieront les équivalences

(19) m'' ^ I , m'j- ^ [ ( m od « ) î

et il suffira que i, divise j pour que la première des formules (19) entraîne l'équivalence

in'~i (modn),

par conséquent, eu égard à la formule (18), l'équivalence

jnJ=i (mod/i),

qui suppose [voù^Xa théorème IV) y divisible par i^,. Ainsi, de ce que le nombre i vérifie l'équivalence

/«' = i (mod/î),

il résulte que tout multiple de /, divisible par?, sera en même temps divisible par j^/, en sorte que i^, divisera nécessairement le produit ii^, et par suite le nombre i, si i, i^^ sont premiers entre eux. Mais alors «. divisible par/, devra l'être pareillement et, pour la même raison, par 4. Donc, si i^, (^ sont premiers entre eux, tout nombre i, propre à vérifier l'équivalence

/m' = i (inod/0,

sera divisible par le produit i^i^,, et l'indicateur correspondant à la base m, ou la plus petite des valeurs de i pour lesquelles on aura

m'~i (mod/0»

devra se réduire à ce produit.

TfiéorèmI': YII. — Soient

les indicateurs correspondants à deux bases diverses

inais à un même module n. Le plus grand commun diviseur m des indicateurs i^, i^^ pourra être décompose, souvent même de plusieurs manières, en deux facteurs u, v tellement choisis, que les rapports

soient des nombres premiers entre eux, et, si l'on pose alors

Il 11.''

l'indicateur i, relatif à la base /n, sera le plus petit nombre entier que puissent diviser simultanément les indicateurs i^, i^^.

Démonstration. — Concevons que le plus grand commun iliviseur w de f,, (^ soit décomposé en facteurs

dont chacun représente un nombre premier, ou une puissance d'un nombre premier. Deux produits

formés avec ces mêmes facteurs, de manière que l'on ait

fourniront, pour les rapports

des nombres premiers entre eux, si l'on fait concourir chaque facteur, par exemple le facteur a, à la formation du produit //, quand a est premier à ^; du produit v, quand a est premier à -; enfin du produit u ou du produit v indifleremment, quand a est premier à chacun des deux

nombres

-1 JL , (X Cf.

Les deux produits u, v étant formés, comme on vient de le dire, ponr déduire le théorème VII du théorème VI, il suffit d'observer que,

étant les indicateurs relatifs aux bases les nombres entiers

seront les indicateurs relatifs aux bases

et que, ces indicateurs étant premiers entre eux, la base m déterminée

par la formule

(le

evra correspondre à l'indicateur

Il V 0)

Or cette dernière valeur /sera précisément le plus petit nombre entier que puissent diviser simultanément les indicateurs i^, i^^.

Corollaire L — Pour montrer une application du théorème VII, considérons en particulier le cas où l'on aurait

Comme

5* et 29"

seront les puissances les moins élevées des nombres 5 et 29, qui, divisées par le module 78, donneront pour reste l'unité, on aura nécessai-

rement

et, par suite,

';=4j ^//=6, (ji-—'î,

attendu que, des deux rapports

JL — "î . , — ,),

le second seul sera premier au facteur 2 de co. Gela posé, pour obtenir une base m, correspondante à l'indicateur

il suffira de prendre et, puisque

il suffira de prendre

Effectivement, 71 '=* est la première puissance de 7 1 qui, divisée par 7cS, donne pour reste l'unité.

Corollaire II. -- Etant données deux bases qui correspondent à deux indicateurs différents on peut toujours trouver une troisième base

qui corresponde à l'indicateur i représenté par le plus petit Ae^ nombres (jui divisent à la fois les deux indicateurs donnés.

Corollaire III. — Soient

trois bases différentes, et

OEtivres deC. — S. I. t . M .

les indicateurs qui correspondent à ces trois bases, mais à un seul et même module /?. Si l'on nomme i' le plus petit nombre que diviseront simultanément i^^ et /,, le plus petit nombre i que pourront diviser simultanément i^ et i' sera en même temps le plus petit des nombres divisibles par cbacun des trois facteurs

D'ailleurs, à l'aide du théorème VII, on pourra trouver, non seulement une base m correspondante à l'indicateur i', mais encore une base m correspondante à l'indicateur i. Donc, étant données trois bases différentes avec un seul module, on peut toujours trouver une nouvelle base qui corresponde à l'indicateur représenté par le plus petit des nombres que divisent les trois indicateurs correspondants aux trois bases données. En appliquant un raisonnement semblable au cas où l'on donnerait quatre ou cinq bases au lieu de trois, on obtiendra génél'alement la proposition suivante :

Théorème YIII. — Etant données plusieurs bases différentes

"ip "'„» '"./' ••■y

avec un seul module n, on peut toujours trouver une nouvelle base qui corresponde à r indicateur représenté par le plus petit des nombres que divisent à la fois les indicateurs' con^espondants aux bases données.

Corollaire. — Si le système des bases données

comprend tous les entiers inférieurs au module donné ti et premiers à ce module, les indicateurs

relatifs à ces mêmes bases, seront tous ceux qui peuvent correspondre au module n. Cela posé, on doit conclure du théorème YllI que tous les indicateurs correspondants à un module donné divisent un mémo nombre qui coïncide avec l'un de ces indicateurs. Il est d'ailleurs évi-

(lent que ce dernier doit être le plus grand de tous les indicateurs, ou celui qu'on peut appeler X indicateur maximum. Nommons 1 cet indicateur maximum. En vertu de la remarque précédente et du théorème IV, l'équivalence

(20) m';si (inod/<)

se trouvera vérifiée toutes les fois que le nombre m sera premier au module n\ et, dans cette supposition, on résoudra en nombres entiers l'équation

m X ± ny = ±: /,

en prenant

(21) X ^±L nu} -'/.

Il nous reste à déterminer, pour cbacjue module n, l'indicateur maximum I. Cette détermination de l'indicateur maximum se trouve intimement liée à la recherche des valeurs correspondantes de la base m, valeurs que nous appellerons racines primitives du module /?, en généralisant une définition admise par les géomètres pour le cas où ce module est la première puissance ou même une puissance quelconque d'un nombre premier impair. D'ailleurs la détermination dont il s'agit se déduit aisément des propositions déjà établies, jointes à quelques autres théorèmes que nous allons énoncer.

TiiÉORÈMi: IX. — Soient n un nombre premier, et X une fonction entière (le X, dans laquelle les coefficients numériques des diverses puissances de x se réduisent à des nombres entiers. Si l'on nomme r une racine de l'équivalence

(22) X = o (mod/i),

et X^ un second polynôme semblable au polynôme X, mais du degré immédiatement inférieur, on pourra choisir ce second polynôme de manière que l'on ait, pour toute valeur entière de x,

(23) \ = {x—r)\^ (mod/0-

Démonstration. — En effet, soit K ce que devient X pour x = r. La

différence X — R sera divisible algébriquement par x — r, et le quotient sera un polynôme X^ semblable au polynôme X, mais du degré immédiatement inférieur. Comme on aura d'ailleurs identiquement