CHAPITRE VL
DE LA œNGRUENCE DES NOMBRES. - THËORÈMES tLÉMENTlIBES.
S7. Le nombre positif m éunt pris pour module ou pour terme de comparaison, si pour un nombre quelconque a on pose
le nombre r, quels que soient son signe et sa grandeur, est dit réùdu de n pour le module m. Si le nombre q est déterminé de manière que r soit en valeur absolue inférieur à m, ce qui arrive quand mq est l'un des deux multiples consécutif de m, entre lesquels tombe a, on dit que r est un résidu minimum.
Le résidu minimum positif étant r, le nombre r — m=. — (m — r) est le résidu minimum négatif. La somme des valeus absotoes de ces deux résidus r et m — r est donc «i. Quand m esiviultiple de n», il n*y a qu'un résidu minimum égal à zéro.
On dit que deux nombres sont congrus pour le module m, quand ils sont réductibles à une même forme nur+r, r étant an résidu qu'on prendra généralement minimum.
Les nombres n^=ma-\-r^ n' = m^ + r sont donc congras;cette congruence s'exprime ainsi
nmsn! mod. m,
ce qui revient à l'équation
n — ii'=m(a — P),
qu'on peut mettre sous ces deux formes
n:=m[a — ^)-\-n' ou n' = m(P — a)-4-ii.
On peut donc dire indifféremment que nest résidu de n\ ou n' de n, pour le module m.
Tous les nombres sont compris dans les formules
Les nombres
forment un Bydtème de restes .
Comme les formules
mx-h m — i, mx-^m — 2, mx-^-m — 3...
reviennent à
/n(;rH-t) — I, m(jr?-Ht)— a, m(ar-Hi)- — 3,...,
on peut dire qtie^ pour avoi^ tous les nombres possibles, il suf&t de considérer m formules consécutives parmi les suivantes :
... /ii«p— 2, ntx — I, mXf /iw?H-i, iiiia?+*2,.,>
ex, si Ton prend m nombres consécutifs parmi les $uivw4s
on aura encore un système de résidus .
58. Au moyen de ces remarques on reconnaîtra tout de suite la vérité des propositions suivantes :
Théorèmbs. — Les nombres congrus à un même nombre sont conn grus entre eux. Les nombres congrus suivant le module n le sont aussi suivant les diviseurs de m. Les nombres congrus suivant les tnodules m, m', m'',..., premiers entre eUx deux à deux, le sont suivant fe produit m m' m*". . . .
Si Von a
ka^kb mod. m ou A-(a— ^6)^omôd.iyt/ '
et que k soit premier à m, on aura
assb mod.^m, "' * * »'
car a — b est divisible t)ar m.
Théorème. — Si l'on a
a^(Xf bss^f c^y,. . . mod.m, < ?
on aura aussi pour le module m a±*^a±(3, rt-f-6-f-cîsa-f-(3-hy, a*ssa*, abc.^a^y...
Généralement, si
sont des fonctions entières à coefficients entiers, on aura
¥{a)&¥(a)y F(a, 6)sF(a,3), F(a, 6,c)ffiaF(a, j3, y). .. mod. m.
Démonstration. — On le voit immédiatement en remplaçant
a^a, bss^y c^y, mod.m par
a = (X'^mg, b = ^'-\-mg^, c=.y'\-m^.
Théorème. — Si dans F {x) on met pour x la suite des nombres entiers et qu'on prenne les résidus minima, ils se reproduiront périodequement : ce seront les restes de
le module étant m.
Corollaire, — Si le reste r ne se présente pas, la congruence Y[x)^r est impossible.
S9. Gauss se proposait de développer ce caractère d'impossibilité dans la huitième section de ses Recherches arithmétiques* On peut présumer qu'il voulait aussi parler de Timpossibilité des équations indéterminées à plusieurs inconnues.
Quand F(^, r, -3...) = ^ P^"'' ^®s valeurs entières a: = a, y = b, !z = r. . . , à plus forte raison la coiigruence ,
F {x,y,z..,)mor
a lieu pour un module quelconque. Donc si, pour un module convenablement choisi, la congruence est impossible, on en devra conclure l'impossibilité de l'équation E(^, j, 2.. .) = o. Pour le cas de F [x), Gauss prend l'exemple
F (jr)=x>— 8^-1-6;
alorsi pour le module 5, on a
F{o) = i, F(i)^4, F(:>.)s3, F(3)s4, F(4)s3; on aurait pu prendre F (—2), F(— I), F(o), F{i), F (2) ou 4, 3, I, 4, 3.
IMPOSSIBILITÉ PAR ï(ON-GONGRUSPÏGE. 71
Comme les restes o el 2 ne se présenleol pas, on voit qu'on ne saurait résoudre en nombres entiers les congruences
x^ — 8^-4-6^0, x^ — 8^4-6^ 2 mod. 5,
et par suite les équations
Voici d'autres exemples d'impossibilité, souvent employée :' Les congruences
^2^2, 3, 4> 5, 6, 7, mod. 8 sont impossibles; autrement, un carré ne saurait avoir les formes
SA-H-a, 8k-\-\ SA'-hS, 8A--^6, 8A--h7.
De même les congruences
x^^iy 3, 5, 6, 7, 8, 10, 11, mod. 12 sont impossibles; autrement,, il n'y a pas de carré des formes
i2/r-|-2, 3, 5, 6, 7, 8, 10, II, et ainsi de suite pour tous les modules.
Théorème. — L'équation x^ -{- y* c=: z^ est impossible en nombres entiers quand l'inconnue paire n'est pas divisible par 4*
Démonstration. — Il suffit da montrer qu'elle est impossible pour certains modules, c'est ce qui se fait comme il suit :
I" On peut supposer que x et j n'ont aucun facteur commun^' car s'il existait, on le ferait disparaître par la division. Par suite, x et 2, yel z n'en auront pas non plus.
2° Les nombres ^, j, z ne sont pas tous impairs, car si cela était,, un membre serait pair et l'autre impair; il n'y aurait pas congru ence pour le module 2.
3° Un seul des nombres x,x, z peut être pair et ce n'est pas z, car il n'y aurait pas, pour 2; pair, congruence pour le module 4> le premier membre ayant la forme 4^-4- 2, et le second la forme ^k.
4'' Soit X pair; il y aura impossibilité pour x double d'un impair/?. Dans ce cas, xz=ip donne
16;?* = z'—y^ =(2— j') {z -t-r'); comme les facteurs z — x\ z -}-/' ont pour somme 22, et pour dif-
72 llITAOVUCTIOn 4 LA Utf (MUB JIM MOBBEBS.
férence 27^, leur plus grand commun diviseur esl ft;<iD devra dduc poser
et de là, par soustraction,
11 faudra prendre le signe supérieur pour que les deux JB^eminres soient de la même forme 4 ^ + 1 ; on a donc
équation impossible, le premier membre ayant la forme SA* + 4 et le second la forme 8/.
Théorème. — L'équation
X étant impair, se ramène à l'équation
de sorte qu'en définitive on retombe sur le cas précédent, et l'imrpossibilité est généralement démontrée.
Démonstration. — Soit
x=pq\ ri^p'q' = {z±x^){z^:j^).
De li
T^p* = z ±x^9 2*^' }• = 2 ;f:j*; d'où p* — 2*«-'g* =:±/». 11 faut prendre le signe supérieur, et ToA a
pi — ^ = a«^«g«.
Delà
eo, prenant
q = rSy D(ry s) = i.
L'addition donne
1^= r^-hiià^-'sY; donc, etc.
Remarque. — Euler, dans son Algèbre, démontre l'impossibilité de réquation j:r*-h j* = 2'paruneméthode dite de Fermât et qui consiste à montrer qu'une solution en nombres positifs conduirait à une autre solution en nombres plus petits, et ainsi de suite à Tinfini, ce qui implique contradiction. Les transformations sont basées sur la réso-
iWPOSKBIfiVrtCMhàH MOK-00!fOACBIfCS. ^3
luUon de l'éq«ali<Mi
Il est vrai qu'elle est toujours possible, puisque . . ».
est une Mémîté, niais éetà suppose que x, y, z nç sont pas spumistà certaines restrictions. Ainsi quand on aura prouvé, comme plus haut, qu'une seule des inconnues est paire, ^l que cette inconnue paire x est double d'un impair, l'impossibilité sera démontrée, car alors
n'est pas même une congruence pour le modulé 8, le premier membre ayant la forme 8 A* + 4 ^t le second la forme 8/.
Puisque dans la méthode dite de Fermât on part d'une splmiotn supposée existante et çn noàibres entiers, il est impossible que les solutions en nombres décroissants se prolongent à l'infini. Quand un examen plus approfondi fera voir le point où }e^ iran^foirmîiUoi^? cessent d'être praticables, l'impossibilité sera prouvée si les transformations employées sont seules possibles. ï)ans le cas présent, la méthode de Fermât revient à la précédente qu'on peut nommer méthode de non-congruence [F. Y Algèbre d'Euler, ch^ i4).
Une conséquence de l'impossibilité de a:*-+-/*=z* est celle dfe x*+f* = u\ Fermât a avancé que pourm>2 Téquation a:^-f-jj^=z'» est impossible. Cette proposition n'a pas encore été démontrée généralement. Les cas les plus simples peuvent s'établir par la méthode de non-congruence, qui consiste à établir qu'il n'y a pas congruence pour un module convenablement choisi et par suite qu'il n'y «r pt^ égalité.
Pour le cas de l'exposant pair, on peut généraliser et ramener l'impossibilité de l'équation
à celle de
le nombre m étant impair.
74 I^TRODICTIO?! % Li THCOtfC %ti XOXBRES.
Théorème de Fermai. — Ses conséquences.
40. La proposition suivante, due à Fermât, est remarquable par ses nombreuses conséquences.
Théorème. — Pour le nombre premier P on a, quand a n'est pas divisible par P, «**""' ai i mod. P.
Démonsi ration. — i" Dans le développement de (tf -+- 1 )** tous les termes, sauf le premier et le dernier, sont multiples de P, parce que
— ^ ^-^— ^^ — ; ' est multiple de P. On aura donc
(a-^ifsa^-hi mod.P, ou
(a-l-i)P(a-4-i)sa'— fl mod.P.
Or pour a = I le second membre i^— i est divisible par P, donc 2^ — aTestaussi; puis en posant a=a, on aura S^t- 3 divisible par P, et ainsi de suite.
On a généralement a^ — a = «(«'"• — i) divisible par P, et comme a ne Test pas, ce sera a*^'— i; on a donc «**■"• as i mod.P.
i"" La formule du polynôme donne semblablement
(^a-^ b-h c -^ d . . .f = a^ -^ b^ -h c^ -^ d^ -h. . . mod.P.
Faisant a = b=c=zd...=zi,\e nombre des termes étant A", on aura
A^fs**, ou *«•-=! mod.P.
Ces deux démonstrations sont dXuler;' en voici une troisième de Gauss.
3* Prenez les multiples de a,
a, 2rt, 3fl,.. , (P^-i)tf, divisez-les par P, et soient
''i, r-if Tj, . . ., 'V— >*
les restes, ils seront différents et formeront à Tonlre près la suite I, 2, 3,. . ., P I.
Car, si Ton avait /Vï = P^-f-r„ ya= Pç'H-ry et ri = rj^ il viendrait {' — j)^ divisible par P, ce qui est impossible; les restes sont donc différents.
Si Ton multiplie membre à membre les P — i équations qui ge tirent de /« = P^-f-r, en donnant à îles valeurs i,2,3...P — i, on trouvera, en négligeant les multiples de P dans le piroduit des seconds membres,
i,2.3...(P— i)^ïP~»si.2.3...P— I mod.P,
et par suite a^-* ^ I mod.P, parce que i.a.S. . .(P'—*i) n'est pas divisible par P^
ïlemar^ùe. — Les restes r et P — r sont dits complémentaires; ils ne peuvent se présenter dans. la suite -
'i» A, n, ...» rp^
car /a^ret jfa^P — r donnent (/-f-jf) a ^o mod.P ou i-i-j multiple de P, ce qui est impossible quand i et j appartieiinent 'à la
suite I, 2, 3, . . ., .
41. Cette dernière démonstration s'applique à la proposition suivante, généralisfition du théorème fte Fermait.
Théorème. — Lorsque di est premier à m, on a
, av '^i mod.m. }
Démonstration. — Soient i, a, ^,. . ., X, (x, les 9 (m) nombres inférieurs et premiers à m; les restes des produits
1. 1 ■ divisés par m seront différents et formerçut, à Tordre près, la suite I, a,.., [i, d'où l'on conclura, comme plus haut, que l'on a
^pw^ I mod. m.
Cette généralisation est d'Euler.
Il est utile de remarquer le cas particulier suivant :
Pour m = P^ on a, quand P ne divise pas a, ^P«-\P^O=i mod.P^ Si a = I , on retombe sur le théorème de Fermai.
^6 UmO^CCTHNI Jk LA TflÉOHi MS XOMMIS.
Remmrqme. — Coomie a ' — i = \a * — «/\* * "♦*"/» <» • rime des eongroences
a ' BEI, a ' ^ — I bmmI.P.
La suite inooirera l'atililé d'une règle pntiqae pour ssToir si le reste
de a ' diTisé psr P est + i ou — i .
4t. TstosÈBi. — Si panm les rtties de$ i
a, aa, 3a,... f I^ja,
divisés par f, Uy em an fmi tmrpassemi- « om ammt
a '-^ =(—!)• niod.P.
MmoasiFoiiom. — Soient les restes n^ r^... rp,; comme ils
ne contiennent pas de restes complémentaires, en rempbçant p 1
r.> par P — (P— n) = P — js» on aura
de sorte que les nombres r^y ra^ jry,. . . , non supérieurs à 9 et
les nombres pt» px^..>»p« inférieurs à : seront à Tordre prèi
on aura donc
r». r.. Tj. ..rp, ^1.1.3 . . . ( — «)* mod.P.
Mais comme on a
il en résultera ''
a ^ s(— 1)% mod.P. . ^ .
Cette propositljipn est de Gauss.
Tbéorèhe. — Pour a:^i, on a
"=^-(^): , , :, et par suite
2 ^ ssi^. mqd.P, pour P=:8Kdbi»
2 ^ SI, mod.P, ;70Mr P = 8K±3, ce qui revient à * ^ . .\ -. , . n ^ ; . *î • \ ' '
2 ^ ^( — i)"^, mod.P.
Si Ton pose P = 49±ï> ow a encore
2 ^ s(— i)^, mod.P.
Démonstration. — Les produits^, la^ 3^,...^| . a • sont,
pour a= 2, égaux à 2, 4, 6,...,P — i. Les restes r», Ta,... ne diffèrent pas de ces produits et vont en croissant rie premier reste 20: qui surpasse
e?t donné par l'inégalité
2a?> ! ou X^ 3—9
le nombre des restes plus grand que est donc
Si P = 4ç-M,
ii = 2<7 — ç=ç; P=4ç — I donne
78 nTR(»DlCT10K A LÀ THÊOMS »tS NOMBRES.
on a donc, pour P = 47±i,
p— 1 2 ^ «; — i)f, mod.P.
Comme — rt — =^^q^zizq 01 ^q- — q=zn{q^ — q)'^q^ on aura
9^— rr — mod.2 ei 2 «f^—i) ° , inod.P.
Remarque. — Cesl dans la théorie de Téqualion x^=a-h Vy qu'il convient de transformer la >'aleur de n qui donne
P-i a ^ s— i)-, mod.P.
11 suffit de dire ici qu'en supposant a positif et inférieur à P^ la
vraie valeur de n, ou le nombre des restes de a, aa, 3a,..., ( J a
supérieurs à 9 est donnée par la proposition qui suit :
Théoaème. — Si le nombre positif a <C^ P est égal à 2a -f- r, r étant o ou i, selon que a est pair ou impair^ on aura
Démonstration. — Elle est analogue à celle donnée pour a = 2. Cas particuliers. — Pour a = 2, on a a == i , r= o, et
. = -E(j').E(|)=ti-E(|).
ce qui s'accorde avec ce qui précède, car E(-Y) = Ef— ^^j- Pour /i = 3, on a a = i , r= 1 , et
Pour a = 5, on a a = 2, /'= 1, ei : ■ • • i. i, ,;.j
= E(|).B(-)-[K(±)H-B(i^)], et ainsi de suite.
45. Voici un théorème qui fait connaître les restes des sommes
Théorème. — Lorsque. m est multiple de P — i , on a SmSsP — t mod. P et y dans le cas contraire, Sa^omod.P.
Démonstration. — Pour le premier cas, on a a^^^""')^! et, comme la somme S« a a P — i termes congrus à i, on aura
S«sP — I, mod.P.
Pour le second cas, on considère les équations - '
^^x[x-\- i)(ar-H2) = ^(^-4- i)(x + i){x -\^i)'
{V — i)lx(x-^i)...{x-^V—Z) = x{x^i) ..(^ + P — 2) P2^(j?-4-ï)...(^-f-P— 2) = ^(^-Hi)..i(a?-hP — i).
Si Ton pose
^ = P — I, ou^H-i=P,
la première équation donne
2(P i)==S,so, mod.P,*
puis la seconde, qui revient à
32^'-+- 32^ = ^(j?rH 0(^-4-2), donne
2^^ = 2(P— ir = S„
divisible par P, puisque 2^ Test aussi, de même que le deuxième
8o IimODUCTION A LA THÉOUI Mi IIOMMBS.
membre; ei ainsi de suite jusqu'à ravant-dernière équation qui donne
S(p,)So, mod.P.
En général, m = g( P — i ) -4- r donne
(Tsar el S,sSr, mod.P.
Remarque. — Les équations précédentes pourraient faire connaître les valeurs exactes des sommes. On a
et ainsi de suite» les formules se compliquant de plus en plus.
Théorème de WiUon.
