CHAP. III. — DES C0NGBUKNCE
103. Théorème. — Soit a un nombre premier avec n. Si l'on divise par n les nombres
les restes obtenus sont, dans un certain ordre, les nombres I, 2, .... n — I.
En effet, aucune division ne se fait exactement, car n étant premier avec a ne peut diviser ha que s'il divise A, ce qui est impossible si h est plus petit que n.
Aucun des restes n'étant nul, ces restes sont certains des nombres i , 2, . . . , n — i .
Deux de ces restes ne peuvent être égaux, car si ha et A'a donnaient le même reste, (A — A') a serait divisible par /i, ce que nous venons de voir être impossible.
Les restes étant des nombres de la suite i, 2, ..., n — 1, étant en même nombre qu'eux et étant différents entre eux, sont ces nombres mêmes.
Remarque, — Considérons en outre le nombre /la; ce nombre divisé par a donne comme reste zéro. On peut donc dire que si l'on divise par n les nombres
a, 2a, ..., (/i — i)a, na^
les restes obtenus sont, dans un certain ordre, les nombres I, 2, ..., 71 — 1, n.
Autre énoncé, — Les nombres a^ ia^ ....(/? — i)a, na sont congrus (mod n) aux nombres o, 1 , 2, . . . , (/i — 1 ).
104. Système complet de restes incongrus par rapport à un module, — On appelle système complet de restes incongrus par rapport à un module n, un système de n nombres tels c\\x'il y en ait un et un seul congru (mod n) à n'importe quel nombre donné.
Il est évident que les nombres o, i, 2, . . . , (/i — i) forment ua système complet de restes incongrus (mod n).
Il en est de même de tout système de nombres respectivement congrus aux précédents; par exemple, les nombres a, aa^ 3a, ... y na du théorème précédent.
PREMIÈRES NOTIONS SUR LES GONGRUENGES. 5j
On généralisera facilement en démontrant la môme propriété pour les nombres a + 6, 2a 4- 6, •••) na -^ b. En d'autres termes, n termes consécutifs dUine progression arithmétique, dont la raison est première avec /i, forment un système complet de restes incongrus (mod n).
105. Quotient de deux nombres (mod/i). — Soient deux nombres A et B et un module n premier avec B. D'après ce qui précède, il existe un nombre q et un seul (à un multiple près
de n) tel que
B^ s A (mod n).
q peut s'appeler quotient de A par B (mod n). Si A ^ o (mod /i), il en est de même de q.
Dans le cas particulier où A = i , les nombres B et y peuvent être dits inverses Vunde Vautre (mod n),
106. Généralisation des résultats du n^ 101. — Nous pouvons maintenant, comme nous l'avons annoncé, généraliser les résultats du n** 101 relatifs à la division des deux membres d'une congruence par un même nombre premier au module.
Il n'est pas, en effet, nécessaire que ce nombre soit diviseur commun des deux membres de la congruence pour que l'on puisse faire celle division; il suffît que ce nombre soit premier au module. D'après ce qui précède, si deux nombres sont congrus (mod /i), leurs quotients (mod/i) par un nombre B premier à n sont aussi congrus (mod n).
En particulier, si le module est un nombre premier absolu, on peut diviser les deux membres de la congruence par un même nombre quelconque, non congru à zéro.
107. Remarque. — Pour qu^un produit de facteurs soit congru à zéro, il faut et il suffit, quand le module est premier, que l'un des facteurs soit congru à zéro.
En effet, ceci revient à dire que, pour qu'un nombre premier divise un produit de facteurs, il faut et il suffit qu'il divise l'un des facteurs.
Les théorèmes précédents mettent bien en évidence l'analogie qui existe entre les égalités et les congruences, surtout les congruences à module premier. Cette analogie va se poursuivre.
58 GHAP. III. — DBS CONGRUEI^GSS.
§ II. — Congruence du premier degpré à une inconnue. Analyse indéterminée du premier degré.
108. De même que parmî les égalités on distingue celles appelées équations dans lesquelles cerlaines quantités sont inconnues, de même on peut distinguer les congruences dans lesquelles certaines quantités sont inconnues et doivent être déterminées de manière *à ce que la congruence soit vérifiée.
La congruence du premier degré à une inconnue a la forme
(4) ax^-b (mod n),
a el b étant connus, x étant inconnu.
D'après ce que nous venons de voir (n** 105), si a est premier avec /i, il existe un nombre et un seul {à un multiple près de n) qui satisfait à la congruence.
Si a n!est pas premier avec n, soit d le plus grand commun diviseur de a et de n. Si b n'est pas divisible par rf, la congruence est évidemment impossible. Si b est divisible par rfj soient
a ^ a'dy b — b'dj n ^ n'd^
la congruence proposée est équivalente à la suivante :
(5) a'x^b' (modn').
a' et /i' étant premiers entre eux, il existe un seul nombre (mod /i') satisfaisant à cette congruence, soit Xq, Toutes les solutions de la congruence (5) sont données par la formule
(6) X --- Xq-t- n! t^
t étant un entier quelconque.
Cherchons combien cela donne de solutions incongrues (mod n) pour la congruence proposée (4).
Pour que les deux valeurs de x données par la formule (6), pour deux valeurs t' ^ t" de t soient congrues (mod/i), il faut et il suffit que leur différence
soit divisible par /i, c'est-à-dire que t^' — d soit divisible par d. On aura donc toutes les solutions incongrues (mod n) de la
GONGRUENGB DU PREMIER DEGRÉ A UlfB INCONNUE. Sq
congruence (4) en donnanl à / les valeurs o, I, a, ..., d — iy
ce qui donne d solutions.
109. Dans le cas particulier où n est un nombre premier absolu /?, on a le résultat suivant, complètement analogue à celui relatif à l'équation du premier degré :
La congruence ax e^ ft (mod p) a une solution sia^o (mod p), [On ne compte pas comme différentes deux solutions congrues (mod /?)].
«Si a = o (mod/?) et que h^ào (mod/>) la congruence est impossible,
Sia^b^o (mod /?), la congruence est indéterminée.
110. Application. — Résolution en nombres entiers de Inéquation ax -\- by = c, — Comme nous Pavons dit dans Tlntroductîon de cet Ouvrage, un des objets principaux de la théorie des nombres est la résolution en nombres entiers des équations à coefficients entiers.
Pour Téquation la plus simple, équation du premier degré à une inconnue ax= 6, la réponse est immédiate.
Cette équation a une solution si b est divisible par a; elle n'en a pas dans le cas contraire.
