Courant Robbins Chap1 4mars15

7/25/2019 Courant Robbins Chap1 4mars15

1/60

CHAPITRE PREMIER

LES NOMBRES NATURELS

Introduction

Le nombre est la base des mathmatiques modernes. Mais quest-cequun nombre ? Quest-ce que cela signifie de dire que 1

2

C 1

2

D 1, que12

12

D 14

et que .1/.1/ D 1 ? On nous apprend lcole manipu-ler les fractions et les nombres ngatifs, mais si lon veut rellement com-prendre le systme des nombres, on doit revenir aux lments les plussimples. Alors que les Grecs ont choisi les notions gomtriques de pointet de droite comme base de leurs mathmatiques, le principe directeur ad-mis aujourdhui est que tout nonc mathmatique doit en fin de comptetre rductible des noncs sur lesnombres naturels 1,1,2,3; : : : Dieua fait les entiers, les hommes ont fait le reste . Par ces mots, Leopold

Kronecker (1823-1891) dsignait les fondements sur lesquels les math-matiques ont pu se structurer.

Crs par lesprit humain pour compter les objets de toutes sortesdassemblages, les nombres nont aucun lien avec les proprits des objetscompts. Le nombre six est une abstraction de toutes les collections desix choses ; il ne dpend en rien des qualits spcifiques de ces choses, nides symboles utiliss. Ce nest qu un stade avanc du dveloppementintellectuel quon ralise le caractre abstrait de lide de nombre. Pour

les enfants, les nombres sont constamment associs des objets tangiblescomme les doigts ou les billes, et les langues primitives tmoignent duneconception concrte du nombre lorsquelles utilisent des mots-nombresdiffrents pour compter des objets de natures diffrentes.

Heureusement, le mathmaticien na pas se proccuper de la naturephilosophique de la correspondance entre les ensembles dobjets concretset la notion abstraite de nombre. Nous allons par consquent admettre lesnombres naturels comme donns, ainsi que les deux oprations fondamen-tales, laddition et la multiplication, qui permettent de les combiner.

Les notes marques dun astrisque sont dues aux auteurs. Des notes numrotes1, 2... ont t ajoutes par Ian Stewart loccasion de la rdition de 1996 et par lestraductrices loccasion de la traduction franaise. Elles sont regroupes en fin de chapitre

17


2/60

18 chapitre i. les nombres naturels

1. Calcul avec des nombres entiers

1. Les lois de larithmtique

La thorie mathmatique des nombres naturels ouentiers naturelsestconnue sous le nom darithmtique.Cette thorie repose sur le fait queladdition et la multiplication des entiers sont gouvernes par certaineslois. Pour noncer ces lois en toute gnralit, on ne peut recourir dessymboles tels que 1, 2, 3 qui font rfrence des entiers particuliers.Lnonc

1 C 2 D 2 C 1

nest quun cas particulier de la loi gnrale selon laquelle la somme de

deux entiers est la mme quel que soit lordre dans lequel on les considre.Cest pourquoi si lon veut exprimer le fait quune certaine relation entreentiers est vraie indpendamment de la valeur de ces entiers, on lesreprsentera de faon symbolique par les lettres a,b ,c; : : : On peut dslors noncer cinq lois fondamentales de larithmtique bien connues dulecteur :

1/ a C b D b C a; 2/ ab D ba;

3/ a C .b C c/ D .a C b/ C c; 4/ a.bc/ D .ab/c;

5/ a.b C c/ D ab C ac

Les deux premires traduisent la commutativit de laddition et dela multiplication, et affirment que lon peut changer lordre des termesdune addition ou dune multiplication. La troisime traduit lassociativitde laddition, et affirme que laddition de trois nombres donne le mmersultat que lon ajoute au premier la somme du deuxime et du troisime,ou au troisime la somme du premier et du deuxime. La quatrime

traduit lassociativit de la multiplication. La dernire, la distributivit,exprime le fait que pour multiplier une somme par un entier on peutmultiplier chaque terme de la somme par cet entier, puis additionner lesproduits obtenus.

Ces lois de larithmtique sont trs simples et peuvent sembler vi-dentes. Mais elles pourraient ne pas tre applicables des entits autresque des entiers. Siaet b sont des symboles ne dsignant pas des entiers,mais des substances chimiques, et si lon utilise le mot addition dans

son sens courant (action dajouter), il est bien vident que la commuta-tivit ne sera pas toujours vrifie. Si par exemple, on ajoute de lacidesulfurique de leau, on obtient une solution dilue, mais laddition deau de lacide sulfurique pur peut provoquer une catastrophe. On pourrait


3/60

[1,1] les lois de larithmtique 19

trouver dautres exemples du mme genre invalidant lassociativit et ladistributivit dans cette arithmtique chimique. Mais on peut aussi ima-giner des systmes arithmtiques, de nature mathmatique cette fois, danslesquels une ou plusieurs des lois 1) 5) ne seraient plus vrifies. De telssystmes sont dailleurs tudis dans les mathmatiques modernes.

Un modle concret de la notion abstraite dentier nous aidera com-prendre sur quelles bases intuitives reposent les lois 1) 5). Au lieu duti-liser les symboles numriques habituels1,2,3, etc., reprsentons lentiercorrespondant au nombre dobjets dune collection donne (comme la col-lection des pommes dun arbre particulier) par un ensemble de pointsdans une bote rectangulaire , un point pour chaque objet. On peut, enmanipulant ces botes, explorer les lois de larithmtique des entiers. Pour

additionner deux entiersaetb, on place bout--bout les botes correspon-dantes et on supprime la ligne qui les spare.

+ =

Fig.1. Addition.

=+

Fig.2. Multiplication.

Pour multiplieraetbon empilealignes comportant chacunebpoints,formant ainsi une nouvelle bote rectangulaire dealignes et bcolonnes.

Il apparat alors que les rgles 1) 5) correspondent aux propritsintuitives de ces oprations avec des botes.

=( + )+

Fig.3. Distributivit.

partir de la dfinition de laddition de deux entiers, on peut dfinirla relation dingalit.Chacun des noncs quivalentsa < b(lire aestinfrieur b) etb > a(lire best suprieur a) signifie que lon peutobtenir la bote b partir de la bote aen ajoutant cette dernire une


4/60


troisime botec convenablement choisie, de sorte queb D a C c. Si telest le cas on crira

c D b a;

ce qui dfinit lopration desoustraction.

=

Fig.4. Soustraction.

On dit que laddition et la soustraction sont des oprations inverses,puisque si lon ajoute lentier d lentier a, et quensuite on soustraitlentierd, on retrouve lentierade dpart :

.a C d / d D a:

Remarquons que nous navons dfini lentier b a que dans le cas ob > a. Nous reviendrons sur linterprtation du symbole b a commeentier ngatif, dans le cas ob < a(p. 80 et suivantes).

Pour exprimer la ngation de lnonca > b, on utilise souvent lunedes deux notations suivantes : b > a(lire best suprieur ou gal a)oua 6 b(lire aest infrieur ou gal b). Ainsi,2 > 2et3 > 2.

On peut tendre un peu le domaine des entiers positifs reprsentspar des botes de points, en introduisant lentierzroet en le reprsentantpar une bote compltement vide. Si lon dsigne cette bote vide parle symbole habituel 0, alors, selon notre dfinition de laddition et de lamultiplication,

a C 0 D a

a 0 D 0;

pour tout entier a. En effet, a C 0correspond laddition dune botevide la bote a, tandis que a 0correspond une bote sans colonne,cest--dire une bote vide. Il est alors naturel dtendre la dfinition de lasoustraction en posant

a aD 0

pour tout entier a. Telles sont les proprits arithmtiques caractris-tiques de zro.

Jusqu une priode tardive du Moyen ge, on sest beaucoup servi

de modles gomtriques similaires ces botes de points, tels les anciensabaques, pour le calcul numrique. Ces modles furent progressivementremplacs par des mthodes symboliques bien suprieures, fondes sur lesystme dcimal.


5/60

[1,2] la reprsentation des entiers 21

2. La reprsentation des entiers

Il faut faire attention bien distinguer un entier du symbole,5, V; : : : ,utilis pour le reprsenter. Dans le systme dcimal, les dix symboles nu-

mriques 0, 1, 2, 3; : : : ; 9, appels chiffres, sont utiliss pour reprsen-ter zro et les neuf premiers entiers positifs. Un entier plus grand, parexemple trois cent soixante-douze , sexprime sous la forme

300 C 70 C 2 D 3 102 C 7 10 C 2

et on le reprsente par le symbole372dans le systme dcimal. Le pointimportant ici est que la signification des symboles numriques 3, 7, 2dpend de leurposition: place des centaines, place des dizaines, place des

units. Cette notation positionnelle permet de reprsenter nimportequel entier en ne se servant que de dix symboles numriques combinsdiffremment. En rgle gnrale un entier zpeut scrire sous une formedu genre

z D a 103 C b 102 C c 10 C d;

oa,b ,c ,ddsignent des entiers un chiffre, de zro neuf. Lentier zest alors reprsent par le symbole abrg

abcd:

Remarquons au passage que les coefficients d, c, b, a sont les restesobtenus dans les divisions successives de zpar 10. Ainsi

372 divis par 10 : quotient 37, reste 237 divis par 10 : quotient 3, reste 7

3 divis par 10 : quotient 0, reste 3

Lcriture de lentier z donne ci-dessus est particulire, elle ne peutreprsenter que des entiers infrieurs dix mille, puisque des entiers plusgrands ncessiteront cinq symboles numriques ou plus. Si zest un entiercompris entre dix mille et cent mille, on peut lcrire sous la forme

z D a 104 C b 103 C c 102 C d 10 C e;

et le reprsenter par le symbole abcde. On peut tablir un nonc sem-blable pour les entiers compris entre cent mille et un million, etc. Mais il

serait prfrable de disposer dune formule gnrale permettant de repr-senter nimporte quel nombre. Pour cela, on remplace les diffrents coeffi-cients,e,d,c; : : : par la seule lettreaaffecte de diffrents indices ,a0,a1,a2,a3; : : : ;et lon indique le fait que les puissances de 10peuvent tre


6/60


aussi grandes que lon veut en dsignant la plus grande, non par 103 ou104 comme dans les exemples ci-dessus, mais par 10n, o n est un entierarbitraire. La mthode gnrale de reprsentation dun entier z dans lesystme dcimal consiste donc lcrire sous la forme

(1) z D an 10n C an1 10

n1 C C a1 10 C a0;

et le reprsenter par le symbole

anan1an2: : : a1a0:

Comme dans le cas particulier ci-dessus, on peut remarquer que a0, a1,a2; : : : ; ansont simplement les restes des divisions successives dezpar10.

Dans le systme dcimal, on choisit le nombre dix comme base. Maisle dbutant ne sait pas que ce choix de dix nest pas obligatoire, et quetout entier suprieur un peut jouer le mme rle. On pourrait parexemple utiliser le systme septimal (base sept). Dans ce systme, unentier sexprime de la faon suivante

(2) bn 7n C bn1 7

n1 C C b1 7 C b0;

o lesb indics sont des nombres un chiffre de zro six, et cet entierest reprsent par le symbole

bnbn1bn2: : : b1b0:

Ainsi cent neuf serait reprsent dans le systme septimal par lesymbole 214, signifiant

2 72 C 1 7 C 4:

Le lecteur pourra dmontrer, en exercice, que pour passer de la base dix

nimporte quelle autre base B, il suffit deffectuer les divisions successivesdu nombrezpar B. Les restes de ces divisions donneront les chiffres dunombre crit dans le systme de base B. Par exemple :

109 divis par 7 : quotient 15, reste 415 divis par 7 : quotient 2, reste 1

2 divis par 7 : quotient 0, reste 2109(systme dcimal) D 214 (systme septimal)

Il est naturel de se demander comment choisir le plus judicieusementla base. Nous verrons quune base trop petite a des inconvnients, etquune grande base ncessite un grand nombre de chiffres et tend consi-drablement les tables de multiplication. On a dfendu le choix de la base


7/60

[1,3] calcul dans des systmes autres que le systme dcimal 23

douze en invoquant le fait que douze est divisible par deux, trois, quatreet six, et que par consquent, les divisions et les calculs sur les fractionsseraient souvent plus simples. Pour crire un entier en base douze (sys-tme duodcimal), on a besoin de deux symboles numriques pour dix etonze. crivons pour dix et pour onze. Dans le systme duodcimal douze scrit donc 10, vingt-deux 1, vingt-trois , 1, et centtrente et un ,.

Linvention de la notation de position, attribue aux Sumriens ou auxBabyloniens et dveloppe par les Hindous, a eu dnormes consquences.Les premiers systmes de numration taient fonds sur un principeexclusivement additif. Dans le systme romain, par exemple, on crit

CXVIII D cent C dix C cinq C un C un C un:Les systmes gyptien, hbreu, et grec taient du mme genre. Lundes inconvnients de toute notation exclusivement additive est que plusles nombres sont grands, plus on doit introduire de nouveaux chiffres.(Bien sr, les savants de lAntiquit navaient pas affaire aux ordres degrandeur quon rencontre aujourdhui en astronomie ou en physiqueatomique.) Mais le principal dfaut des anciens systmes, tels que celuides Romains, tait que le calcul sur des nombres tait si difficile quil

fallait tre un spcialiste, mme pour traiter les problmes les plus simples.Tout cela est bien diffrent avec le systme positionnel indien que nousutilisons aujourdhui. Ce systme fut introduit en Europe mdivale pardes marchands venus dItalie, qui lavaient appris des Musulmans. Il alavantage de permettre de reprsenter tous les nombres, petits et grands, partir dun ensemble restreint de symboles numriques diffrents (dansle systme dcimal, il sagit des chiffres arabes 0, 1, 2; : : : ; 9). Mais ilprsente un plus grand avantage encore : la facilit des calculs. Les rglesde calcul sur les nombres crits en notation de position peuvent snoncersous forme de tables daddition et de multiplication des chiffres utilissdans ce systme, que lon peut mmoriser une fois pour toutes. Lancienart du calcul, jadis limit quelques experts, est aujourdhui enseign dansles coles lmentaires. Rares sont les exemples o le progrs scientifiquea si profondment boulevers et facilit la vie quotidienne.

3. Calcul dans des systmes autres que le systme dcimal

Lutilisation de la base dix remonte laube de la civilisation et estsans aucun doute due au fait que nous comptons avec nos dix doigts. Maisdans de nombreuses langues, les mots dsignant les nombres tmoignentdune utilisation ancienne dautres bases, en particulier le nombre 12et


8/60


le nombre20. En anglais et en allemand, les mots pour 11 et 12ne sontpas construits daprs le principe dcimal de la combinaison de 10avecdautres chiffres, comme cest le cas pour les autres nombres de cettedizaine, et ils sont linguistiquement indpendants des mots dsignant 10.En franais, les mots vingt et quatre-vingts pour20et80suggrentquun systme de base vingt a pu tre utilis. En danois, le mot dsignant70, halvfirsindstyve signifie mi-chemin de (trois fois ) quatre foisvingt. Les astronomes babyloniens possdaient un systme de notationqui tait partiellement sexagsimal (base soixante), et lon pense que celaexplique la division bien connue des heures et des angles en soixanteminutes.

Dans un systme diffrent du systme dcimal, les rgles de larith-

mtique sont les mmes, mais on doit utiliser des tables diffrentes pourladdition et la multiplication des chiffres . Nous sommes habitus ausystme dcimal et attachs ce systme par les mots de notre langue d-signant les nombres, cela peut donc tre un peu droutant. Essayons defaire une multiplication dans le systme septimal. Avant de le faire, il estrecommand dcrire les tables que nous aurons utiliser :

Addition1 2 3 4 5 6

1 2 3 4 5 6 102 3 4 5 6 10 11

3 4 5 6 10 11 12

4 5 6 10 11 12 13

5 6 10 11 12 13 14

6 10 11 12 13 14 15

Multiplication1 2 3 4 5 6

1 1 2 3 4 5 62 2 4 6 11 13 15

3 3 6 12 15 21 24

4 4 11 15 22 26 33

5 5 13 21 26 34 42

6 6 15 24 33 42 51

Multiplions maintenant265par24, o ces symboles numriques sontcrits dans le systme septimal. (Dans le systme dcimal cela reviendrait

multiplier145par18.) Les rgles de multiplication sont les mmes quedans le systme dcimal. On commence par multiplier 5par4, ce produitvaut26comme lindique la table de multiplication.

265

24

1456

5 63

10 416

On crit6au rang des units, en retenant le2pour le rang suivant.On a ensuite 4 6 D 33, et 33 C 2 D 35. On crit 5, et on continue decette manire jusqu ce que tout ait t multipli. Pour additionner1 456


9/60

[1,3] calcul dans des systmes autres que le systme dcimal 25

et 5630, on a 6 C 0 D 6au rang des units, 5 C 3 D 11au rang desseptaines. On crit 1et on retient 1pour le rang des quarante-neuf, olon a1 C 6 C 4 D 14. Le rsultat final est que 265 24 D 10 416.

Pour vrifier ce rsultat, on peut multiplier les mmes nombres en lescrivant cette fois dans le systme dcimal. Pour crire 10 416(systmeseptimal) dans le systme dcimal, on calcule les quatre premires puis-sances de 7: 72 D 49, 73 D 343, 74 D 2401. Par consquent 10 416enbase sept est gal 2401 C 4 49 C 7 C 6en base dix. En additionnantces nombres, on trouve que 10 416 dans le systme septimal est gal 2610dans le systme dcimal. On multiplie prsent 145par 18dans lesystme dcimal. Le rsultat est2 610 ; les calculs taient donc justes.

Exercices.1) tablir les tables daddition et de multiplication dans le systme duodci-mal et faire quelques exercices du mme genre.

2) crire trente et cent trente-trois dans les systmes de base5,7,11,12.3) Que signifient les symboles11111et21212dans ces systmes ?4) tablir les tables daddition et de multiplication dans les bases 5,11,13.

Dun point de vue thorique, la base deux est la plus petite basepossible dun systme de notation de position. Les seuls chiffres de cesystme dyadiquesont0et1 ; tout nombrez est reprsent par une suitede 0et de 1. Les tables daddition et de multiplication se rduisent aux

deux rgles suivantes1 C 1 D 10et 1 1 D 1. Mais linconvnient de cesystme est vident : il faut de longues expressions pour reprsenter despetits nombres. Par exemple soixante-dix-neuf, que lon peut exprimersous la forme 1 26 C 0 25 C 0 24 C 1 23 C 1 22 C 1 2 C 1, scrit1 001 111dans le systme dyadique.

Pour montrer la simplicit de la multiplication dans le systme dya-dique, multiplions sept par cinq, ces nombres tant respectivement repr-sents par111et101. Si lon se souvient que1 C 1 D 10dans ce systme,on a

111

101

111

11 1

100 011 D 25 C 2 C 1

soit trente-cinq, comme il se doit.Gottfried Wilhelm Leibniz (1646-1716), lun des plus grands intellec-

tuels de son temps, adorait le systme dyadique. Pour citer Laplace : Cefut ainsi que Leibnitz crut voir limage de la cration, dans son Arithm-tique binaire o il nemployait que les deux caractres zro et lunit. Ilimagina que lunit pouvait reprsenter Dieu ; et zro, le nant ; et que


10/60


ltre Suprme avait tir du nant, tous les tres, comme lunit avec lezro, exprime tous les nombres dans ce systme.

Exercice.Considrons le problme de la reprsentation des entiers en base a. Pour

nommer les entiers dans ce systme on a besoin de mots pour les symboles numriques0, 1; : : : ; a1et pour les diffrentes puissances de a : a, a2, a3; : : : Combien de motsdiffrents sont ncessaires pour nommer tous les nombres de zro mille, lorsque a D 2,3,4,5; : : : ; 15 ? Quelle base ncessite le plus petit nombre de mots ? (Exemples : sia D 10, ilnous faut dix mots pour les chiffres, plus des mots pour10,100et1000, ce qui fait un totalde treize mots. Sia D 20, on a besoin de vingt mots pour les chiffres, plus des mots pour 20et400, ce qui fait un total de vingt-deux. Si a D 100, on a besoin de cent un mots.)

*2. Linfinitude du systme des nombres. Linduction mathmatique

1. Le principe de linduction mathmatique

La suite des entiers1,2,3,4 : : : na pas de fin ; aprs avoir atteint unentiern, on peut crire lentier suivantn C 1. On exprime cette propritde la suite des entiers en disant quil existe une infinit dentiers. Lasuite des entiers est lexemple le plus simple et le plus naturel de linfini

mathmatique qui joue un rle considrable dans les mathmatiquesmodernes. Partout dans ce livre nous aurons utiliser des collections oudes ensembles contenant une infinit dobjets mathmatiques, commelensemble de tous les points dune droite ou lensemble de tous lestriangles dun plan. La suite infinie des entiers est lexemple le plus simpledun ensemble infini.

Le procd consistant passer, pas pas, de n nC 1, qui gnrela suite infinie des entiers, est la base de lun des schmas les plus fon-

damentaux du raisonnement mathmatique, le principe dinduction ma-thmatique. Linduction empirique des sciences naturelles conduit, partir dune suite dobservations particulires dun certain phnomne, lnonc dune loi gnrale gouvernant ce phnomne. Le degr de certi-tude avec lequel la loi est ainsi tablie dpend du nombre dobservationset de confirmations. Ce genre de raisonnement inductif est souvent totale-ment convaincant. Prdire que le soleil se lvera demain lest a peu dechance dtre contredit, mais la nature de cet nonc nest pas la mmeque celle dun thorme dmontr par un raisonnement strictement lo-gique ou mathmatique.

Dune manire trs diffrente, linduction mathmatique2 est employepour tablir la vrit dun thorme mathmatique dans une suite infinie


11/60

[2,1] le principe de linduction mathmatique 27

de cas, le premier, le deuxime, le troisime et ainsi de suite sans excep-tion. Dsignons par A un nonc dans lequel intervient un entiern arbi-traire. Par exemple, A pourrait tre lnonc la somme des angles dunpolygone convexe n C 2cts est gale nfois 180 . Ou encore A0

pourrait tre lassertion suivante en traantndroites dans un plan, onne peut pas diviser le plan en plus de2n parties . Pour dmontrer un telthorme pourtoutentiern, il ne suffit pas de le dmontrer pour les 10,les 100ou mme les 1000 premires valeurs de n, ce qui relverait delinduction empirique. On doit au contraire recourir une mthode deraisonnement strictement mathmatique et non empirique, dont la spci-ficit apparatra dans les dmonstrations des deux noncs particuliers Aet A0. Dans le cas de lnonc A, si n D 1, le polygone est un triangle,

et daprs la gomtrie lmentaire, la somme de ses angles est gale 1 180. Pour un quadrilatre, n D 2, on trace une diagonale qui le di-vise en deux triangles, ce qui montre immdiatement que la somme desangles dun quadrilatre est gal la somme des angles de deux triangles,et nous donne180 C 180 D 2 180. Passons au cas dun pentagone, ila cinq cts, n D 3, et dcomposons-le en un triangle et un quadrilatre.Puisque la somme des angles de ce dernier est 2 180, comme on vientde le dmontrer, et puisque la somme des angles du triangle est 180, onobtient3 180 pour le pentagone. Il est clair que lon peut continuer linfini de la mme manire, dmontrant le thorme pour n D 4, puispour n D 5, et ainsi de suite. Chaque nonc dcoule du prcdent dela mme manire, de sorte que le thorme gnral peut tre tabli pourtout entiern.

On peut, de mme, dmontrer le thorme A0. Pour n D 1, cestvident, puisquune droite divise le plan en deux parties. Ajoutons pr-sent une deuxime droite. Chacune des parties prcdentes sera diviseen deux nouvelles parties, moins que la nouvelle droite ne soit paral-

lle la premire. Dans tous les cas, pourn D 2, il ny aura pas plus que4 D 22 parties. Ajoutons maintenant une troisime droite. Chacun des do-maines prcdents sera divis en deux parties ou demeurera intact. Ainsila somme des parties ne sera pas plus grande que 22 2 D 23. Sachantque cela est vrai, on peut dmontrer le cas suivant de la mme manire, etainsi de suite linfini.

Lide essentielle qui se dgage des arguments prcdents est quonpeut tablir un thorme gnral A pour toute valeur de n, en dmontrant

successivement une suite de cas particuliers, A1, A2; : : :On peut faire cela deux conditions : a) il existe une mthode gnrale pour montrer que siun nonc Ar est vrai alors lnonc suivant, ArC1, estgalementvrai ; b)onsaitque le premier nonc A1est vrai. Que ces deux conditions soient


12/60


suffisantes pour tablir la vrit de tous les noncs A1, A2, A3; : : : estun principe logique aussi fondamental pour les mathmatiques que lesrgles classiques pour la logique aristotlicienne. Nous le formulerons dela faon suivante :

Supposons que nous voulions tablir une suite infinie de propositionsmathmatiques

A1; A2; A3; : : :

constituant, toutes ensemble, la proposition gnrale A.Supposons que :a) par un argument mathmatique on montre, r tant un entier arbitraire,que silassertion Ar est vraie, alors lassertion ArC1 lest aussi, et b) lapremire propositionA1 estvraie. Alors toutes les propositions de la suite

doivent tre vraies, etAest dmontr.On acceptera ce principe comme on accepte les rgles simples dela logique ordinaire, et comme un principe de base du raisonnementmathmatique. On peut en effet tablir la vrit de chaque nonc Anen commenant par lassertion b), selon laquelle A1 est vraie, puis enutilisant de manire rpte lassertion a) pour tablir successivement lavrit de A2, A3, A4et ainsi de suite jusqu atteindre lnonc An. Leprincipe dinduction mathmatique repose donc sur le fait quaprs toutentierr il en existe un autre, r C 1, et que tout entiernpeut tre atteint

en un nombre fini dtapes, partir de lentier 1.Le principe dinduction mathmatique est souvent appliqu dune fa-

on non explicite, ou simplement indiqu par un etc. ou et ainsi desuite trs informel. Cest particulirement frquent dans lenseignementlmentaire. Mais lusage explicite de largument inductif est indispen-sable pour des dmonstrations plus subtiles. Nous proposerons quelquesillustrations de ce principe simple mais non trivial.

2. La progression arithmtique

Quelle que soit la valeur de n, la somme 1C2C3C Cn des npremiers

entiers est gale n.n C 1/2

.Pour dmontrer ce thorme par inductionmathmatique, on doit montrer que pour tout n, lassertion An:

(1) 1 C 2 C 3 C C n D n.n C 1/

2

est vraie. a) Sir est un entier et si lnonc Arest vrai, cest--dire si

1 C 2 C 3 C C r D r.r C 1/

2;


13/60

[2,2] la progression arithmtique 29

alors, en additionnant .r C 1/ aux deux membres de cette galit, onobtient lgalit

1 C 2 C 3 C C r C .rC 1/ D r.rC 1/

2 C .r C 1/

D r.rC 1/ C 2.r C 1/

2D

.rC 1/.r C 2/

2;

qui est prcisment lnonc ArC1. b) il est clair que lnonc A1 estvrai, puisque 1 D 1 2

2 . Par consquent, selon le principe dinduction

mathmatique, lnonc Anest vrai pour toutn, ce quil fallait dmontrer.Dordinaire on dmontre ce rsultat en crivant la somme1 C 2 C 3 C

C nde deux faons diffrentes :

Sn D 1 C 2 C C .n 1/ C n

et

Sn D n C .n 1/ C C 2 C 1:

En additionnant ces deux sommes, on observe que chaque paire de nombres

de la mme colonne a pour somme n C 1, et, puisquil y a ncolonnes entout, il sensuit que

2Sn D n.n C 1/;

ce qui dmontre le rsultat.On peut immdiatement dduire de (1) la formule permettant de

calculer la somme des .n C 1/ premiers termes de toute progressionarithmtique,

(2) Pn D a C .a C d / C .a C 2d / C C .a C nd / D .n C 1/.2a C nd /

2:

En effet

Pn D .n C 1/a C .1 C 2 C C n/d D .n C 1/a Cn.n C 1/d

2

D 2.n C 1/a C n.n C 1/d2

D .n C 1/.2a C nd /2

:

Dans le cas oa D 0etd D 1, on retrouve (1).


14/60


3. La progression gomtrique

On peut procder dune manire similaire pour la progression gom-trique. On va dmontrer que pour toute valeur de n

(3) Gn D a C aq C aq2 C C aqn D a

1 qnC1

1 q:

(On suppose queq 6D 1, parce que sinon le dernier membre de (3) na pasde sens.)

Cette galit est vraie pourn D 1, en effet

G1 D a C aq D a.1 q2/

1 qD

a.1 q/.1 C q/

1 qD a.1 C q/:

Etsion suppose que

Gr D a C aq C C aqr D a

1 qrC1

1 q;

il sensuit que

GrC1 D .a C aq C C aqr/ C aqrC1 D Gr C aq

rC1

D a1 qrC1

1 qC aqrC1 D a

.1 qrC1/ C qrC1.1 q/

1 q

D a1 qrC1 C qrC1 qrC2

1 q

D a1 qrC2

1 q:

Ce qui est prcisment lgalit (3) dans le cas o n D r C 1, et achve ladmonstration.

Dans les manuels denseignement lmentaire, la dmonstration estgnralement faite de la faon suivante. Posons

Gn D a C aq C C aqn;

et multiplions chaque membre de cette galit parq, on obtient

qGn D aq C aq2 C C aqnC1:

Si lon soustrait membre membre chacune de ces galits, on obtient

Gn qGn D a aqnC1;

.1 q/Gn D a.1 qnC1/;

Gn D a1 qnC1

1 q:


15/60

[2,4] la somme des npremiers carrs 31

4. La somme des npremiers carrs

Une autre application intressante du principe dinduction math-matique permet dtablir la somme des n premiers carrs. En faisant

quelques essais, on vrifie que

(4) 12 C 22 C 32 C C n2 D n.n C 1/.2n C 1/

6;

du moins pour de petites valeurs de n, et lon peut imaginerque cetteformule reste vraie pour tout entier n. Pour dmontrer ce rsultat onutilise nouveau le principe dinduction mathmatique. On observe toutdabord quesilgalit An, ici lgalit (4), est vraie pour n D r , de sorte

que12 C 22 C 32 C C r2 D

r.r C 1/.2r C 1/

6;

alors, en ajoutant.r C 1/2 aux deux membres de cette galit, on obtient

12 C 22 C 32 C C r2 C .rC 1/2 D r.rC 1/.2rC 1/

6C .r C 1/2

D r.r C 1/.2rC 1/ C 6.rC 1/2

6

D .r C 1/r.2rC 1/ C 6.rC 1/

6D

.r C 1/.2r2 C 7rC 6/

6D

.rC 1/.r C 2/.2r C 3/

6;

qui est prcisment lgalit ArC1, puisquelle est obtenue en substituantr C 1ndans (4). Pour complter la dmonstration il suffit de vrifier quelgalit A1,

12 D 1.1 C 1/.2 C 1/

6;

est vraie. Lgalit Anest par consquent vraie pour tout entiern.On peut tablir des formules du mme genre pour des sommes depuissances dentiers plus grandes, 1k C 2k C 3k C C nk , k tant unentier positif. Le lecteur pourra sexercer en dmontrant par inductionmathmatique que

(5) 13 C 23 C 33 C C n3 Dhn.n C 1/

2

i2:

Il faut bien comprendre que le principe dinduction mathmatiquepermet dedmontrerla formule (5) une fois cette formule pose, mais ladmonstration nexplique pas comment on la obtenue. Pourquoi suppo-ser prcisment que la somme des npremiers cubes est gale n.nC


16/60


1/=22 plutt qun.n C 1/=32 ou .19n2 41n C 24/=2ou toute autreexpression du mme genre ? Ce nest pas parce que la dmonstration dunthorme consiste en lapplication de certaines rgles simples de logiquequil nexiste pas en mathmatiques une part de crativit dans le choixdes possibilits examiner. La question de lorigine delhypothse(5) re-lve dun domaine o aucune rgle gnrale nest donne ; cest l quelexprience, lanalogie et lintuition interviennent. Mais une fois lhypo-thse correcte formule, le principe dinduction mathmatique suffit sou-vent en fournir une dmonstration. Dans la mesure o cette dmonstra-tion ne nous dit rien sur la dcouverte de cette hypothse, il serait peut-tre plus correct de lappelervrification.

*5. Une ingalit importante

Dans un des chapitres suivants nous utiliserons lingalit

(6) .1 C p/n > 1 C np;

qui est vraie pour tout nombre p > 1 et tout entier npositif. (Nousanticipons ici, par souci de gnralit, lusage des nombres ngatifs etnon entiers en permettant p dtre un nombre suprieur 1. La

dmonstration du cas gnral est exactement la mme que celle du casopest un entier positif.) Utilisons, l encore, linduction mathmatique.

a)Silest vrai que .1 C p/r > 1 C rp, alors en multipliant les deuxmembres de cette ingalit par le nombre positif1 C p, on obtient

.1 C p/rC1 > 1 C rp C p C rp2:

Le terme positifrp2 ne fait que renforcer lingalit, de sorte que

.1 C p/rC1 > 1 C .r C 1/p;

ce qui montre que lingalit (6) est encore vraie pour lentier suivant,r C 1.

b) Il est vrai que .1 C p/1 > 1 C p, ce qui achve la dmonstrationdu fait que (6) est vraie pour tout entier n. La restriction aux nombresp > 1est essentielle. Si p < 1, alors1 C pest ngatif et largumentde a) ne tient plus, puisque si les deux membres dune ingalit sont

multiplis par une quantit ngative, le sens de lingalit est invers. (Parexemple, si lon multiplie les deux membres de lingalit 3 > 2par 1on obtient, si on ne change pas le sens de lingalit, 3 > 2qui est uneingalit fausse.)


17/60

[2, *6] la formule du binme 33

*6. La formule du binme

Il est souvent utile de disposer dune expression explicite pour la n-ime puissance dun binme,.a C b/n. Par un simple calcul on trouve que

pourn D 1,.a C b/1 D a C b;

pourn D 2,

.a C b/2 D .a C b/.a C b/ D a.a C b/ C b.a C b/ D a2 C 2ab C b2;

pourn D 3,

.a C b/3 D .a C b/.a C b/2

D a.a2 C 2ab C b2/ C b.a2 C 2ab C b2/

D a3 C 3a2b C 3ab2 C b3;

et ainsi de suite. Quelle loi gnrale de formation se cache derrire lesmots et ainsi de suite ? Regardons de quelle manire on a calcul.a C b/2. Puisque .a C b/2 D .a C b/.a C b/, on obtient lexpressiondveloppe de.a C b/2 en multipliant chaque terme de a C bpar a, puis

parb, et en additionnant les produits obtenus. On utilise le mme procdpour calculer .aC b/3 D .aC b/.aC b/2. On pourrait continuer de lamme manire et calculer .a C b/4, .a C b/5 et ainsi de suite linfini.Lexpression dveloppe de.a C b/n sera obtenue en multipliant chaqueterme de lexpression dveloppe de .aC b/n1 para, puis par b, et enadditionnant les produits obtenus, ce qui conduit au diagramme suivant :

a C b D a C b

.a C b/2 D a2 C 2ab C b2

.a C b/3 D a3 C 3a2b C 3ab2 C b3

.a C b/4 D a4 C 4a3b C 6a2b2 C 4ab3 C b4

qui nous donne immdiatement la loi gnrale de formation des coeffi-cients dans le dveloppement de.a C b/n. On construit un tableau trian-gulaire de nombres, en commenant par les coefficients1,1 de a C b, ettel que chaque nombre du triangle soit la somme des deux nombres situs


18/60


de part et dautre dans la ligne prcdente. Ce tableau est connu commeletriangle de Pascal.

1 1

1 2 11 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

1 7 21 35 35 21 7 1

Lan-ime ligne de ce tableau nous donne les coefficients du dveloppement

de .a C b/n suivant les puissances dcroissantes de a et les puissancescroissantes deb;ainsi

.a C b/7 D a7 C 7a6b C 21a5b2 C 35a4b3 C 35a3b4 C 21a2b5 C 7ab6 C b7:

En utilisant une notation concise dindices et dexposants, on peut dsi-gner les nombres de lan-ime ligne du triangle de Pascal par

C0n D 1; C1n; C

2n; C

3n; : : : ; C

n1n ; C

nn D 1:

Alors la formule gnrale pour.a C b/n pourra scrire

(7) .a C b/n D an C C1nan1b C C2na

n2b2 C C Cn1n abn1 C bn:

Selon la loi de formation du triangle de Pascal, on a

(8) Cin D Ci1n1 C C

in1:

Le lecteur expriment pourra, en exercice, utiliser cette relation et lesdeux rsultats suivants, C01 D C

11 D 1, pour montrer par induction

mathmatique que

(9) Cin D n.n 1/.n 2 / : : : . n i C 1/

1 2 3 : : : iD

n

i.n i /:

(Pour tout entier positifn, le symbolen(lire factoriellen) dsigne leproduit desnpremiers entiers :n D 1 2 3 : : : n. Il est galement pratique

de dfinir0 D 1, de sorte que (9) soit vraie pour i D 0et i D n.) Cetteforme explicite des coefficients du dveloppement binomial est parfoisappeleformule du binme(voir galement p. 485 et 535).


19/60

[2, *7] autres remarques sur linduction mathmatique 35

Exercices.Dmontrer, par induction mathmatique, que :

1) 11 2 C 12 3 C C

1n.n C 1/

D nn C 1 .

2) 1

2

C 2

22 C

3

23 C C

n

2n D2

n C 2

2n .

3)1 C 2q C 3q2 C C nqn1 D 1 .n C 1/qn C nqnC1

.1 q/2 .

4).1 C q/.1 C q2/.1 C q4/ : : : . 1 C q2n

/D 1 q2

nC1

1 q .

Trouver la somme des progressions gomtriques suivantes :

5) 11 C x2

C 1.1 C x2/2

C C 1.1 C x2/n

.

6)1 C x1 C x2

C x2

.1 C x2/2 C C x

n

.1 C x2/n.

7) x2 y2

x2 C y2 C

x2 y2

x2 C y2

2C C

x2 y2

x2 C y2

n.

En utilisant les formules (4) et (5) dmontrer que :

8)12 C 32 C C .2n C 1/2 D .n C 1/.2n C 1/.2n C 3/

3 .

9)13 C 33 C C .2n C 1/3 D.n C 1/2.2n2 C 4n C 1/.10) Dmontrer les mmes rsultats directement par induction mathmatique.

*7. Autres remarques sur linduction mathmatique

Le principe dinduction mathmatique peut tre lgrement gnralis en disant : tant donne une suite dnoncs As , AsC1, AsC2; : : : , s tant un entier positif quel-conque, si

a) pour chaque valeurr > s, la vrit de ArC1dcoule de la vrit de Ar ,et si

b) Asest vrai,alors tous les noncs As , AsC1, AsC2; : : : sont vrais. Cela signifie que Anest vrai pourtout nombre n > s. Cest le mme raisonnement que celui utilis dans le principe

ordinaire dinduction mathmatique, mais la suite 1, 2, 3; : : : est remplace par la suites,s C 1,s C 2,s C 3 ; : : :En utilisant le principe sous cette forme on peut renforcer un peulingalit de la page 32 en liminant le cas dgalit et dmontrer que : pour toutp 6D0 et>1et tout entiern > 2,

(10) .1 C p/n > 1 C np:

Nous laissons au lecteur le soin de la dmonstration.Le principe du plus petit entier qui nonce quetout ensembleCnon vide dentiers

positifs possde un plus petit lmentest trs voisin du principe dinduction mathmatique.Un ensemble est vide sil na aucun lment, par exemple lensemble des cercles droitsou lensemble des entiers ntels que n > n. Pour des raisons videntes on exclut de telsensembles de lnonc du principe. Lensemble C peut-tre fini, comme lensemble 1,2,3,4,5, ou infini comme lensemble de tous les nombres pairs2,4,6,8,10; : : : Tout ensembleC non vide doit contenir au moins un entier, npar exemple, et le plus petit des entiers 1,2,3 ; : : : ; nqui appartient C sera le plus petit entier de C.


20/60


La seule manire de raliser limportance de ce principe est dobserver quil nesappliquepas tous les ensembles C de nombres qui ne sont pas des entiers ; par exemple,

lensemble des fractions positives1, 12 , 1

3 , 1

4 ; : : :ne contient pas de plus petit lment.Du point de vue de la logique il est intressant dobserver que le principe du plus petit

entier peut tre utilis pour dmontrerle principe dinduction mathmatique en tant quethorme. Pour cela, considrons une suite dnoncs A1, A2, A3; : : :tels quea) pour tout entier positifr la vrit de ArC1dcoule de celle de Ar .b) A1est vrai.Supposer que lun des noncs Arest faux conduit une contradiction. En effet, si lun

des Artait faux, lensemble C detousles entiersnpositifs pour lesquels Anest faux seraitnon vide. En vertu du principe du plus petit entier, C possderait un plus petit lment, p,devant tre> 1 cause de b). Par consquent Ap serait faux et Ap1serait vrai, ce quicontredirait a).

Une fois de plus, soulignons que le principe dinduction mathma-

tique est tout fait distinct de linduction empirique des sciences natu-relles. La confirmation dune loi gnrale par un nombre fini de cas, aussigrand soit-il, ne donne pas une dmonstration de la loi au sens mathma-tique rigoureux du terme, mme si aucune exception nest encore connue ce jour. Une telle loi demeure unehypothsetrs raisonnable, sujette modification en fonction des rsultats dune exprience future. En math-matiques, une loi ou un thorme nest dmontr que si lon peut prou-ver quil est consquence logique ncessaire de certaines assertions consi-

dres comme vraies. Il existe de nombreux exemples dnoncs math-matique qui ont t vrifis pour un certain nombre de cas particuliersmais qui nont pas encore t prouvs comme tant vrais en gnral (pourun exemple, voir page 49). On peutsupposerquun thorme est vrai entoute gnralit si lon constate quil est vrai dans un certain nombre decas particuliers et lon peut alors essayer de le dmontrerpar induction ma-thmatique. Si lon y arrive, le thorme est dmontr, sinon il peut trevrai ou faux et pourrait bien tre un jour valid ou invalid par dautresmthodes.

Quand on utilise le principe dinduction mathmatique, on doit toujours sassurerque les conditions a) et b) sont bien satisfaites. Ngliger de le faire peut conduire desabsurdits comme celle qui suit, le lecteur est invit y trouver lerreur. Nous allons dmontrer quedeux entiers positifs quelconques sont gaux,par exemple que5 D 10.

Mais dabord une dfinition : si a et b sont deux entiers positifs diffrents, on dfinitmax.a;b/comme tant le plus grand de ces deux entiers ; si a D bon pose max.a;b/ DaD b . Par consquent max.3; 5/Dmax.5; 3/D 5, tandis que max.4;4/D 4. Considronsmaintenant lnonc An si aet b sont deux entiers positifs tels que max.a;b/Dn, alorsaD b.

a) Supposons que Arsoit vrai. Soientaetbdeux entiers positifs tels que max.a;b/DrC 1. Considrons les deux entiers

D a 1

D b 1


21/60

notes 37

alors max.;/D r . Par consquent D , car on suppose que Arest vrai. Il sensuit queaD b et donc ArC1est vraie.

b) A1est visiblement vrai, car si max.a;b/D 1 alors, puisque aet bsont par hypothsedes entiers positifs, ils doivent tous deux tre gaux 1. Par consquent, par induction

mathmatique, Anest vrai pour tout nombre n.Maintenant sia et b sont deux entiers positifs quelconques, dsignons max.a;b/parr . Puisque lon a montr que Anest vrai quel que soit n, en particulier Ar est vrai et parconsquenta D b .

Notes

1. Pour les auteurs, les entiers naturels sont 1; 2 ; 3; : : : et positif signifie > 0. Latraduction a conserv ces usages.

Ces dfinitions taient universelles jusquau milieu du xxe sicle. Elles ont ensuitet modifies, mais de faon non uniforme selon la langue et le pays. Dans les pays

francophones, on considre aujourdhui zro comme un entier naturel, et on considre danslenseignement des mathmatiques mais pas dans la langue courante, pas en mdecine,par exemple quepositif signifie > 0. En anglais, en allemand, en russe certains auteursont conserv lusage ancien, et crivent N D f1 ; 2 ; 3 ; : : : gtandis que dautres considrentzro comme un nombre naturel, et crivent N D f0 ; 1 ; 2 ; 3 ; : : : g. Mais personne napropos de changer dans ces langues le sens du motpositif,ni du motngatif,qui signifietoujours < 0, ce qui fait que les premiers auteurs disent que N est form des nombrespositifs, tandis que pour les seconds Nest form des nombres non-ngatifs.

Ainsi, zro est la fois positif et ngatif dans lenseignement franais moderne, et nilun ni lautre en anglais ou en allemand.

Pour viter les ambiguts dues au passage dune langue lautre et la coexistence des

notations anciennes et des nouvelles, on vite souvent en franais demployer les termespositifetpositif ou nul,et on ditstrictement positifpour> 0,positif au sens largepour > 0.(N.d.T.)

2.Induction mathmatiqueet raisonnement par rcurrencesont des expressions syno-nymes. En franais, la premire semploie dans les ouvrages de philosophie, la secondedans lenseignement des mathmatiques. En anglais, on emploie aussi bien en philosophiequen mathmatiques lexpressionmathematical induction.Nous lavons conserve en cer-tains endroits dans cette traduction, notamment pour pouvoir faire la comparaison aveclinduction empirique.(N.d.T.)


22/60


23/60

SUPPLMENT AU CHAPITRE I

THORIE DES NOMBRES

Introduction

Les nombres entiers se sont peu peu dtachs de la pense mys-tique, mais lintrt que leur portent les mathmaticiens na jamais faibli.

Euclide (env. 300 av. J.-C.), lauteur des lments, qui doit sa renommeaux parties de son ouvrage qui tablissent les fondements de la gomtrie,semble avoir apport une contribution originale la thorie des nombres,aussi appelearithmtique(du grecarithmos,nombre), alors mme que sagomtrie nest pour lessentiel quune compilation de rsultats plus an-ciens. Tmoignent aussi de cet intrt Diophante dAlexandrie (env. 275apr. J.-C.), lun des prcurseurs de lalgbre, auteur des Arithmtiques,Pierre de Fermat (1601-1665), magistrat Toulouse et lun des plus grands

mathmaticiens de son temps, qui a t le premier depuis lAntiquit faire des dcouvertes dans ce domaine, Euler (1707-1783), le mathmati-cien le plus prolifique de lhistoire, qui y a consacr une part importantede ses recherches. On peut encore ajouter les noms illustres de Legendre,de Dirichlet ou de Riemann. Gauss (1777-1855), le plus grand mathma-ticien des temps modernes, dont les travaux touchent presque tous lesdomaines des mathmatiques, aurait exprim son opinion sur la thoriedes nombres dans cette observation : La science mathmatique est lareine des sciences et larithmtique est la reine des mathmatiques.

1. Les nombres premiers

1. Rsultats essentiels

La plupart des noncs de thorie des nombres, et des noncs math-matiques en gnral, ne portent pas sur un objet particulier le nombre 5

ou le nombre 32 mais sur une classe entire dobjets qui possdent uneproprit commune, comme la classe des entiers pairs,

2 ; 4 ; 6 ; 8 ; : : : ;

39


24/60

40 supplment au chapitre i. thorie des nombres

ou la classe des entiers divisibles par trois,

3; 6; 9; 12;:::;

ou la classe des carrs parfaits,

1; 4; 9; 16;:::;

et ainsi de suite.En thorie des nombres il existe une classe de nombres particulire-

ment importante, et mme fondamentale : celle desnombres premiers.Laplupart des entiers peuvent tre dcomposs en un produit de facteursplus petits : 10 D 2 5, 111 D 3 37, 144 D 3 3 2 2 2 2, etc. Les

nombres que lon ne peut pas dcomposer ainsi sont appels nombrespremiers. Plus prcisment,un nombre premier est un entierp, plus grandque 1, qui na pas dautre diviseur que 1et lui-mme. (On dit quun en-tierbest undiviseurdun entier asil existe unentierctel que a D bc .Commebcest le produit des facteursb et c , on dit aussi dans ce cas quebpeut tre mis en facteur dans a.) Les nombres 2, 3,5,7,11,13, 17; : : :sont des nombres premiers, tandis que 12par exemple nen est pas un,puisque 12 D 3 4. La classe des nombres premiers est particulirement

importante parce que tout entier peut tre exprim comme un produit denombres premiers: si un nombre nest pas lui-mme un nombre premier,il peut tre factoris (cest--dire dcompos en produit de facteurs) defaon rpte, jusqu ce que tous ses facteurs soit des nombres premiers.Ainsi360 D 3 120 D 3 30 4 D 3 3 10 2 2 D 3 3 5 2 2 2 D 23 32 5.Un entier (autre que 1) qui nest pas un nombre premier est appel unnombrecompos.

Lune des premires questions que lon se pose propos de la classedes nombres premiers est de savoir sil existe un nombre fini de nombres

premiers diffrents, ou si cette classe contient une infinit de nombres,comme la classe des entiers dont elle fait partie. La rponse est quil existeune infinit de nombres premiers.

La dmonstration de linfinit de la classe des nombres premiers telleque la proposait Euclide reste un modle de raisonnement mathmatique.Elle relve de la mthode indirecte1 . On commence par supposer quele thorme que lon nonce est faux. Dans ce cas on suppose quil y aun nombre fini de nombres premiers, peut-tre une grande quantit

1 milliard par exemple ou de faon plus gnrale, n. En utilisant desindices on peut noter ces nombres premiers p1, p2; : : : ; pn. Tout autrenombre sera un nombre compos et devra tre divisible par au moinslun des nombres premiers p1, p2; : : : ; pn. On fait alors apparatre une


25/60

[1,1] les nombres premiers 41

contradiction en construisant un nombre A qui nest divisible par aucundes nombresp1,p2; : : : ; pn. Ce nombre est

A D p1p2: : : pn C 1

que lon obtient en ajoutant1au produit des nombres que nous avons sup-poss tre les seuls nombres premiers. A diffre de chacun des nombrespremiersp1,p2; : : : ; pnparce quil est plus grand que tous ces nombres, ildoit par consquent tre un nombre compos. Mais la division de A parp1, par p2, etc., a toujours pour reste 1 ; A nest donc divisible par au-cun despi . Puisque notre hypothse initiale, savoir quil nexiste quunnombre fini de nombres premiers, mne cette contradiction, cette hypo-

thse est absurde et par consquent sa ngation est vraie, ce qui dmontrele thorme.

Bien que cette dmonstration soit indirecte, comme toute dmonstration par labsurde,on peut facilement la transformer en une mthode de construction dune suite infiniede nombres premiers, du moins en thorie. On sait quil existe un nombre premier, parexemple p1 D 2. On suppose que lon a trouv n nombres premiers p1, p2; : : : ; pn;alors le nombre p1p2: : : pn C 1 est lui-mme premier ou a pour facteur premier unnombre diffrent de ceux que lon a dj trouvs. Puisquon peut toujours trouver ce facteurpremier de manire directe, on est sr de trouver au moins un nouveau nombre premierpnC1; si lon continue de cette manire on voit bien que la suite des nombres premiers que

lon construit na pas de fin.

Exercice.Effectuer cette construction en commenant par p1 D2,p2 D3 et trouvercinq autres nombres premiers.

Lorsquon crit un nombre sous la forme dun produit de facteurspremiers, on peut ranger ces derniers dans nimporte quel ordre. Aprsquelques essais, on ralise vite que, mis part cette possibilit de changerlordre des facteurs, il ny a quune seule faon dcrire un nombre commeproduit de facteurs premiers :la dcomposition dun nombreNplus grand

que1en produit de nombres premiers est unique.Cet nonc semble telle-ment vident premire vue que le profane peut trs bien le considrercomme allant de soi. Mais en ralit, il ne sagit nullement dune vidence,et la dmonstration, bien que parfaitement lmentaire, ncessite des rai-sonnements assez subtils. La dmonstration classique propose par Eu-clide de cet nonc, auquel on a donn le nom de thorme fondamentalde larithmtique est fonde sur une mthode ou un algorithme per-mettant de trouver le plus grand diviseur commun de deux nombres. Nous

en rediscuterons page 63. Nous en proposons ici une dmonstration plusrcente, un peu plus courte et peut-tre plus sophistique que celle dEu-clide. Cest un autre exemple typique de dmonstration indirecte. Nousallons supposer lexistence dun entier admettant deux dcompositions


26/60


en facteurs premiers diffrentes et montrer que cette hypothse conduit une contradiction. Cette contradiction invalidera notre hypothse et prou-vera ainsi que la dcomposition en facteurs premiers de tout entier estunique.

Sil existe un entier positif admettant deux dcompositions en fac-teurs premiers diffrentes, il existera un plus petitentier ayant cette pro-prit (voir p. 35),

(1) m D p1p2: : : pr D q1q2: : : qs;

o lespietqjsont des nombres premiers. En changeant lordre despietdesqjsi cela est ncessaire, on peut supposer que

p1 6 p2 6 6 pr ; q1 6 q2 6 6 qs:

Bien sr, p1 ne peut pas tre gal q1, sinon on pourrait simplifierles deux membres de lgalit (1) par ce facteur premier et lon auraitdeux dcompositions diffrentes dun entier plus petit que m, ce quicontredirait la dfinition de m. Par consquent p1 < q1 ou q1 < p1.Supposons p1 < q1. (Si q1 < p1 il suffit de permuter les lettres pet qdans ce qui suit.) Considrons lentier

(2) m0 D m p1q2q3: : : qs:

En remplaantmpar les deux expressions de lgalit (1) on peut crirelentierm0 sous deux formes diffrentes

m0 D p1p2p3: : : pr p1q2q3: : : qs D p1.p2p3: : : pr q2q3: : : qs/;(3)

m0 D q1q2q3: : : qs p1q2q3: : : qs D .q1 p1/q2q3: : : qs:(4)

Puisque p1 < q1, (4) permet daffirmer que m0 est positif et (2), quem0 est plus petit que m. Par consquent la dcomposition en facteurspremiers dem0 doit treunique, lordre des facteurs prs. Mais daprs(3), lentier premier p1 est un diviseur de m0, donc daprs (4), p1 doittre un diviseur deq1 p1ou deq2q3: : : qs. Cela provient de lunicit dela dcomposition en facteurs premiers de m0, par le mme raisonnementque dans le paragraphe suivant. Il est impossible quep1diviseq2q3: : : qs,car cet entier tant lui aussi infrieur m, sa dcomposition en facteurspremiers est unique etp1devrait alors tre gal lun desqj. Or tous les

qjsont plus grands que p1. Par consquent p1 doit tre un diviseur deq1 p1, de sorte quil existe un entierhtel que,

q1 p1 D p1 h ou q1 D p1.h C 1/:


27/60

[1,2] la rpartition des nombres premiers 43

Mais si ctait le casp1serait un diviseur deq1, ce qui contredirait le faitque q1est un nombre premier. Cette contradiction invalide notre hypo-thse de dpart, ce qui achve la dmonstration du thorme fondamentalde larithmtique.

Ce thorme a un corollaire important :si un nombre premierpdiviseun produitab, alorspdoit tre un diviseur de aou un diviseur de b.Eneffet, sipne divisait niani b , alors le produit des facteurs premiers de aet debnous donnerait une dcomposition en facteurs premiers de lentierabne contenant pasp. Dautre part, sipdiviseab , alors il existe un entierttel que

ab D pt:

Par consquent le produit de p par la dcomposition en facteurs pre-miers de t donnerait une dcomposition en facteurs premiers de lentierab contenantp, ce qui contredit le fait que la dcomposition en facteurspremiers deab est unique.

Exemples. Si lon a vrifi que 13 est un diviseur de 2652, et que2652 D 6 442, on peut en dduire que13est un diviseur de442. Dautrepart,6est un diviseur de240, et240 D 15 16, mais6ne divise ni15ni16,ce qui montre quil est essentiel que psoitpremier.

Exercice.Pour trouver tous les diviseurs dun nombre a il suffit de dcomposer a enun produitaD p

11 p

22 : : : p

rr ;

o lespisont des nombres premiers distincts, levs chacun une certaine puissance.Tousles diviseurs deasont de la forme

b D p11 p

22 : : : p

rr ;

o lesj sont des entiers quelconques satisfaisant les ingalits suivantes :

0 6 1 6 1; 0 6 2 6 2; : : : ; 0 6 r 6 r :

Dmontrer cet nonc. En dduire que le nombre de diviseurs de a (y comprisa et 1) estgal au produit

.1C 1/.2C 1 / : : : . r C 1/:

Par exemple, le nombre de diviseurs de

144D 24 32

est5 3. Ces diviseurs sont1,2,4,8,16,3,6,12,24,48,9,18,36,72,144.

2. La rpartition des nombres premiers

On peut tablir la liste de tous les nombres premiers infrieurs unentier N donn de la faon suivante : on crit, dans lordre croissant, tous


28/60


les entiers infrieurs N, puis on supprime tous les multiples de deux,puis parmi ceux qui restent, tous les multiples de trois, et ainsi de suite

jusqu ce que tous les nombres composs aient t limins. Ce procd,connu sous le nom de crible dratosthne , gardera dans les maillesde ses filets tous les nombres premiers infrieurs N. En raffinant cettemthode, on a pu tablir, petit petit, la table des nombres premiers in-frieurs N pour des valeurs de N de plus en plus grandes (aujourdhuienviron 10 millions). Ces tables ont fourni une grande quantit de don-nes empiriques concernant la rpartition et les proprits des nombrespremiers et ont permis de faire de nombreuses conjectures (comme si lathorie des nombres tait une science exprimentale), hautement plau-sibles, mais souvent extrmement difficiles dmontrer.

a. Les formules conduisant des nombres premiers

On a recherch des formules arithmtiques simples ne produisantque des nombres premiers, dfaut den trouver une qui fournisse tousles nombres premiers. Fermat a mis la clbre conjecture que tous lesnombres de la forme

F.n/ D 22n

C 1

taient premiers. Pourn D 1;2;3;4on obtient en effet les nombresF.1/ D 22 C 1 D 5;

F.2/ D 222

C 1 D 24 C 1 D 17;

F.3/ D 223

C 1 D 28 C 1 D 257;

F.4/ D 224

C 1 D 216 C 1 D 65 537;

qui sont tous premiers. Mais, en 1732, Euler a montr que 225

C 1 D

641 6700417, par consquent F.5/nest pas premier. On a dmontr parla suite que plusieurs de ces nombres de Fermat taient des nombrescomposs, en faisant appel des rsultats thoriques de plus en plusprofonds, tant donn limpossibilit dune preuve par essais directs. ce jour, on na toujours pas dmontr que lun des nombres F.n/, pourn > 4, est premier.

Une autre formule simple :

f.n/ D n2

n C 41

fournit un grand nombre dentiers premiers. Pour n D 1 ; 2 ; 3 ; : : : ; 4 0, f.n/est premier ; en revanche,f .41/ D 412 nest pas premier.


29/60


Lexpressionn2 79n C 1601

donne des nombres premiers pour tous les entiers ninfrieurs ou gaux

79, mais pas pour n D 80. Dune manire gnrale, on peut dire quela recherche dexpressions simples ne donnant que des nombres premiersa t vaine. Il est encore plus improbable que lon trouve un jour uneformule algbrique fournissanttousles nombres premiers2.

b. Les nombres premiers dans les progressions arithmtiques

Alors que lon dmontre facilement que la suite de tous les entiers, 1,

2,3,4; : : : ;contient une infinit de nombres premiers, il est beaucoup plusdifficile de le dmontrer pour des suites telles que 1,4,7,10,13; : : : ou3,7, 11, 15, 1 9 ; : : : ou plus gnralement, pour une progression arithmtiquea,a C d,a C 2 d ; : : : ; a C n d ; : : : , oaetdnont aucun facteur commun.Toutes les observations ont montr que chacune de ces progressionscontenait une infinit de nombres premiers, comme la plus simple dentreelles, 1 ; 2 ; 3 ; : : : , mais la dmonstration de ce thorme gnral a ncessitde gros efforts. Lejeune-Dirichlet (1805-1859), lun des mathmaticiens

les plus importants du xixe

sicle, vit ses efforts couronns de succslorsquil appliqua la recherche de la dmonstration de ce thorme,les outils les plus avancs de lanalyse mathmatique de son poque. Sesarticles originaux sur ce sujet sont parmi les plus extraordinaires russitesdes mathmatiques, et une centaine dannes plus tard on na toujourspas russi simplifier suffisamment sa dmonstration pour la mettre laporte dtudiants peu entrans aux techniques du calcul diffrentiel etintgral et de la thorie des fonctions.

Bien quil soit hors de question, ici, de dmontrer le thorme gn-

ral de Dirichlet, on peut tout de mme gnraliser la dmonstration dEu-clide de linfinit des nombres premiers certaines progressions arithm-tiquesparticulirestelles que4n C 3et6n C 5. Prenons la premire de cesprogressions et remarquons tout dabord que tout nombre premier plusgrand que deux est impair (sinon il serait divisible par deux) et que, parconsquent, il est de la forme4n C1ou4n C3, avecnentier. Remarquonsaussi que le produit de deux nombres de la forme 4n C 1est lui-mme unnombre de cette forme puisque

.4a C 1/.4b C 1/ D 16ab C 4a C 4b C 1 D 4.4ab C a C b/ C 1:

Supposons prsent quil nexiste quun nombre fini de nombres premiers,


30/60


p1,p2,: : : pn, de la forme4n C 3, et considrons le nombre

N D 4.p1p2: : : pn/ 1 D 4.p1p2: : : pn 1/ C 3:

Soit le nombre N est lui-mme premier, soit il peut tre dcompos enun produit de facteurs premiers, forcment tous diffrents de p1; : : : ; pn,puisquon peut faire la division de lentier N par chacun des pi en obte-nant pour reste 1. De plus, les facteurs premiers de N ne peuvent pastre tous de la forme 4n C 1, tant donn que N nest pas de cette formeet que, comme nous venons de le voir, le produit de nombres de la forme4n C 1 est encore un nombre de cette forme. Par consquent, lun aumoins des facteurs premiers de N doit tre de la forme 4n C 3. Mais celaest impossible, puisque nous avons vu quaucun desp

i, supposs tretous

les nombres premiers de la forme4n C 3, nest un facteur premier de N.Lhypothse selon laquelle les nombres premiers de la forme 4n C 3sonten nombre fini conduit donc une contradiction, et par consquent lenombre des entiers premiers de cette forme est infini.

Exercice.Dmontrer le thorme correspondant pour la progression 6n C 5.

c. Le thorme des nombres premiers

Dans leur recherche dune loi gouvernant rpartition des nombrespremiers les mathmaticiens ont franchi une tape dcisive lorsquils ontrenonc trouver une formule mathmatique simple donnant tous lesnombres premiers ou le nombre exact dentiers premiers parmi les npremiers entiers, pour soccuper plutt de la rpartition moyenne desnombres premiers parmi les entiers.

Pour tout entier n, dsignons par An le nombre dentiers premiersinfrieurs ou gaux n. En soulignant les nombres premiers dans la suite

des premiers entiers : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 , onpeut calculer les premires valeurs de An:

A1 D 0; A2 D 1; A3 D A4 D 2; A5 D A6 D 3; A7 D A8 D A9 D A10 D 4;

A11 D A12 D 5; A13 D A14 D A15 D A16 D 6; A17 D A18 D 7;A19 D 8; etc.

Si lon considre maintenant une suite de valeurs de nqui augmenteindfiniment, par exemple

n D 10; 102

; 103

; 104

; : : : ;

alors les valeurs correspondantes de Anaugmenteront elles-aussi indfini-ment (bien que plus lentement). En effet, on sait quil existe une infinit


31/60


de nombres premiers, donc tt ou tard les valeurs de Andpasseront toutnombre donn. La densit des nombres premiers parmi lesnpremiersentiers est donne par le rapport An=n, et les valeurs de An=n peuventtre calcules empiriquement partir dune table des nombres premierspour un assez grand nombre de valeurs de n.

n An=n

103 0; 168

106 0; 078498

109 0; 050847478

: : : : : : : : : : : : : : :

La dernire valeur donne par la table peut tre considre comme don-nant la probabilit quun entier choisi au hasard parmi les 109 premiersentiers soit premier, puisquil existe 109 choix possibles, parmi lesquelsA109sont premiers.

La rpartition des nombres premiers parmi les entiers est extrme-ment irrgulire. Mais cette irrgularit dans le dtail disparat si lonse concentre sur la rpartition moyenne des nombres premiers donne parle rapport An=n. La loi simple qui gouverne le comportement de ce rap-

port est lune des plus remarquables dcouvertes en mathmatiques. Pournoncer lethorme des nombres premierson doit dabord dfinir le lo-garithme naturel dun entier n. Pour cela, prenons deux axes perpendicu-laires du plan, et considrons le lieu de tous les points du plan dont le pro-duit des distancesxety ces axes est gal 1. En termes de coordonnesxety , ce lieu est une hyperbole quilatre, dfinie par lquationxy D 1.

x

y

1 n

Fig.5. Laire de la rgion grise sous lhyperbole dfinitlog n.

Dfinissons maintenant log n comme laire de la figure 5 dlimite parlhyperbole, laxe desx, et les deux droites verticalesx D 1etx D n. (On


32/60


trouvera au chapitre VIII une discussion plus dtaille du logarithme.) partir dune tude empirique des tables des nombres premiers, Gaussobserva que le rapport An=n est approximativement gal 1= log n, etque cette approximation semble samliorer mesure que naugmente.

La qualit de lapproximation est donne par le rapport An=n1= log n dont les

valeurs pourn D 1000, 1million, 1milliard sont donnes dans la tablesuivante :

n An=n 1= log n An=n

1= logn

103 0; 168 0; 145 1; 159

106 0; 078498 0; 072382 1; 084

109 0; 050847478 0; 048254942 1; 053

: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : partir de cette vidence empirique, Gauss a mis la conjecture que

le rapport An=n est asymptotiquement gal 1= log n. Cela signifieque si lon considre une suite de valeurs dende plus en plus grandes, parexemple

10; 102; 103; 104; : : : ;

comme prcdemment, alors le rapport

An=n1= log n

;

calcul pour ces valeurs successives de n, se rapprochera de plus en plusde 1, et la diffrence de ce rapport avec 1 pourra tre rendue aussipetite quon le dsire condition de ne considrer que des valeurs de nsuffisamment grandes. On exprime cela symboliquement par le signe :

An=n 1= log n

signifie :

An=n

1= log ntend vers1lorsquenaugmente indfiniment.

Il est clair que lon ne peut pas remplacer ce signe par le signeordinaire de lgalit tant donn que Anest toujours un entier alors quen= log nnen nest pas un.

Que la rpartition moyenne des nombres premiers puisse tre dcritepar la fonction logarithme est une dcouverte tonnante : on est surpris devoir que deux notions mathmatiques apparemment aussi loignes sonten ralit intimement lies.


33/60


Bien que lnonc de la conjecture de Gauss soit simple comprendre,une dmonstration mathmatique rigoureuse de cette conjecture taitbien au del des capacits de la science mathmatique de son poque.Pour prouver ce thorme, qui ne met en jeu que des notions des pluslmentaires, il est ncessaire demployer les mthodes les plus puissantesdes mathmatiques modernes. Il a fallu presque un sicle avant que lana-lyse natteigne un niveau de dveloppement tel quHadamard (1896) Paris et de la Valle Poussin (1896) Louvain puissent en fournir une d-monstration complte. Von Mangoldt et Landau y apportrent dimpor-tantes modifications et de nombreuses simplifications. Mais limpulsiondcisive est venue de Riemann (1826-1866), qui bien avant Hadamardavait indiqu dans un article clbre la stratgie adopter. Rcemment,

le mathmaticien amricain Norbert Wiener a modifi la dmonstrationde manire viter lusage des nombres complexes une tape impor-tante du raisonnement. La dmonstration de ce thorme nen demeurepas moins difficile, mme pour un tudiant avanc. Nous y reviendronspage 543 et suivantes.

d. Deux problmes non rsolus sur les nombres premiers

Alors que le problme de la rpartition moyenne des nombres pre-miers a t rsolu de faon satisfaisante, de nombreuses autres conjec-tures, confirmes par toutes les preuves empiriques possibles, nont pasencore t dmontres.

Lune dentre elles est la clbre conjecture de Goldbach.Goldbach(1690-1764) ne joue quun rle minime dans lhistoire des mathmatiquessi ce nest pour ce problme quil soumit Euler dans une lettre de 1724.Dans tous les cas considrs il avait constat quun nombre pair (sauf

2, qui lui-mme est premier) pouvait scrire comme somme de deuxnombres premiers. Par exemple : 4 D 2 C 2, 6 D 3 C 3, 8 D 5 C 3,10 D 5 C 5, 12 D 5 C 7, 14 D 7 C 7, 16 D 13 C 3, 18 D 11 C 7,20 D 13 C 7 ; : : : ; 4 8 D 29 C 19; :::; 100 D 97 C 3. etc.

Goldbach demanda Euler sil pouvait prouver que cela tait vraipour tousles nombres pairs, ou sil pouvait trouver un contre exemple.Euler ne put jamais rpondre cette question, ni personne depuis. Lespreuves empiriques en faveur de lnonc que tout nombre pair peut

scrire de la sorte sont profondment convaincantes, chacun peut le vri-fier sur un grand nombre dexemples. La source de la difficult se trouvedans le fait que les nombres premiers sont dfinis partir de la multipli-cation, alors que ce problme porte sur laddition. De manire gnrale,


34/60


il est difficile dtablir des liens entre les proprits multiplicatives et lesproprits additives des entiers.

Il y a peu de temps encore, une dmonstration de la conjecture deGoldbach semblait compltement inaccessible, mais aujourdhui elle neparat plus hors de porte. En 1931, Schnirelmann (1905-1938), un jeunemathmaticien russe jusqualors inconnu, tablit un rsultat important,tout fait inattendu et surprenant pour les spcialistes. Il dmontra quetout entier positif peut tre reprsent par la somme dau maximum300 000nombres premiers.Bien que ce rsultat semble ridicule compar lobjec-tif original qui tait de dmontrer la conjecture de Goldbach, il constitue

nanmoins le premier pas dans cette direction. La dmonstration est di-recte et constructive, mme si elle ne fournit aucune mthode utilisable enpratique pour trouver la dcomposition dun entier quelconque en sommede nombres premiers. Plus rcemment, le mathmaticien russe Vinogra-dov a russi, en utilisant des mthodes dues Hardy, Littlewood et leurgrand collaborateur indien Ramanujan, rduire le nombre de 300 0004, ce qui est bien plus proche de la solution du problme de Goldbach.Mais il y a une diffrence considrable entre les rsultats de Schnirelmann

et de Vinogradov, sans doute plus significative que le progrs de 300 0004. Vinogradov a dmontr son thorme pour des entiers suffisammentgrands ; plus prcisment, il a dmontr quil existeun entier N tel quetout entier n >N peut scrire comme la somme dau plus quatre nombrespremiers. La dmonstration de Vinogradov ne nous permet pas destimerla valeur de N; contrairement la dmonstration de Schnirelmann, la d-monstration de Vinogradov est une dmonstration par labsurde et doncnon constructive. En ralit, Vinogradov a prouv que lhypothse selonlaquelle il existerait une infinit dentiers ne pouvant scrire comme la

somme dau plus quatre nombres premiers conduit une absurdit. Cetexemple illustre bien la diffrence profonde entre une dmonstration di-recte et une dmonstration indirecte3. (Voir la discussion gnrale p. 113.)

Le problme suivant, encore plus frappant que celui de Goldbach, najamais vu lombre dune solution. On a observ que les nombres premiersapparaissent souvent par paires de la forme pet p C 2. Comme 3et 5,

11et13,29et31, etc. On dit que ce sont des nombres premiersjumeaux.On pense quil existe une infinit de paires de nombres premiers jumeauxmais on na, pour le moment, aucune ide de la dmarche suivre pour ledmontrer.


35/60

[2] congruences 51

2. Congruences

1. Notions gnrales

Chaque fois que lon aborde le problme de la divisibilit des entierspar un entierddonn, la notion de congruence et la notation correspon-dante (dues Gauss) sont l pour claircir la situation et simplifier lesraisonnements.

Pour introduire cette notion, examinons les restes de la division par 5.On a

0 D 0 5 C 0

1 D 0 5 C 1

2 D 0 5 C 23 D 0 5 C 3

4 D 0 5 C 4

5 D 1 5 C 0

6 D 1 5 C 1

7 D 1 5 C 2

8 D 1 5 C 3

9 D 1 5 C 410 D 2 5 C 0

11 D 2 5 C 1

12 D 2 5 C 2

etc.

1 D 1 5 C 4

2 D 1 5 C 3

3 D 1 5 C 24 D 1 5 C 1

5 D 1 5 C 0

6 D 2 5 C 4

etc.

On observe que le reste de la division dun entier par 5est lun des cinqentiers 0, 1, 2, 3, 4. On dit que deux entiers aet bsont congrus modulo 5 sils ont mme reste dans la division par 5. Ainsi 2, 7, 12, 17, 2 2 ; : : : ; 3, 8,

13, 1 8 ; : : : sont tous congrus modulo 5, puisquils ont tous comme reste2. Plus gnralement, on dit que deux entiersaetbsontcongrus modulod,dtant un entier donn, siaetbont mme reste dans la division pardou, ce qui revient au mme, sil existe un entierntel quea b D nd. Parexemple,27et15sont congrus modulo4, puisque

27 D 6 4 C 3; 15 D 3 4 C 3:

La notion de congruence est si utile quil convient de la noter simple-

ment. On crita b .mod d /

pour exprimer le fait queaetbsont congrus modulod, et sil ny a aucundoute concernant le module, on peut omettre dcrire mod d. (Si anest pas congru bmodulod, on criraa 6 b .mod d /.)

Dans la vie quotidienne les congruences interviennent couramment.Les aiguilles dune montre, par exemple, indiquent lheure modulo12.

Avant de poursuivre la lecture de ce chapitre, le lecteur devra sassu-

rer de lquivalence des noncs suivants :1. aest congru bmodulod.

2. aD b C ndpour un certain entiern.


36/60


3. ddivisea b.

La congruence modulo un certain entier dpossde de nombreusesproprits de lgalit ordinaire, do lavantage de la notation propose

par Gauss. Les plus importantes proprits formelles de la relationa D bsont les suivantes :

1) On a toujoursa D a.

2) Sia D b, alorsb D a.

3) Sia D betb D c, alorsa D c.

De plus, sia D a0 etb D b0, alors

4) a C b D a0 C b0.

5) a b D a0

b

0

.6) ab D a0b0.

Ces proprits restent vraies lorsque la relationa D best remplace parla relation de congruencea b .mod d /. Ainsi

10) On a toujoursa a .mod d /.

20) Sia b .mod d /, alorsb a .mod d /.

30) Sia b .mod d /etb c .mod d /, alorsa c .mod d /.

Le lecteur vrifiera lui mme ces proprits.De plus, sia a0 .mod d /etb b0 .mod d /, alors

40) a C b a0 C b0 .mod d /.

50) a b a0 b0 .mod d /.

60) ab a0b0 .mod d /.

Autrement dit, on peut additionner, soustraire et multiplier des congruencesmodulo un mme entier.Pour dmontrer ces trois noncs il suffit de re-marquer que si

aD a0 C rd; b D b0 C sd ;

alors

a C b D a0 C b0 C .r C s/d

a b D a0 b0 C .r s/d

ab D a0b0 C .a0s C b0r C rsd/d;

les conclusions attendues sensuivent immdiatement.

Linterprtation gomtrique de la notion de congruence est parti-culirement instructive. Habituellement, pour reprsenter gomtrique-ment les entiers, on choisit un segment de longueur unit et on le pro-longe par des segments semblables dans les deux directions. On peut, de


37/60

[2,1] congruences 53

cette manire, faire correspondre chaque entier un point de la droite,comme dans la figure 6. Mais lorsquon opre avec des entiers modulod,on considre deux entiers congrus modulodcomme identiques dans toutce qui touche la division par d, puisquils ont mme reste dans cettedivision. Pour traduire cela gomtriquement, on utilise un cercle divisendparties gales. Le reste de la division dun entier par dest lun desnombres0,1; : : : ; d 1, que lon place sur la circonfrence du cercle in-tervalles gaux. Chaque entier est congru modulod lun de ces entierset peut, par consquent, tre reprsent gomtriquement par le pointcorrespondant ; deux nombres sont congrus entre eux modulodsils sontreprsents par le mme point. La figure 7 illustre le cas o d D 6. Uneautre illustration, pour le cas d D 12, est donne par le cadran dune

horloge.

3 2 1 0 1 2 3

Fig.6. Reprsentation gomtrique des entiers.

::

4

28::

::

5

17::

::

1

5

11::

::

2

4

10::

::

3

3

9::

::

0

6

12::

Fig.7. Reprsentation gomtrique des entiers modulo 6.

Pour illustrer lutilisation de la proprit multiplicative 60/ des congruences,

nous allons dterminer les restes de la division des puissances successivesde10par un nombre donn. Par exemple,

10 1 .mod 11/;


38/60


puisque 10 D 1 C 11. En multipliant successivement cette congruencepar elle-mme, on obtient

102 .1/.1/ D 1 .mod 11/

103 1 .mod 11/

104 1 .mod 11/; etc.

partir de l, on peut montrer que tout entier

z D a0 C a1 10 C a2 102 C C an 10

n;

exprim dans le systme dcimal, a mme reste dans la division par 11

que la somme alterne de ses chiffres,t D a0 a1 C a2 a3 C

En effet,

z t D a1 11 C a2.102 1/ C a3.10

3 C 1/ C a4.104 1/ C

et puisque tous les nombres 11, 102 1, 103 C 1; : : : sont congrus 0modulo 11, z t lest aussi, et par consquent z a mme reste dans la

division par11que t . Il sensuit en particulier quun nombre est divisiblepar11(ou, ce qui revient au mme, quil a pour reste 0dans la divisionpar 11) si et seulement si la somme alterne de ses chiffres est divisiblepar11. Par exemple, puisque3 1 C 6 2 C 8 1 C 9D 22, le nombrez D 3162819est divisible par 11. Trouver une rgle pour la divisibilitpar 3ou par 9est encore plus simple, puisque 10 1 .mod 3ou9/, etdonc 10n 1 .mod 3ou9/pour tout n. Il sensuit quun nombre z estdivisible par3ou par9si et seulement si la somme de ses chiffres

s D a0 C a1 C a2 C C an

est elle aussi divisible par3ou par9, respectivement.Pour les congruences modulo7on a

10 3; 102 2; 103 1; 104 3; 105 2; 106 1:

partir de l, les restes successifs se rptent. Ainsi z est divisible par7si et seulement si lexpression

r D a0 C 3a1 C 2a2 a3 3a4 2a5 C a6 C 3a7 C

est elle-mme divisible par7.


39/60

[2,1] congruences 55

Exercice.Trouver une rgle semblable pour la divisibilit par13.

Lorsquon additionne ou quon multiplie des congruences modulo uncertain entierddonn, disons par exemple d D 5, on peut viter que

les nombres ne deviennent trop grands dans les calculs intermdiairesen remplaant systmatiquement chaque entier intervenant dans le calculpar lentier gal

0; 1; 2; 3; ou 4

auquel il est congru. Par consquent, pour calculer des sommes et desproduits dentiers modulo 5, il suffit dutiliser les tables daddition et demultiplication suivantes :

a C b

b 0 1 2 3 4

a 0 0 1 2 3 4

1 1 2 3 4 0

2 2 3 4 0 1

3 3 4 0 1 2

4 4 0 1 2 3

a b

b 0 1 2 3 4

a 0 0 0 0 0 0

1 0 1 2 3 4

2 0 2 4 1 3

3 0 3 1 4 2

4 0 4 3 2 1

La deuxime de ces tables nous montre quun produitabnest congru 0 .mod 5/ quesi aou best congru 0 .mod 5/. Cela peut nous suggrerla rgle gnrale

7)ab 0 .mod d /seulement sia 0oub 0 .mod d /,

qui nest que lextension dune rgle bien connue du calcul sur les entiers, savoir queab D 0seulement si a D 0ou b D 0. Maisla rgle 7) nestvalable que si le moduledest premier.Supposonsdpremier. La relation

ab 0 .mod d /signifie queddiviseab , et lon a vu quun nombre premier dne divise unproduitab que sil diviseaoub; cest--dire si

a 0 .mod d / ou b 0 .mod d /:

Sidnest pas premier, cette rgle ne sapplique pas ; on peut en effetcrired D r s, avecr etsinfrieurs d, de sorte que

r 6 0 .mod d /; s 6 0 .mod d /;

maisrs D d 0 .mod d /:


40/60


Par exemple, 2 6 0 .mod 6/et 3 6 0 .mod 6/, mais 2 3 D 6 0.mod 6/.

Exercice. Montrer que la rgle de simplification suivante sapplique lorsque les congruencessont considres modulo un entier premier :

Si ab ac et a60; alors b c :

Exercices. 1) quel nombre compris entre 0 et 6 (au sens large) le produit 11 18 2322 13 19est-il congru modulo7 ?

2) quel nombre compris entre0et12(au sens large) le produit3 7 11 17 19 23 29 113est-il congru modulo13 ?

3) quel nombre compris entre0et4(au sens large) la somme 1 C 2 C 22 C C219

est-elle congrue modulo5 ?

2. Le thorme de Fermat

Au xviie sicle, Fermat, le fondateur de la thorie des nombres mo-derne, a dcouvert un thorme extrmement important : si p est unnombre premier qui nest pas un diviseur de lentiera, alors

ap1 1 .mod p/:

Autrement dit, le reste de la division par p de la.p 1/-ime puissancedeaest gal 1.

Certains de nos calculs prcdents confirment ce thorme ; on a vupar exemple que 106 1 .mod 7/,que 102 1 .mod 3/,etque 1010 1.mod 11/. On peut montrer de la mme faon que 212 1 .mod 13/etque510 1 .mod 11/. Pour vrifier ces dernires congruences il nest pasncessaire de calculer des puissances leves, on peut utiliser la propritmultiplicative des congruences :

24

D 16 3 .mod 13/; 52

3 .mod 11/28 9 4 .mod 13/; 54 9 2 .mod 11/212 4 3 D 12 1 .mod 13/; 58 4 .mod 11/

510 3 4 D 12 1 .mod 11/:

Pour dmontrer le thorme de Fermat, considrons les multiples de a

m1 D a; m2 D 2a; m3 D 3a; : : : ; mp1 D .p 1/a:

Deux de ces entiers ne peuvent tre congrus entre eux modulo p, parcequalorspserait un diviseur demr ms D .r s/apour un certain coupledentiersr; svrifiant1 6 r < s 6 .p 1/. Mais la rgle7) montre quecela ne peut pas se produire. En effet, pne divise pas s rpuisque s rest


41/60

[2,3] rsidus quadratiques 57

infrieur pet dautre part, par hypothse,pne divise pasa. On montrede la mme faon quaucun de ces nombres m1, m2; : : : ; mp1 ne peuttre congru 0, ils doivent par consquent tre respectivement congrusaux nombres1,2,3; : : : ; p 1, dans un certain ordre. Il sensuit que

m1m2: : : mp1 D 1 2 3 : : : . p 1/ap1

1 2 3 : : : . p 1/ .mod p/

ou, si lon pose K D 1 2 3 : : : . p 1/pour plus de concision, que

K

ap1 1

0 .mod p/:

Mais, daprs la rgle 7/, K nest pas divisible par p , puisquaucun deses facteurs ne lest ; par consquent, toujours daprs cette rgle,ap1 1doit tre divisible parp, autrement dit

ap1 1 0 .mod p/:

Ce qui achve la dmonstration du thorme de Fermat.Pour confirmer encore une fois ce thorme, prenonsp D 23etaD 5.

On a, modulo23,52 2,54 4,58 16 7,516 49 3,520 12,

522 24 1. Aveca D 4, au lieu de5, on obtient, toujours modulo23,42 7, 43 28 5, 44 20 3, 48 9, 411 45 1,422 1.

Dans lexemple ci-dessus o aD 4 et p D 23, mais aussi dans dautres,on peut remarquer quune autre puissance dea, plus petite quep 1, estcongrue 1. La plus petite de ces puissances, dans ce cas 11, est toujoursun diviseur dep 1. (Voir lexercice 3 qui suit.)

Exercices.1) Montrer de la mme faon que28 1 .mod 17/ ;38 1 .mod 17/ ;

314

1 .mod 29/ ;214

1 .mod 29/ ;414

1 .mod 29/ ;514

1 .mod 29/.2) Vrifier le thorme de Fermat pour p D 5,7,11,17,23en donnant lentieradesvaleurs diffrentes.

3) Dmontrer le thorme gnral suivant : le plus petit entier positife pour lequelae 1 .mod p/est un diviseur dep 1. (Indication : diviserp 1pare, on obtient

p 1D k eC r;

o0 6 r < e, et utiliser le fait queap1 ar 1 .mod p/.)

3. Rsidus quadratiques

Si lon revient aux exemples qui nous ont servi illustrer le tho-rme de Fermat on peut voir que non seulement on a toujours ap1 1


42/60


.mod p/, mais que (lorsque p est premier et diffrent de 2, par cons-quent impair et de la formep D 2p0 C 1) pour certaines valeurs deaon aaussiap

0

D a.p1/=2 1 .mod p/. Cest intressant. Voyons cela de plusprs. Du thorme de Fermat on tire :

ap1 1 D a2p0

1 D .ap0

1/.ap0

C 1/ 0 .mod p/:

Puisquun produit est divisible parpsi et seulement si lun de ses facteurslest, il est clair queap

0

1ou ap0

C 1doit tre divisible par p , de sorteque pour tout nombrep > 2premier et tout entier anon divisible parp,on a

a.p1/=2 1 ou a.p1/=2 1 .mod p/:

Ds le dbut de la thorie des nombres moderne, les mathmaticiensse sont demands quels pouvaient tre les entiers a correspondant aupremier cas de figure et ceux correspondant au second. Supposons queasoit congru modulopau carr dun certain nombrex,

a x2 .mod p/:

Alors a.p1/=2 xp1 est, daprs le thorme de Fermat, congru 1 modulo p. Un entier a, qui nest pas un multiple de p et qui estcongru modulopau carr dun nombre est appel un rsidu quadratiquemodulo p,alors quun nombre b, qui nest pas un multiple de p et quinest pas congru un carr est appel unnon-rsidu quadratique modulop. On vient de voir que tout rsidu quadratique a modulo p satisfaitla congruence a.p1/=2 1 .mod p/. On peut dmontrer sans grandedifficult que pour tout non-rsidub on ab .p1/=2 1 .mod p/. Nousallons montrer tout lheure que parmi les nombres 1,2,3; : : : ; p 1il ya exactement.p 1/=2rsidus quadratiques et.p 1/=2non-rsidus.

Bien que les calculs aient permis de runir une grande quantit dedonnes empiriques, il na pas t facile de dcouvrir les lois gnralesgouvernant la rpartition des rsidus quadratiques et des non-rsidus. Lapremire proprit importante de ces rsidus a t trouve par Legendre(1752-1833); Gauss lappela plus tard la loi de rciprocit quadratique.Selon cette loi, tant donns deux nombres premiers distincts p et q, qest un rsidu quadratique modulo p si et seulement si p est un rsidu

quadratique modulo q, condition que le produitp 1

2

q 12

soitpair.

Dans le cas o ce produit estimpair,la situation est inverse, de sorte quepest un rsidu moduloqsi et seulement siqest unnon-rsidumodulop.Lune des premires russites du jeune Gauss a t de donner la premiredmonstration rigoureuse de cet important thorme qui tait longtemps


43/60

[3] les triplets pythagoriciens et le grand thorme de fermat 59

rest un dfi pour les mathmaticiens. La dmonstration de Gauss taitloin dtre simple, et la loi de rciprocit nest pas vraiment facile tablir mme de nos jours, bien quun grand nombre de dmonstrationsdiffrentes (dont plusieurs autres par Gauss lui-mme) aient t publies.On na compris que rcemment la vritable signification de la loi derciprocit quadratique grce aux progrs de la thorie des nombresalgbriques.

Pour donner un exemple de la rpartition des rsidus quadratiques,prenonsp D 7. Puisque, modulo7,

02 0; 12 1; 22 4; 32 2; 42 2; 52 4; 62 1;

et que les carrs suivants reproduisent cette mme suite, les rsidusquadratiques modulo 7 sont les nombres congrus 1, 2 ou 4, et lesnon-rsidus sont congrus 3, 5 ou 6. Dans le cas gnral, les rsidusquadratiques modulo psont les nombres congrus 12, 22; : : : ; . p 1/2.Or ces nombres sont congrus deux deux, en effet

x2 .p x/2 .mod p/ .par exemple22 52 .mod 7//;

puisque .p x/2 D p2 2px C x2 x2 .mod p/. Par consquent la

moiti des nombres1,2; : : : ; p 1est constitue des rsidus quadratiquesmodulopet lautre moiti des non-rsidus quadratiques.

Pour illustrer la loi de rciprocit quadratique, prenons le casp D 5,q D 11. Puisque11 12 .

Documents

Courant Robbins Chap1 4mars15