DÉCOMPOSITION DBS NOMBRES ENTIERS

£n effet, les nombres a et a' ne diffèrent que par un ma)lipl& de m ; il en est donc de même des nombres ah et a'b.

Si a ^ a', b Si b' {mod. m), on a aussi ab ^ a'b' (mod, m).

En effet, on a, par hypothèse, a-r^ a' '\- km et fr = fr' + hm ; donc, en multipliant ces deux égalités membre à membre, on a ah = ctb' -hpm, p désignant le nombre entier a' h + b'k + hhm.

Ce théorème s'étend sans difficulté au cas où on considère un nombre quelconque de congruences.

Les propriétés relatÎTes à la division ne sont pas vraies sans restriction.

Ainsi, de ce que ab s a'b (mod. m), il ne résulte pas nécessairement que asm a' (mod. m) ; cela n^est certain que si b est premier avec m; car alors on a un produit de deux facteurs, divisible par m, b(a — a'), et, comme m est premier avec le facteur b, il divise le second, a — a^. Mais si b n*est pas premier avec m, soit 8 le p. g. c. d. entre 6 et m ; le produit

^a — a') est divisible par x* et comme ? ®t r sont premiers

entre eux, on peut seulement affirmer que a — a' est divisible

La congruence ab ^ al> (mod, m) entraîne donc seulement a = a' {mod, -^ ), 8 étant lep, g. c, d, entre m et h.

De même si l'on a a& s a'b' (mod. m) et a a a' (mod. m), il n*en résulte pas nécessairement b^ b' (mod. m).

En effet, on a toujours 6 = &' 4- m/n- f , h étant un entier positif ou négatif, et r le reste de b — If relatif au module m ; en prenant pour r le reste positif, r est compris parmi les nombres 0, 1, 2, ..., m — 1. On déduit de là 6 s &' -h r (mod. m), et, comme a^^a' (mod. m), on a

ab s a'b* -h a'r (mod. m).

En retranchant la première congruence de celle-ci, il reste a'r = 0 (mod. m). Cette condition n'entraîne r = 0 que si a' est premier avec m ; mais si a' et m ont un p. g. c. d. 8 autre

m 2m 3m (8 — i)m que i , on a r = 0 ou -j ou -g- ou -j-» ... ou g , et,

dans ce cas, on n'a pas nécessairement h ^b' (mod m), mais

seulement& as &' (mod. -g-).

Au lieu de a', on eût pu considérer a ; or ces deux nombres, pris successivement avec m, donnent le même p. g. c. d., puisque, par hypothèse, a — a' est divisible par m.

Enfin, il est évident que si deux nombres sont congrus relative-

i64 PROPRIÉTÉS DBS NOMBRES

ment à un module quelconque, ils sont congrus par rapport à tout diviseur de ce module.

Car dire que a s a' (mod. m), c'est dire que a — a' est divisible par m, et alors cette différence est divisible par tout diviseur de m.

* 95. Idée des congruenees entières. — Si nous considérons une congruence renfermant une inconnue, par exemple la congruence

a;' — 8a? -h 6 s 0 (mod. m),

dans laquelle œ représente un nombre entier inconnu qui doit rendre le premier membre divisible par m, nous dirons que Tune des valeurs entières de œ qui satisfait à cette condition est une racine de la congruence.

11 est facile de voir que si une congruence a une racine, a?, elle en a une infinité, et que tout nombre congru à a?, par rapport au module m, satisfait aussi à la congruence. En effet, soit y ^ a> (mod. m) ; on a y' ^ x^ (mod. m). D'où

y9^a^^ ^ 8y S — Sa?, 6 s 6 (mod. m) ;

il n*y a plus qu'à combiner ces trois congruenees par voie d'addition pour obtenir

t/3 8y j 6^a;8 3a.^es0 (mod. m).

Si donc on a une racine a? d'une pareille congruence, tous les nombres de la forme œ-h hm sont aussi racines. On regarde tous ces nombres comme ne formant qu'une solution, et on se borne à chercher les racines inférieures au module m.

Si l'on considère la congruence

a;3 — 8a? -4- 6 ss 0 (mod. 5),

il n'y a qu'à essayer les 5 nombres 0, 1, 2, 3, 4; le premier membre donne les restes 1, 4, 3, 4, 3» et aucun de ces nombres ne convient. Cette congruence n'a pas de racine. On peut en conclure en outre qu'il n'y a pas de nombre entier qui annule a?« — 8a? 4- 6, c'est-à-dire que l'équation a?' — 8a? -f- 6 = 0 n'a aucune racine entière.

Résoudre une congruence, c'est trouver les racines de cette congruence; on peut dire que la congruence précédente est résolue et n'a pas de racine.

La congruence

a?* — 4a?' -h 5a?* — 7a? — 6 ■■ 0 (mod. H) admet pour racines i, 5, 10.

" 96. Caractères de divisibilité. — Les caractères de divisibilité peuvent être exposés très simplement avec le langage

DâCOMPOSlTlOM DBS N0B1BRB8 BKTIERS 165

actuel. Prenons pour exemples les caractères de divisibilité par 9 et par il.

Soit N un nombre de 7 chiffres, par exemple, et soient a, b, c, d, e, f^ g ces chiffres, le nombre étant parcouru de droite à , gauche. Nous avons vu que Ton a 1 5 10 s 100 ■■ 1000 ai 10000 B 100000 ai 1000000 (mod.9) ; d*où Ton déduit la suite des congruences

a^a, iOb SB b, iOOe stt c, \

iOOO d^d, lOOOOe SB 0, 100000 Z' la f, ? (mod. 0). 1000000 gwsg /

En ajoutant ces diverses congruences, on obtient

N m a-hb-hc-hd-he-hf-^g (mod. •).

(1 n'y a plus qu'à traduire cette congruence en langage ordinaire pour avoir le caractère de divisibilité par 9. On a de même

1 = 1, 10 a — 1, 100 al, 1000 — — 1, etc., (mod. 11).

On en déduit

. a^a, iOôsi — &, 100 c aie J

1000 c^ s — (2, 10000 6 as e [ (mod. 11). 100000/'=-/', 1000000 ^s^\

En ajoutant ces diverses congruences on obtient

N aa — ô + c— d + e — /"^y (mod. 11).

C'est le caractère de divisibilité par 11. 11 n'y a plus qu'à traduire cette congruence en langage ordinaire pour obtenir le caractère de divisibilité tel que nous l'avons donné antérieurement.

* 97. Congruences du premier degré. — La congruence ax-hb^O (mod. m), dans laquelle a et 6 désignent des nombres entiers donnés, positifs ou négatifs, et où a désigne un nombre entier inconnu, s'appelle la congruence du premier degré.

Nous allons chercher les racines de celte congruence, c'est-àdire les nombres entiers de l'ensemble 0, 1, 2, . . ., m — 1, qui, mis à la place de a?, rendent le premier membre divisible par m.

La résolution de cette congruence revient à la recherche des

solutions entières de l'équation à deux inconnues oo? -h d = my

ou my — 007 = d, pourvu que l'on ne garde de chaque solution

j que la valeur de m et que l'on se borne à celles qui sont plus

/ petites que m.

Si a et m sont premiers entre eux (voir n* 88), l'équation aune infinité de solutions entières données par les formules flv = 0^0 + km, y = yo + Aa, dans lesquelles h désigne un

i66 PROPRIÉTÉS DES KOMBRBS

nombre entier quelconque, positif, négatif ou nul. Toutes les valeurs de œ sont donc congrues, suivant le module m, au même nombre â?o > il y a donc une et une seule racine, le reste de x^ lelatif au module m.

Si a et m ne sont pas premiers entre eux et que leur plus grand commun diviseur ne divise pas le nombre ^, il n'y a pas de solution et la congruence est impossible.

Si a et m ont un plus grand commun diviseur 8, autre que I, et qui divise è, il y a une infinité de solicitions entières données

par les formules » = »o + * "F» y = yo -t- A g^ ; et si Ton sup-

pose, ce qui est toujours permis, qtte œ^ est plus petit que -^t

on voit que a? a 8 valeurs incongrues suivant le mbdule m,

«^o> ^o + -§» a?o + -3*v..->a?o-*-(5— Ij-g-

Ce sont les racines de la congruence proposée.

'£n particulier, si le module est un nombre premier p et que a ne soit pas divisible parp, la congruence oa? -+- è s 0 (mod. p) a toujours une racine et une seule.

' 98. Théorème de Fermât. — On eût pu baser l'exposé théorique qui précède sur la proposition suivante, dont nous déduirons d'ailleurs le théorème de Fermât.

Théorème. — Soient h un nombre entier quelconque, a et m 'âeuœ nombres entiers premiers entre etMB, il y a toujours parmi Qbs m nombres suivants, congrus par rapport au module a,

b, b + a, b + 2a, , bH-(m — i)a,

jun nombre et un seul^ qui soit congru à un nombre donné A.

Mn effet, tous ces nombres sont incongrus relativement à m, «HT la différence entre deux d'entre eux est de la forme ha^ h distant un nombre entier plus petit que m ; cette différence ne peut donc être divisible dans aucun cas par le nombre m, puisque m est premier avec a. Donc les restes de tous ces nombres relaiii^ement au module m, sont distincts, et, comme ils sont au nombre de m, ce ne peut être que les m restes des divisions par

.iM, 0,1,2, , m — 1 , ces restes étant d'ailleurs écrits dans

«mixcèrtain ordre. Le reste de A se trouve forcément dans cette aaile ; donc il y a sûrement l'un des nombres proposés qui admet le même reste que A, c'est-à-dire qui est congru à A.

11 résulte de là que l'un des nombres ax-^-b a pour reste 0^ iO'ffst-à-dire que la congruence du premier degré a une racine et \ seule, dans le cas où a et m sont premiers entre eux.

Théorème de Fermât. — Si p désigne un nombre premier ab-