RÉSIDUS DES MULTIPLES
331 . Théorème I. Les m — 1 premiers multiples d'un nombre a premier avec m donnent pour résidus par rapport au module m, dans un certain ordre ^ les m — 4 premiers nombres.
Considérons la série des m — 1 premiers multiples de a; savoir :
et les résidus qu'ils fournissent quand on les divise par m.
PRINaPKS DE LA TBÉORIB DES NÛMBRKS. 515
Nous remarquons qu'aucun de ces résidus n'est nul ; car si lun des multiples aa donnait le résidu 0, c'est-à-dire était divisible par m, le nombre m, divisant le produit aa et étant premier avec le facteur a, «diviserait l'autre facteur a, ce qui est impossible, puisque a est plus petit que m. Nous remarquons ensuite que deux multiples aa et «'a ne peuvent donner le même résidu ; car abrs la difTérence (a—a')a de ces deux multiples donnerait le résidu 0, ce qui est impossible. On obtient ainsi par ces résidus m — 1 nombres différents qui sont tous inférieurs à m; ces résidus sont donc, dans un certain ordre, les m —1 premiers nombres
Exemple. Les huit premiers multiples de 5 donnent, p&r rapport au module 9, les résidus
332. CoBotxAiBE I. Si l'on prolonge indéfiniment la série des multiples^ les mêmes résidus se reproduisent dans le même ordre.
Considérons la série indéfinie des multiples de a; savoir :
Oa, ifl, 2fl, 3a, , (m — l)a, ma, (w4-1)û, (m-f-2)fl,
On peut déduire chaque résidu du résidu précédent en ajoutant à ce dernier le résidu de a et retranchant m si la somme surpasse m. Les m premiers multiples (en regardant comme premier multiple le produit de a par 0, c'est-à-dire 0) donnent dans un certain ordre les résidus
Le multiple ma, étant divisible par m, donne le premier résidu ; on recommence donc les mômes opérations, et Ton retrouve les mêmes résidus dans le même ordre.
Soit aa l'un des multiples. Si l'on ajoute à a un multiple quelconque de m, le résidu ne change pas.
Les deux mulliples aa et (m — a) a donnent des résidus complémentaires, c'est-à-dire des résidus dont la somme est m; car la somme de ces deux multiples est divisible par m.
333. Corollaire II. Les multiples d*un nombre b, équivalant h a par rapport au module m, donnent les mêmes résidus dans le même ordre.
En effet, puisque le résidu de h est lé même que celui de a, les deux séries de résidus sont identiques. On peut donc toujours remplacer le nombre a par son résidu, plus petit que m.
Lorsque le nombre b premier avec m n'est pas équivalent à û, les deux séries diffèrent par l'ordre des résidus,
334. Théorème IL Si deux nombres b etm ont un plus grand commun diviseur d, /^s -j — 1 multiples successifs
ei, 2a, Zor , (^ l\n,
donnent j par rapport au module m, dans un certain ordre y les résidus
d, 2rf, U, , {^ — \\d.
J'appelle a' et m' les deux quotients, premiers entre eux, que Ton obtient en divisant les deux nombres a et m par leur plus grand commun diviseur d. Soit r le résidu fourni par un multiple quelconque aa,
(if.a'=^mq'\'r \
puisque a et m sont divisibles par d, le résidu r est aussi divisible, et Ton a
en désignant par r' le quotient ^. Or, d'après le théorème précédent, les multiples de a' donnent, par rapport au module m', les résidus
Donc les multiples de a donnent, par rapport au module m^ les résidus
Le multiple suivant m'a donnerait le résidu 0, et on retrouverait ensuite les mémos résidus dans le môme ordre.
PRINCIPES DE U THÉORIE DES NOMBRES. 3i7
Ainsi, dans tous les cas, les résidus des multiples d*un nombre par rapport à un môme module forment une série périodique simple.
335. Corollaire. On a souvent à résoudre des équivalences de la forme
ax^r (mod m).
La question est de trouver les multiples de a qui donnent le résidu r par rapport au module m. On peut toujours supposer le nombre r plus petit que m, sans quoi on le remplacerait par son résidu.
Considérons d'abord le cas où a est premier avec m. La suite des m — 1 premiers multiples de a donnant pour résidus, dans un certain ordre, les m — 1 premiers nombres, l'un de ces multiples, par exemple oa, donnera le résidu r, et ensuite de m en m les mulliples reproduiront le même résidu. On peut donc donner à x les valeurs
Toutes ces valeurs sont comprises dans la formule
dans laquelle y désigne un nombre entier quelconque, ou plus simplement
x^oL (mod m).
Soit, par exemple, à résoudre Téquivalence
bx=S (mod 9).
On cherche parmi les huit premiers multiples de 5 celui qui donne le résidu 8 : c'est 5 x 7 ; on a donc
a:=7H-9î/, ou
x^zl (mod 9).
Lorsque les deux nombres a et m ont un plus gjrand commun diviseur d, il est nécessaire que le résidu r soit aussi divisible par d, sans quoi l'équivalence serait impossible. Si donc on
51S LIVRE VII. — CHAPITRE lîl.
appelle a\ m\ f^ les quotients que Ton obtient en divisant par d les nombres a, m, r, Téquivalence proposée est ramenée à la suivante :
a'a;=/ {mod m'),
dans laquelle a' et m' sont premiers entre eux.
336. Trouver combien il y a de nombres inférieurs et prg^ miers dm.
Il résulte des théorèmes précédents que, si l'on considère les m— 1 premiers nombres comme les résidus des multiples d'un même nombre par rapport au modale m, il y a autant de manières de les obtenir, c est-à-dire il y a autant d'ordres ou de dispositions différentes qu^il y a de nombres plus petits que m et premiers avec lui. Nous sommes ainsi amenés à cher* cher combien il y a de nombres inférieurs et premiers à m.
Supposons le nombre m décomposé en facteurs premiers, et soit
Imaginpns éci île la série des m premiers nombres
Si Ton en retranche les nombres qui contiennent l'un des facteurs premiers a, ft, c, d, ou plusieurs d'entre eux, il restera les nombres premiers avec m.
Mettons d'abord à part les nombres qui contiennent le facteur a, c'est-à-dire les multiples de a,
tt, iaé Zdé * — tf*
Ces multiples sont au nombre de — . De même les multiples do
b sont au nombre de -^ ) les multiples de ab au nombre de
j-r, etc. Si de la série des tft premiers nombres on retranche
les multiples de a qu'elle renferme^ la série des nombres res-
PRINCIPES DK U THÉÛRIE D£S NOMBRES. 31
tants contiendra m^— , oufn(i — | nombres. Pouk* abré-
a \ aj
! ger nous poserons
nous désignerons par (m) la sériedes m premiers nombres, par
f — jla série des multiples defl, et par (m') la série qui reste
quand on retranche la seconde de la première.
Cherchons maintenant combien dans la série (m') il y a de multiples de 6. Ces multiples sont ceux que contient la série
(m), moins ceux que contient la série f — j , Le nombre des premiers est t-. Puisque a et fr sont premiers entre eux, les multiples de h contenus dans la série f - J , étant en môme temps multiples de a, sont multiples de ah; ce sont donc les mulfi-^ ^les de ah contenus dans la série (m); leur nombre est -?
Ainsi le nombre des multiples de h contenus dans la série [m') est
ab~
De même le nombre des multiples de c contenus dans la
série (m') est — , le nombre des multiples de bc est -r- etc. On
' c oc
voit par là que la série (m') jouît des mêmes propriétés que la série (m).
Si de la série (m!) on retranche les multiples de b qu'elle
contient, la série des nombres restants renferme W— -r- ou m'{ 1— r ) nombres. Pour abréger, nous poserons
520 LIVRE VII. — GHÂPfTRK Ht.
nous désignerons par ( -r- ) la série des muUiples de b que ren*
ferme la série (m'), et par (m") la série des nombres restants.
Le même raisonnement peut être continué indéfiniment.
Cherchons combien dans la série (m") il y a de multiples de c;
ces multiple»sont ceux que contient la série (m') , et qui sont au
nombre de — , moins ceux que contient la série ( j< j ; les nom*
bres c et ft étant premiers entre eux, ces derniei^sont les mul-
m' tiples dé bc contenus dans la série (m'), au nombre de p. Le
nombre des mutliples de c contenus dans la série (m") est donc
c bc^^ c c '
Ainsi la série (m") jouit des mêmes propriélés que la série (m') ,
ou que la série (m). Si de cette série (m") on retranche les
mutliples de c qu'elle contient, la série restante contiendra
''— — =m" 1 — I nombres. Ces derniers nombres sont c \ cj
premiers avec m. En remplaçant m", puism' par leurs valeurs, et désignant par n le nombre des nombres inférieurs et premiers à m, on obtient la formule
ou
Parexemple,sim=12 = 2«x3,onan=2(2— 1)(3 — 1) = 4. Les quatre nombres inférieurs et premiers à 12 sont
11 en résulte les quatre dispositions suivantes des 11 premiers nombres :
PRINCiPES DE LA THÉORIE DES NOMBRES 331.
337. Reuarque. Si a est un nombre inférieur et. premier à fhytn — a est aussi premier avec m; ainsi les nombres infé-. rieurs et premiers à m se correspondent deux à deux, et leur nombre est pair. Les dispositions correspondantes des m — 1 premiers nombres sont inverses Tune de l'autre.
Il y a exception pour m=2; dans ce cas m = 1.
33d. ConoixAiRE I. Soient m et m' deux nombres premiers entre eux. Désignons par n le nombre des nombres inférieurs et premiers à m, et par n' le nombre des nombres inférieurs et premiers à m'. Supposons m et m' décomposés en facteurs premiers, et soient
on a
Les facteurs premiers a\ V étant dilférenls de a, 6, c, le nombre des nombres inférieurs et premiers au produit
est
Par exemple, si w=3, m'=5, on a h=2, n'=:4. Le «ombre des nombres inférieurs et premiers à 3 X 5 ou 1 5 est 2 x 4 c'csl-à-dire 8. •
339. Corollaire IL Supposons la circonférence divisée en m parties égales, et plaçons sur les points de division les numéros
Si Ton prend pour unité Tu; : des divisions, la circonférence
vftut m unités. Quand, partant du point 0, on parcourt dans le même sens les arcs
a, 2fl, 3fl, , (m — l)a,
les numéros auicquels on arrive sont précisément les résidus de ces multiples par rapport au module m; car un multiple quelconque égale un certain nombre de circonférences, c'està-dire un certain nombre de fois m, plus le numéro auquel on aiTive.
Quand a est premier avec m, les multiples de adonnent pour résidus les m — 1 premiers nombres, et Ton passe par tous les points avant de revenir au point de départ. Le multiple ma ramène au point de départ 0. En continuant, on repasse par les mêmes points que précédemment. On obtient ainsi un polygone régulier de m côtés.
Mais si a et m ont un plus grand commun diviseur d, on ne passe que par les numéros multiples de d, et Ion forme un
polygone régulier de -r côtés.
Les multiples de a et de m— a donnent le même polygone en ordre inverse; il en résulte que le nombre des polygones réguliers de m côtés est égal à la moitié du nombre des nombres inférieurs et premiers à m.
(Voyez, pour plus de détails, mes Éléments de géométrie.)
RÉSIDUS DGS PUISSAKCES.
340. Thêorèhe III. Soit p un nombre premier ^ a un nomh-e ^elconque non divisible par p, le nombre bT'^ est équivalent à Vunité par rapport au module p.
En effet, on sait que le produit de plusieurs nombres équivaut au produit des résidus de ces différents nombres (n'^ÔO); les multiples
a, 2û, 3fl, , (p — l)â
donnent» par rapport au module p, les résidus
PRINCIPES DE LA THÉCmiK DES NOMBRES. 525
Le produit dé ious ces multiples équivaut au produit de tous les résidus. On a donc
