INFO 1 Semestre 1 Anne 2012/2013

IUT de LAVALDpartement Informatique

- Polycopi de cours -

Mathmatiques Discrtes

Yann Walkowiak 1http://www.univ-lemans.fr/~ywalko

yann.walkowiak@univ-lemans.fr

1. Merci Patricia Everaere et Serge Iovleff dont les documents mont aid rdiger ce cours.

Table des matires

1 Thorie des ensembles 11.1 Ensembles et oprations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Proprits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.3 Application entre deux ensembles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.4 Cardinal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.5 Miscellannes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2 Logique 132.1 Logique propositionnelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.2 Prdicats et quantificateurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.3 Thormes et dmonstrations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3 Relations sur un ensemble 213.1 Dfinition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213.2 Oprations sur les relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223.3 Proprits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.4 Relation dquivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263.5 Relation dordre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

4 Thorie des graphes : introduction 314.1 Graphes et modlisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314.2 Graphe orient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314.3 Graphe non orient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334.4 Graphe partiel et sous-graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344.5 Thorme des poignes de mains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344.6 Chemin, chane, circuit et cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344.7 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

5 Arithmtique 395.1 Divisibilit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395.2 Nombres premiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415.3 quation diophantienne ax+ by = c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

i

ii Table des matires

5.4 Congruences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455.5 Cryptographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

6 Mais qui sont ces gens ? 51

Bibliographie 57

Partie 1

Thorie des ensembles

Nul ne doit nous exclure du Paradis que Cantor a cr (David Hilbert)

1.1 Ensembles et oprations

1.1.1 Dfinition - Exemples

Il est trs dlicat de donner une dfinition rigoureuse de ce quest un ensemble. Nous nous contenteronsdune dfinition intuitive bien suffisante pour nos besoins.

Dfinition 1.1.1. Un ensemble est une collection dobjets appels lments de lensemble. On note x E(et on dit x appartient E) si x est un lment de E.

Exemple 1.1.1. 1. lensemble N des entiers naturels N = {0, 1, 2, 3, . . .} (7 N, 2 / N)2. lensemble Z des entiers relatifs (2 Z, 13 / Z)3. lensemble Q des nombres rationnels ( 13 Q,

2 / Q)

4. lensemble R des nombres rels (

2 Q)

Un ensemble peut tre reprsent par une patate, plus joliment appele diagramme dEuler 1

Exemple 1.1.2. lensemble E = {a, b, g, u, i,m} est reprsent par le diagramme dEuler de la figure 1.1.

On a lhabitude de noter les ensembles avec des capitales majuscules et les lments dun ensemble avecdes minuscules. Un ensemble peut tre dfini en extension, cest--dire en donnant la liste de ses lments,ou en comprhension, cest--dire en donnant une proprit vrifie par ses lments (et uniquement parses lments).

Exemple 1.1.3. 1. E = {2, 4, 6} est donn en extension2. E = {x N | x est pair et 1 x 7} est le mme ensemble donn en comprhension.

Dfinition 1.1.2. Il existe un ensemble ne contenant aucun lment. On appelle cet ensemble ensemblevide et on le note .

1. Leonhard Paul Euler, voir chapitre 6 page 51

1

2 Thorie des ensembles

Figure 1.1 Diagramme dEuler de lensemble E

Il y a une infinit de faons de dcrire un ensemble donn, la plus simple est souvent la meilleure !

{x N | x+ 1 = 0} =

a y est, vous savez ce quest un ensemble, il est temps den prendre plusieurs et de jouer un peuavec. Peut-on mettre un ensemble dans un autre ? Des lments peuvent-ils tre dans plusieurs ensemblesdiffrents ? Comment enlever des lments dun ensemble ? Bref, cest le moment de vous poser desquestions, je rpondrai certaines dans la suite, pour les autres, essayez dy rpondre par vous-mmes !

1.1.2 Inclusion, parties

Dfinition 1.1.3. On dit que lensemble F est inclus dans lensemble E, et on note F E, si tous leslments de F sont lments de E.

F E x F, x E

On dit aussi que F est une partie de E ou un sous-ensemble de E.On note P(E) lensemble des parties de E.

Attention ne pas confondre lappartenance et linclusion.Lappartenance se note et linclusion se note .

Exemple 1.1.4. F = {a, b, u} E = {a, b, g, u, i,m} (voir figure 1.2)Exemple 1.1.5. Soit lensemble E = {a, b, c}.

llment a appartient lensemble E (a E) lensemble {a, b} est inclus dans lensemble E ({a, b} E) P(E) = {, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}

1.1. Ensembles et oprations 3

Figure 1.2 F est inclus dans E

Proposition 1.1.1. Deux ensembles A et B sont gaux (i.e. contiennent exactement les mmes lments)

si et seulement si

A BetB A

do la maxime, fort utile en pratique pour dmontrer une galit :

Une galit, cest deux inclusions

1.1.3 Oprations sur les ensembles

Dfinition 1.1.4. Soient A et B deux ensembles inclus dans E. On dfinit les oprations suivantes :

IntersectionA B = {x E / x A et x B}

RunionA B = {x E / x A ou x B}

ComplmentaireA = {x E / x / A}

DiffrenceA \B = {x E / x A et x / B}

Exemple 1.1.6. Les diagrammes dEuler de la figure 1.3 illustrent ces diffrentes oprations.

Toutes ces oprations permettent de crer de nouveaux ensembles partir densembles de dpart. Lersultat nest pas toujours simple deviner, et il nest pas rare davoir une criture trs complexe pour

un ensemble qui ne contient peut-tre pas dlment ! Comme pour les oprations sur les nombres rels, il y a unordre respecter quand on enchane plusieurs des ces oprations. Que pensez-vous de lcriture suivante :

A B C \A B \A ?

4 Thorie des ensembles

(A) Intersection - A B = {u} (B) Runion - A B = {a, b, g, i, u}

(C) Complmentaire - A = {i,m} (D) Diffrence - A \B = {a, b, g}Figure 1.3 Oprations sur les ensembles

1.2 Proprits

Une fois ces oprations dfinies, nous nous intressons leurs proprits. Citons tout dabord lesproprits classiques de commutativit et dassociativit.

Proposition 1.2.1. Soient A, B et C trois parties dun ensemble E. Commutativit

A B = B A et A B = B A Associativit

(A B) C = A (B C)et

(A B) C = A (B C)Remarque. On peut donc omettre les parenthses et crire par exemple A B C. En revanche, ilpeut arriver que (A B) C 6= A (B C), lcriture A B C ne veut donc rien dire !

Si vous ne voulez pas perdre btement des points lors dun examen a, vous vrifierez bien que vous nedrogez pas la rgle suivante :

On ne mlange pas les et les sans mettre de parenthses !a. et vous ne le voulez pas nest-ce pas ?

1.3. Application entre deux ensembles 5

Les proprits qui suivent peuvent sembler moins videntes la premire lecture. Je ne saurais quetrop vous conseiller de faire un diagramme dEuler illustrant chaque proprit afin de vous en convaincre.

Proposition 1.2.2. Soient A, B et C trois parties dun ensemble E. Distributivit

A (B C) = (A B) (A C)et

A (B C) = (A B) (A C) Formules de De Morgan

A B = A B

A B = A B Absorption

Si A B, alors A B = A et A B = B Elments particuliers

A = A E = A

A = A A E = E

1.3 Application entre deux ensembles

Les ensembles sont donc des collections dobjets, mais qui ninteragissent pour linstant pas entre eux.Nous allons maintenant voir comment on peut faire des associations entre deux ensembles diffrents. Ceconcept dassociation entre deux objets est fondamental en mathmatiques et permet de modliser desconcepts comme des transformations, des relations. . . que nous rencontrerons dans les diffrents cours.

1.3.1 Dfinitions

Dfinition 1.3.1. Soient A et B deux ensembles. Une application f : A B est un procd qui associe tout lment x de A un unique lment y de B.A est appel lensemble de dpart et B lensemble darrive.On note y = f(x) ; y est appel l image de x par f et x est appel lantcdent de y par f .

1.3.2 Applications injectives, surjectives, bijectives

On distinguera parmi les applications entre deux ensembles celles qui nenvoient pas deux lmentsdiffrents vers un mme lment (applications injectives) et celles qui occupent tout lespace darrive(applications surjectives). La dfinition suivante formalise ces notions.

Dfinition 1.3.2. 1. f est dite injective si x1, x2 A, (f(x1) = f(x2) x1 = x2)2. f est dite surjective si ( y B, x A; y = f(x))3. f est dite bijective si f est injective et surjective

La figure 1.4 illustre ces notions.

6 Thorie des ensembles

(a) (b) (c)

Figure 1.4 Application (a) injective, (b) surjective, (c) bijective

1.3.3 Application rciproque

Dire quune application f de E dans F est bijective, cest dire que tout lment y F admet ununique antcdent x E. On peut donc dfinir une application en associant tout lment y de F sonunique antcdent x dans E.

Cette application est alors appele application rciproque de f et est note f1.

Exemple 1.3.1. Lapplication f(x) = x2 dfinie de R+ vers R+ admet une rciproque quon note habi-tuellement

x.

1.3.4 Compose

Dfinition 1.3.3. Soient E, F et G trois ensembles et soient f une application de E vers F et g uneapplication de F vers G.A tout lment x de E, on peut faire correspondre un lment y de F par f puis cet lment y, on peutfaire correspondre un lment z de G par g. Lapplication de E dans G qui x de E fait correspondrellment z de G est appele application compose de f et g et se note g f .Autrement dit, (g f)(x) = g(f(x))Exemple 1.3.2. Considrons f(x) = x2 et g(x) = 2x+ 3. Calculer g f puis f g.Quen pensez-vous ?

Thorme 1.3.1. Soient E, F et G trois ensembles et soient f une application de E vers F et g uneapplication de F vers G.

1. Si f et g sont injectives, alors g f est injective.2. Si f et g sont surjectives, alors g f est surjective.3. Si f et g sont bijectives, alors g f est bijective et (g f)1 = f1 g1.

1.4 Cardinal

1.4.1 Ensemble fini

Pour les ensembles contenant un nombre fini dlments, on souhaite tudier le lien entre les oprationset le nombre dlments de chaque ensemble. Ceci nous permettra de faire du dnombrement et ainsi dersoudre des problmes complexes via une modlisation en thorie des ensembles.

Dfinition 1.4.1. Si un ensemble A a un nombre fini dlments, on note |A| ou ]A, et on appellecardinal de A, le nombre dlments de A.

1.5. Miscellannes 7

Proposition 1.4.1. Soient A et B deux parties de E. |A B| = |A|+ |B| |A B| A B |A| |B| |P(E)| = 2|E|

Dmonstration. Pour la premire proprit, il sufft de constater que quand on ajoute le nombre dlmentsde A et le nombre dlments de B, on compte deux fois ceux qui sont la fois dans A et dans B. Leseconde proprit est vidente puisque tout lment de A est galement dans B, donc B contient auminimum autant dlment que A. La dernire proprit peut se dmontrer par rcurrence, je vous lalaisse en exercice, nous en dirons quelques mots en TD.

1.4.2 Proprits

Thorme 1.4.1. Soient E et F des ensembles finis.1. |E| = |F | si et seulement sil existe une bijection de E sur F2. |E| |F | si et seulement sil existe une injection de E sur F3. |E| |F | si et seulement sil existe une surjection de E sur F

Thorme 1.4.2. Soient E et F des ensembles finis de mme cardinal et f une application de E versF . Alors

fbijective f injective fsurjective

1.4.3 Ensemble dnombrable

Dfinition 1.4.2. Un ensemble E est dit dnombrable sil existe une bijection entre E et lensemble Ndes entiers naturels.

Exemple 1.4.1. lensemble des entiers pairs est dnombrable Q est dnombrable [0, 1] nest pas dnombrable

Il y aurait donc plusieurs infinis ? Peut-on les comparer ? Un dbut de rponse dans la section 1.5.2 etsuivantes a.

a. Quel teasing !

1.5 Miscellannes

1.5.1 Prouver une implication, une quivalence

Dans les exercices, il est souvent demand de prouver une implication entre deux propositions.

Pour dmontrer que (P1) (P2), on suppose que (P1) est vraie et on cherche dmontrer (P2).

Pour prouver une quivalence, nous avons la maxime suivante, hautement inspire de la maxime 1 :

8 Thorie des ensembles

Une quivalence, cest deux implications.

Pour dmontrer que (P1) (P2), on dmontre donc que (P1) (P2) et (P2) (P1).

Remarque. Pour montrer quune implication est fausse, il suffit de donner un contre-exemple, cest--dire un cas particulier o lhypothse est vrifie mais pas la conclusion.

1.5.2 Lhtel de linfini

Monsieur et Madame Hilbert sont les grants dun htel, appel humblement Htel de linfini. Cenom na pas t donn au hasard, leur htel comporte une infinit de chambres, numrotes par les entiersde 1 jusqu . . . linfini.

Cest la pleine saison touristique et toutes les chambres sont occupes quand arrive un touriste alle-mand.

Comment trouver une place libre dans un htel complet ? Monsieur Hilbert regarde Mme Hilbert puisson chat, et dcide de demander au client de la chambre 1 de dmnager dans la chambre 2, en disant auclient de la chambre 2 daller dans la chambre 3. . . et ainsi de suite jusqu linfini. Ainsi, la chambre 1sera libre pour notre touriste allemand !

Mme Hilbert na pas fini de fliciter M Hilbert pour son ingnieuse ide quun car de touristes arrive lhtel. De ce car, descend une infinit de touristes hollandais qui veulent tous dormir lhtel !

Comment trouver une infinit de places libres dans un htel complet ? Perplexe, Mme Hilbert regardeson mari qui la regarde ainsi que son chat, quand Mr Hilbert fait un appel au micro dans toutes leschambres. Il demande tous les clients de noter leur numro de chambre et daller dans la chambre quiporte le numro double du leur. Ainsi, le client de la chambre 1 va dans la 2, celui de la 2 va dans la 4,celui de la 3 va dans la 6 et ainsi se suite. . . Toutes les chambres portant un numro impair sont ainsilibres et peuvent accueillir tous les touristes hollandais !

1.5.3 Comparons les infinis

Il y a autant dentiers pairs que dentiers impairs On la vu dans lhistoire prcdente, il semble difficilede comparer des infinis, mais nous allons tout de mme tenter de le faire. Que pensez-vous de lide quily a autant dentiers pairs que dentiers impairs ? Elle semble intuitivement valable mais il faut donner unsens au mot autant dans un contexte densembles infinis. Lide la plus naturelle est de considrer quedeux ensemble possdent autant dlments si on peut trouver une application bijective entre ces deuxensembles. En effet, on cre ainsi une association 1--1 entre les lments des deux ensembles. Considronspar exemple lapplication suivante, qui va de lensemble A des entiers pairs vers lensemble B des entiersimpairs :

f : A Bn 7 n+ 1

Vous vrifierez que f est bien bijective, ce qui tend valider lhypothse que A et B ont autant dlments.

Il y a autant dentiers pairs que dentiers naturels Passons quelque chose qui vous semblera cer-tainement moins naturel. Que pensez-vous de lapplication suivante, qui va de lensemble N des entiersnaturels vers lensemble A des entiers naturels pairs :

f : N An 7 2n

1.5. Miscellannes 9

Elle est injective puisque deux entiers distincts senvoient toujours sur des entiers pairs distincts. Elle estsurjective puisque tout entier pair scrit comme un multiple de 2. Elle est donc bijective, ce qui prouvequil y a autant dentiers pairs que dentiers ! Etonnant non ? Mais ce nest pas fini. . .

Il y a autant dentiers relatifs que dentiers naturels Si vous avez bien suivi jusquici, vous avezcompris quil suffit de prouver que Z est en bijection avec N. Ce nest pas trop difficile, mme si un peuplus technique crire proprement. Lide est de chercher un moyen dnumrer les lments de Z, cequon peut faire assez naturellement en alternant les entiers positifs et ngatifs : 0, 1, -1, 2, -2, 3, -3. . . Jevous laisse vrifier que lapplication suivante convient :

f : N Zn 7 n+12 si n est impairn 7 n2 si n est pair

Il y a autant de rationnels que dentiers Intressons-nous dsormais lensemble des rationnels quiest lensemble des fractions pq avec p Z et q N, p et q tant sans diviseur commun. Je ne vaispas crire de faon explicite la bijection qui est plus dsagrable crire qu comprendre. Lide estla suivante : on souhaite trouver un moyen dnumrer toutes les fractions possibles, on dresse alorsun tableau qui numre en ligne les numrateurs possibles et en colonne les dnominateurs possibles.Enumrer les fractions revient trouver une mthode pour parcourir toutes les cases du tableau, ce quipeut tre fait en le lisant diagonale par diagonale :

HHHHHpq 1 2 3 . . .

1 1 2 6 . . .2 3 53 4...

Il y a donc autant de rationnels que dentiers naturels.

Et les rels ? Passons aux rels. Y a-t-il un moyen dnumrer tous les rels comme on la fait pour lesrationnels ? Et bien la rponse est non, et la dmonstration, due Georg Cantor 2, est particulirementjolie. Il sagit dune preuve par labsurde : supposons en effet quil soit possible dtablir une liste numrote(infinie bien sr !) des rels de lintervalle [0, 1[.

1 0, x1,1x1,2x1,3 . . .2 0, x2,1x2,2x2,3 . . .3 0, x3,1x3,2x3,3 . . ....

...

Construisons maintenant le rel dont lcriture dcimale est

0, y1y2y3 . . .

o les dcimales sont choisies telles que y1 6= x1,1, y2 6= x2,2, y3 6= x3,3. . .Ce rel, par construction, nest pas dans la liste ! En effet, a ne peut pas tre le premier car la

premire dcimale est diffrente, ni le second car la deuxime dcimale est diffrente, et ainsi de suite. . .Ceci prouve quil nest pas possible dtablir une liste numrote de tous les rels de [0, 1[. Il ny a doncpas autant dentiers que de rels.

2. Georg Cantor, voir chapitre 6 page 51

10 Thorie des ensembles

Une notation a t introduite pour exprimer que linfini des entiers est plus petit que linfini des rels :on dit que le cardinal de N est 0 (aleph 0) et le cardinal de R est 1 (aleph 1).

Lhypothse du continu est une conjecture qui affirme quil nexiste pas densemble dont le cardinalest strictement compris entre celui de N et celui de R.

1.5. Miscellannes 11

12 Thorie des ensembles

Partie 2

Logique

2.1 Logique propositionnelle

2.1.1 Proposition logique

Dfinition 2.1.1. On appelle proposition logique une affirmation ayant une valeur de vrit, i.e. qui estsoit vraie soit fausse.

Exemple 2.1.1. Les affirmations suivantes sont des propositions logiques ; lesquelles sont vraies ? fausses ? 2 + 3 = 5 pi = 7 2 < 4 3 est pair

Cette phrase est fausse nest pas une proposition logique car elle ne peut tre ni vraie ni fausse !

Le raisonnement scientifique consiste cherche connatre la valeur de vrit de diffrentes proposi-tions. Cette recherche se base sur des propositions dont les valeurs de vrit sont connues.

Le calcul propositionnel sintresse la faon dont les propositions sont lies entre elles et aux cons-quences quon peut en tirer sur leurs valeurs de vrit.

2.1.2 Connecteurs logiques

Ils vont permettre de construire de nouvelles propositions partir de propositions donnes, la valeurde vrit dpendant des valeurs de vrit des propositions donnes.

Dfinition 2.1.2. La ngation dune proposition p, note p, a pour valeur V si p a pour valeurF et F si p a pour valeur V . Sa table de vrit est :

p pV FF V

13

14 Logique

La conjonction de deux propositions p et q, note p q, a pour valeur V ssi p et q sont toutes lesdeux vraies. Sa table de vrit est :

p q p qV V VV F FF V FF F F

La disjonction de deux propositions p et q, note p q, a pour valeur V ssi p ou q (ou les deux) estvraie. Sa table de vrit est :

p q p qV V VV F VF V VF F F

Exemple 2.1.2. On considre les propositions logiques p = 6 est divisible par 2 q = 6 est divisible par 3

Alors p = 6 nest pas divisible par 2, pq = 6 est divisible par 2 et par 3 et pq = 6 est divisible par 2 ou par 3.

Aprs ces connecteurs de base, nous allons voir des connecteurs plus sophistiqus : limplication etlquivalence.

Dfinition 2.1.3. L implication, note p q, a pour valeur V ssi (p est vraie et q est vraie) ou(p est faux et q est quelconque). Sa table de vrit est :

p q p qV V VV F FF V VF F V

On crira p q si la proposition p q est vraie.

Lquivalence de deux propositions p et q, note p q, a pour valeur V ssi p et q ont mme valeurde vrit. Sa table de vrit est :

p q p qV V VV F FF V FF F V

On crira p q si la proposition p q est vraie.

Limplication est intuitivement la plus difficile apprhender : le faux implique nimporte quoi ! Parexemple, notons p la proposition logique je cours le 100m en 5 secondes et q la proposition les Info1

auront tous 20/20 au prochain examen. Et bien limplication p q est vraie quelle que soit la valeur de vritde q, simplement car p est faux.

2.1. Logique propositionnelle 15

2.1.3 Formules propositionnelles

Dfinition 2.1.4. On appelle formule propositionnelle la combinaison de propositions logiques et deconnecteurs logiques. On peut crire la table de vrit dune telle formule en fonction des valeurs desvrit des propositions qui la constituent.

Exemple 2.1.3. Si p et q sont deux propositions logiques, alors (p)q est une formule propositionnelle.Sa table de vrit est

p q (p) qV V VV F FF V VF F V

Remarque. Si deux formules propositionnelles ont la mme table de vrit, on dit quelles sont logique-ment quivalentes et on crira lgalit entre les deux formules.

Exemple 2.1.4. 1. On vient de voir que p q = (p) q2. exercice : montrer que p q = (p q) (q p)

On distingue les formules propositionnelles qui sont toujours vraies et celles qui sont toujours fausses :

Dfinition 2.1.5. On appelle tautologie une formule propositionnelle qui est toujours vraie.On appelle antilogie une formule propositionnelle qui est toujours fausse.

2.1.4 Proprits

Les connecteurs logiques que nous avons dfinis satisfont un certain nombre de proprits numresdans la proposition suivante. Celles-ci nous permettront souvent de simplifier une formule propositionnelle.

Proposition 2.1.1. (i) (p) = p(ii) associativit

(p q) r = p (q r) et (p q) r = p (q r)

(iii) commutativitp q = q p et p q = q p

(iv) idempotencep p = p et p p = p

(v) distributivit

p (q r) = (p q) (p r) et p (q r) = (p q) (p r)

(vi) loi de De Morgan(p q) = (p) (q) et (p q) = (p) (q)

Dmonstration. Cest un excellent exercice qui vous fera manipuler les tables de vrit.

16 Logique

2.2 Prdicats et quantificateurs

2.2.1 Prdicats

Dfinition 2.2.1. Un prdicat est une proposition logique P (x) qui dpend dune variable x. La valeurde vrit de P (x) dpend du choix de x.

Exemple 2.2.1. 1. P1(x) =x est pair, alors P1(2) est vrai mais P1(3) est faux.2. P2(x) =x > x 1, alors P2(x) est toujours vrai quand x est dans R.3. P3(x) =x 6= x, alors P3(x) est toujours faux.

- Un prdicat peut dpendre de plusieurs variables (par ex. P (x, y) =x

2.2. Prdicats et quantificateurs 17

(c) Il existe un unique

Quand un prdicat P (x) est vrai pour exactement une valeur de x dun ensemble E, on crit

! x E, P (x)et on dit Il existe un unique x dans E, P (x)

Exemple 2.2.4. ! x ] 1, 1[, x2 = 0

2.2.3 Quantificateurs et connecteurs logiques

Un prdicat auquel on applique un quantificateur devient une proposition logique. Vous tes certai-nement impatients dappliquer les diffrents connecteurs , et ces quantificateurs et dobserver cequon obtient. Il est alors urgent de faire trs attention ce que vous crivez car une erreur est trs vitearrive et peut en un instant transformer un nonc correct en horreur innommable !

Vous retiendrez donc deux choses trs importantes :

1) Il faut faire trs attention quand on mlange quantificateurs et connecteurs lo-giques !

2) Ne jamais intervertir quantificateur et connecteur, ni deux quantificateurs sans avoir pris la peine derflchir.

(i) effet de la ngation sur les quantificateurs

( x E, P (x)

)= x E, (P (x))

( x E, P (x)

)= x E, (P (x))

(ii) effet de la conjonction sur les quantificateurs

x E,(P (x) Q(x)

)

( x E,P (x)

)( x E,Q(x)

)x E,

(P (x) Q(x)

)=

( x E,P (x)

)( x E,Q(x)

)

Dans la deuxime implication la rciproque est fausse !

Penser E = Z, P (x) =x est pair, Q(x) =x est impair

18 Logique

(iii) effet de la disjonction sur les quantificateurs

x E,(P (x) Q(x)

)=

( x E,P (x)

)( x E,Q(x)

)x E,

(P (x) Q(x)

)

( x E,P (x)

)( x E,Q(x)

)

Dans la premire implication la rciproque est fausse !Le mme exemple que prcdemment le prouve.

2.3 Thormes et dmonstrations

Tout ce quon vient de voir, ce sont les outils qui vont nous permettre dlaborer des dmonstrationsrigoureuses. Un thorme est un rsultat obtenu en faisant oprer des oprations logiques sur des objetsmathmatiques (dfinis dans des dfinitions) et des rsultats connus. Afin dinitier la thorie, on dfiniun ensemble daxiomes (grosso modo liste de rsultats considrs comme vrais, aucun ntant une cons-quence des autres, lensemble ne prsentant aucune contradiction), puis chaque rsultat prouv enrichitlensemble des rsultats connus. 2

Voici quelques exemples de types de dmonstrations :1. Preuve par labsurde : pour prouver lnonc P, on fait lhypothse quil est faux et on montre quon

aboutit une contradiction.Exemple 2.3.1. La dmonstration que

2 R \Q est une trs jolie dmonstration par labsurde,

dont les arguments ne demandent que trs peu de connaissances mathmatiques.2. Pour prouver une implication P Q, on suppose que P est vraie et on procde des dductions

jusqu prouver que Q est vraie. En effet, dans le cas o P est fausse, limplication est toujoursvraie.

3. Disjonction de cas : quand le nombre de possibilit est fini, il est envisageable dtudier tous les caspossibles.Exemple 2.3.2. pour montrer que (P Q) R, il suffit de montrer que P R et Q R. exercice : montrer que le carr de tout rel est positif ou nul (considrer les cas x 0 et x < 0).

4. Contrapose : base sur lquivalence (P Q) (Q P )Exemple 2.3.3.

A B B A5. Raisonnement par rcurrence : on souhaite montrer quun prdicat P (n) est vrai pour toutes les

valeurs de n, on dmontre tout dabord que P (0) est vrai, puis que limplication P (n) P (n+ 1)est vraie.Exemple 2.3.4. Exercice : montrer que n N, n < 2n.

2. Avez-vous une ide du nombre de nouveaux thormes dmontrs chaque anne dans le monde ?

2.3. Thormes et dmonstrations 19

La logique, a se cultive !

20 Logique

Partie 3

Relations sur un ensemble

3.1 Dfinition

3.1.1 Ensemble produit

Dfinition 3.1.1. Le produit cartsien de deux ensembles A et B est lensemble de tous les couples (a, b)o a A et b B. On le note AB (A croix B).

AB = {(a, b) | a A, b B}

Proposition 3.1.1. Si A et B sont des ensembles finis, alors AB aussi et

|AB| = |A| |B|

Si B = A, alors on note parfois AA = A2, AAA = A3 . . .Vous avez certainement dj rencontr les ensembles R2 (le plan) et R3 (lespace).

3.1.2 Relation binaire

Dfinition 3.1.2. Une relation binaire R dun ensemble A sur un ensemble B est un sous-ensemble deAB.

Si (a, b) est un lment de la relation R, on dit que a est en relation avec b et on note aRb.

Une relation R sur un ensemble E est une relation de E sur E, cest--dire un sous-ensemble de E E.

Exemple 3.1.1. E = {1, 2, 3, 4} R = {(1, 2); (1, 3); (1, 4); (2, 3); (2, 4); (3, 4)}On a 1R2, 2R4 mais pas 3R1

21

22 Relations sur un ensemble

On peut galement dfinir une relation en donnant une condition ncessaire et suffisante pour quedeux lments x et y soient en relation.

Exemple 3.1.2. E = {1, 2, 3, 4} xRy x yOn a 2R1, 3R3 mais pas 1R4

3.1.3 Reprsentation matricielle

Dfinition 3.1.3. Soit E lensemble {1, 2, . . . , n}. On appelle matrice dune relation R sur E le tableau n lignes et n colonnes dont llment la ligne i et la colonne j vaut 1 si iRj et 0 sinon.Exemple 3.1.3. E = {1, 2, 3, 4}, xSy x y

M =

1 0 0 01 1 0 01 1 1 01 1 1 1

3.1.4 Reprsentation sagittale

Dfinition 3.1.4. Soit E lensemble {1, 2, . . . , n}. On appelle reprsentation sagittale ou graphe dunerelation R sur E le graphe dont les sommets sont les lments de E et pour lequel il y a une flche dusommet x vers le sommet y si xRy.Exemple 3.1.4. E = {1, 2, 3, 4}, xSy x y

1-- 2oo qq

3

OO @@11 4oo

^^>>>>>>>

OO

mm

3.2 Oprations sur les relations

Les relations sur E tant des sous-ensembles de E E, on peut leur appliquer les oprations sur lesensembles.

Soient R et S deux relations sur E. On dfinit :

la runion : R Sa(R S)b (aRb) ou (aSb)

lintersection : R Sa(R S)b (aRb) et (aSb)

3.3. Proprits 23

le complmentaire : RaRb (aRb)

La notion de relation binaire nest pas commutative, on introduit ainsi lopration de rciproque quichange les variables :

la transpose : Rta(Rt)b bRa

Exemple 3.2.1. Considrons lensemble E = {a, b, c, d} et les relations R = {(a, a), (a, b), (b, a), (b, c), (c, d)}et S = {(a, b), (b, a), (b, c), (c, b), (d, b), (d, c)}. Dcrivez les diffrentes oprations dfinies ci-dessus et don-ner leur reprsentation matricielle et sagittale. Comment obtient-on la matrice et les graphes des relationsR S, R S, R, et Rt en fonction des matrices et grpahes de R et S ?

3.3 Proprits

3.3.1 rflexivit

Dfinition 3.3.1. La relation R est dite rflexive si

x E, xRx

Exemple 3.3.1. Sur lensemble E = {1, 2, 3, 4}, la relation R dfinie par

xRy x|y (x divise y)

est rflexive car 1|1, 2|2, 3|3 et 4|4.Exemple 3.3.2. Sur lensemble E = {1, 2, 3, 4}, la relation R dfinie par

xRy x < y

nest pas rflexive car 1 nest pas strictement infrieur 1 !

Sur la matrice, la rflexivit se traduit par une diagonale ne contenant que des 1. Dterminez dansles matrices suivantes, lesquelles sont des matrices reprsentant une relation rflexive :

M1 =

1 0 11 1 00 0 1

M2 = 1 0 10 0 1

1 0 1

M3 =

1 1 0 11 1 0 01 1 1 10 1 1 0

M4 =

1 0 1 0 00 1 0 0 01 0 1 0 00 1 1 1 00 0 0 1 1

Sur le graphe, cel se traduit par la prsence dune boucle sur chaque sommet. Dterminez dans

les graphes de la figure 3.1, lesquels sont des graphes reprsentant une relation rflexive.

24 Relations sur un ensemble

G1 : 1-- 2oo qq

3

OO @@11 4oo

^^>>>>>>>

OO

mm

G2 : a boo qq

c

OO

11 doo

OO

G3 : 1-- 2 qq

311 4 mm

G4 : a qq

vvb

77

** c mmjj

Figure 3.1 Saurez-vous trouver les proprits de ces graphes ?

3.3.2 Symtrie

Dfinition 3.3.2. La relation R est dite symtrique si (x, y) E E, xRy yRx

Exemple 3.3.3. Sur lensemble E = {1, 2, 3, 4}, la relation R dfinie parxRy x|y (x divise y)

nest pas symtrique car 2 divise 4 mais 4 ne divise pas 2.

Exemple 3.3.4. Sur lensemble E = {1, 2, 3, 4}, la relation R dfinie parxRy x a la mme parit que y

est symtrique car si x a la mme parit que y alors il est clair que y a la mme parit que x.

Sur la matrice, la symtrie se traduit par la symtrie de la matrice par rapport sa diagonale (sily a un 1 la place i, j, alors il y a galement un 1 la place j, i. Dterminez dans les matrices suivantes,lesquelles sont des matrices reprsentant une relation symtrique :

M1 =

1 1 01 1 00 0 1

M2 = 1 0 10 0 1

1 0 1

M3 =

1 1 0 11 1 0 01 1 1 10 1 1 0

M4 =

1 0 1 0 00 1 0 1 01 0 0 1 00 1 1 1 00 0 0 0 1

Sur le graphe, la symtrie se traduit par la non prsence de flche simple. Autrement dit, ds quil

y a une flche entre deux sommets, il doit y avoir galement la flche dans lautre sens. Dterminez dansles graphes de la figure 3.1, lesquels sont des graphes reprsentant une relation symtrique.

3.3.3 Antisymtrie

Dfinition 3.3.3. La relation R est dite antisymtrique si (x, y) E E, xRy et yRx x = y

3.3. Proprits 25

Exemple 3.3.5. Sur lensemble E = {1, 2, 3, 4}, la relation R dfinie par

xRy x|y (x divise y)

est antisymtrique car si x|y et y|x alors x = y.Exemple 3.3.6. Sur lensemble E = {1, 2, 3, 4}, la relation R dfinie par

xRy x a la mme parit que y

nest pas antisymtrique car 2 et 4 ont la mme parit et pourtant 2 6= 4.

Sur la matrice, lantisymtrie se traduit par le fait suivant : sil y a un 1 dun ct de la diagonale,alors il doit y avoir un 0 lemplacement symtrique par rapport la diagonale. Dterminez dans lesmatrices suivantes, lesquelles sont des matrices reprsentant une relation antisymtrique :

M1 =

1 0 11 1 00 0 1

M2 = 1 0 10 0 1

1 0 1

M3 =

1 1 0 10 1 0 01 1 1 10 1 0 0

M4 =

1 0 1 0 00 1 0 0 01 0 1 0 00 1 1 1 00 0 0 1 1

Sur le graphe, cel se traduit par la non prsence de flche double (il peut en revanche y avoir des

boucles). Dterminez dans les graphes de la figure 3.1, lesquels sont des graphes reprsentant une relationantisymtrique.

3.3.4 Transitivit

Dfinition 3.3.4. La relation R est dite transitive si

(x, y, z) E3, xRy et yRz xRz

Exemple 3.3.7. Sur lensemble E = {1, 2, 3, 4}, la relation R dfinie par

xRy x|y (x divise y)

est transitive car si x|y et y|z alors x|z.Exemple 3.3.8. Sur lensemble E = {1, 2, 3, 4}, la relation R dfinie par

xRy |x y| 1

nest pas transitive car 1R2 et 2R3 mais 1 nest pas en relation avec 3.

Sur la matrice, la transitivit ne se traduit pas par une rgle simple qui se voit directement surla matrice. Il est toutefois possible de vrifier toutes les relations possibles. Dterminez dans les matricessuivantes, lesquelles sont des matrices reprsentant une relation transitive :

M1 =

1 0 11 1 00 0 1

M2 = 1 0 10 0 1

1 0 1

26 Relations sur un ensemble

M3 =

1 1 0 11 1 0 01 1 1 10 1 1 0

M4 =

1 0 1 0 00 1 0 0 01 0 1 0 00 1 1 1 00 0 0 1 1

Sur le graphe, cel se traduit par le fait suivant : sil y a une flche dun sommet x un sommet y

et une flche du sommet y un sommet z, alors la flche raccourci de x z doit apparatre galement.Dterminez dans les graphes de la figure 3.1, lesquels sont des graphes reprsentant une relation transitive.

3.4 Relation dquivalence

3.4.1 Dfinition

Dfinition 3.4.1. Une relation ayant les proprits de rflexivit, de symtrie et de transitivit est ap-pele relation dquivalence.

Soit R une relation dquivalence sur un ensemble E. On appelle classe dquivalence dun lment xde E, et on note x, lensemble des lments de E en relation avec x

x = {y E | xRy}Lensemble des classes dquivalences de la relation R est appel ensemble quotient et se note E/R.

3.4.2 Proprits

Le concept de relation et de classes dquivalence peut tre vu comme le regroupement en sous-ensembles des lments en relation les uns avec les autres. Ce concept peut paratre abstrait mais permetpar exemple de construire lensemble des rationnels (lide est de regrouper les diffrentes critures dunemme fraction et de les identifier un seul lment (cf. TD)). Les proprits qui suivent sont importanteset permettent de mieux comprendre la notion.

Proposition 3.4.1. Si y x, alors x = y.

Dmonstration. On suppose que y x, cest--dire que yRx. Montrons tout dabord que x y. Soit z x, cel signifie que zRx. Or on sait que xRy (car yRxet la relation est symtrique), donc par transitivit, on en dduit que zRy, ce qui signifie que z y.

Montrons maintenant linclusion inverse : y x. Soit z y, cel signifie que zRy. Or on sait queyRx, donc par transitivit, on en dduit que zRx, ce qui signifie que z x.

Ce rsultat signifie que nimporte quel lment dune classe peut reprsenter la classe toute entire.On dira que x est un reprsentant de la classe x. Mais si y x, alors y peut tre choisi pour reprsenterla mme classe car y = x.

Proposition 3.4.2. Lensemble des classes dquivalence sur un ensemble E forme une partition de E(i.e. E est gal la runion disjointe de ses classes dquivalence).

3.4.3 Exemples

Exemple 3.4.1. Sur Z, la relation dfinie par xRy 12|(x y) est une relation dquivalence.Exemple 3.4.2. Construction de Q cf TD

3.5. Relation dordre 27

3.5 Relation dordre

3.5.1 Dfinition

Dfinition 3.5.1. Une relation ayant les proprits de rflexivit, dantisymtrie et de transitivit estappele relation dordre.

Si deux lments quelconques de E sont comparables, i.e.

(x, y) E E, xRy ou yRx,la relation est dite dordre total, sinon elle est dite dordre partiel.

Dfinition 3.5.2. Soit R une relation dordre sur un ensemble E et soient x et y deux lments compa-rables.

Si xRy, on dit que x minore y ou que y majore x.Exemple 3.5.1. Sur N, la relation xRy x y est une relation dordre total.

Sur N, la relation xRy x est un multiple de y est une relation dordre partiel. En effet, on na ni2 est un multiple de 3 ni 3 est un multiple de 2 par exemple.

3.5.2 Diagramme de Hasse

Dfinition 3.5.3. Soit R une relation dordre sur E. On dit quun lment y E domine un lmentx E si xRyx 6= yil nexiste pas dlment z E; xRz et zRy (z 6= x, y)Cette relation est appele couverture de la relation R.

Son graphe est appel diagramme de Hasse 1 de la relation R.

1. On obtient le diagramme de Hasse dune relation dordre en retirant les boucles et les raccourcis.2. Dans un diagramme de Hasse, il ne peut pas y avoir de circuit, sinon la relation de dpart ne serait pas

antisymtrique.

Exemple 3.5.2. Donner le diagramme de Hasse de la relation divise sur lensemble E = {1, 2, 3, 4, 5, 6}.

3.5.3 lments particuliers dun ensemble ordonn

Dfinition 3.5.4. Soient E un ensemble, R une relation dordre sur E et F une partie de E. Un majorant de F est un lment b de E qui majore tous les lments de F .

x F, xRb Un minorant de F est un lment a de E qui minore tous les lments de F .

x F, aRx1. Helmut Hasse voir chapitre 6 page 53

28 Relations sur un ensemble

Le maximum de F est, sil existe, un lment de F qui est majorant de F . Le minimum de F est, sil existe, un lment de F qui est minorant de F . La borne suprieure de F est, le minimum de lensemble des majorants de F . La borne infrieure de F est, le maximum de lensemble des minorants de F . Un lment maximal de F est un lment de F qui na pas de majorant dans F . Un lment minimal de F est un lment de F qui na pas de minorant dans F .

Le maximum et la borne suprieure sont uniques sils existent.On appelle respectivement lment nul et lment universel de (E,R) le minimum et le maximum de

lensemble E.

3.5.4 Exemple

On considre lensemble E = {diviseurs de 30} = {1, 2, 3, 5, 6, 10, 15, 30}, muni de la relation xRy x|y. Son diagramme de Hasse est

2 //

@@@

@@@@

@ 6

BBB

BBBB

B

1

@@//

>>>

>>>>

3

>>~~~~~~~~

@@@

@@@@

@ 10 // 30

5 //

>>~~~~~~~~15

>>||||||||

Figure 3.2 Diagramme de Hasse de la relation divise sur lensemble des diviseurs de 30

Les lments particuliers pour les sous-ensembles F = {1, 2, 5} et G = {2, 6} sont consigns dans letableau suivant :

F = {1, 2, 5} G = {2, 6}majorants 10,30 6,30minorants 1 1,2maximum - 6minimum 1 2borne suprieure 10 6borne infrieure 1 2lments maximaux 2,5 6lments minimaux 1 2

3.5. Relation dordre 29

Les liens familiaux sont un bon exemple de relation

30 Relations sur un ensemble

Partie 4

Thorie des graphes : introduction

4.1 Graphes et modlisation

De manire gnrale, un graphe est un ensemble de sommets et dartes (ou arcs) reliant ces sommets.Cet objet trs simple permet de modliser des situations trs diffrentes :

relation sur un ensemble fini (cf chapitre prcdent) circulation dans une ville : sommets=carrefours, arcs=rues (ventuellement en sens unique) plan de mtro : sommets=arrts, artes=voies rseau informatique : sommets=ordinateur, artes=connexions physiques gestion de projet : sommets=tches, arcs=une tche ne peut commencer que si la prcdente esttermine

Il existe diffrents types de graphes, orients ou non, ou autorisant plusieurs arcs entre deux sommets.

4.2 Graphe orient

Dfinition 4.2.1. Un graphe orient est un couple G = (S,A) o S est un ensemble fini appel ensembledes sommets et A est un sous-ensemble de S S appel ensemble des arcs.

Une manire de visualiser un graphe est sa reprsentation sagittale : on dessine un point pour chaquesommet et les arcs entre deux sommets sont reprsents par une flche.

Exemple 4.2.1.S = {a, b, c, d} A = {(a, b), (b, a), (b, d), (c, c), (c, d)}

a''bhh

c-- // d

Figure 4.1 Reprsentation sagittale du graphe de lexemple 4.2.1

Dfinition 4.2.2 (Terminologie). Soient G = (S,A) un graphe orient et a = (x, y) A un arc de G. x est appel lorigine de a et y lextrmit de a. On dit aussi que y est un successeur de x ou que x est un prdcesseur de y.

31

32 Thorie des graphes : introduction

Un arc de la forme (x, x) est appel une boucle. On notera

+(x) = {y S | y successeur de x} lensemble des successeurs dun sommet x

et(x) = {y S | y prdecsseur de x} lensemble des prdcesseurs dun sommet x

On dfinit alorsd+(x) = |+(x)| = degr extrieur de xd(x) = |(x)| = degr intrieur de x

etd(x) = d+(x) + d(x) = degr de x

Attention, sil y a une boucle (x, x) au sommet x, alors x est la fois son propre successeur et son propreprdcesseur.

Dfinition 4.2.3. Soit G = (S,A) un graphe avec S = {x1, x2, . . . , xn}.On appelle matrice dadjacence du graphe G la matrice M = (ai,j)1in

1jncarre dordre n dfinie par

ai,j ={

1 si (xi, xj) A0 sinon

On appelle liste dadjacence du graphe G la liste des successeurs pour chaque sommet.

Exemple 4.2.2. La matrice dadjacence du graphe de lexemple 4.2.1 est

M =

0 1 0 01 0 0 10 0 1 10 0 0 0

Sa liste dadjacence est

a bb a dc c dd

quon peut aussi crire sous la forme {{b}, {a, d}, {c, d}, {}}.

Limplmentation dun graphe en machine passe par le choix dune de ces reprsentations. Quelle est votre avis la meilleure ?

4.3. Graphe non orient 33

4.3 Graphe non orient

Dfinition 4.3.1. Un graphe non orient est un couple G = (S,A) o S est un ensemble fini appelensemble des sommets et A est un ensemble de paires (non ordonnes) de sommets appel ensemble desartes.

Comme pour les graphes orients, on peut visualiser un graphe via sa reprsentation sagittale : ondessine un point pour chaque sommet et chaque arte entre deux sommets est reprsente par un segment.

A tout graphe orient est associ le graphe non orient obtenu en oubliant lorientation, i.e. en remplaantles arcs par des artes.

Exemple 4.3.1.S = {a, b, c, d} A = {(a, b), (b, d), (c, c), (c, d)}

a b

c d

Figure 4.2 Reprsentation sagittale du graphe de lexemple 4.3.1

Dfinition 4.3.2 (Terminologie). Soient G = (S,A) un graphe non orient et a = (x, y) A une artede G.

x et y sont les extrmits de a. On dit aussi que x et y sont voisins. Une arte de la forme (x, x) est appele une boucle. On notera

(x) = {y S | y voisin de x} lensemble des voisins dun sommet x On dfinit alors le degr dun sommet x :

d(x) ={ |(x)| sil ny a pas de boucle en x|(x)|+ 1 sinon

Dfinition 4.3.3. Soit G = (S,A) un graphe non orient avec S = {x1, x2, . . . , xn}.On appelle matrice dadjacence du graphe G la matrice M = (ai,j)1in

1jncarre dordre n dfinie par

ai,j ={

1 si (xi, xj) A0 sinon

On appelle liste dadjacence du graphe G la liste des successeurs pour chaque sommet.

La matrice dadjacence dun graphe non orient est ncessairement symtrique.

34 Thorie des graphes : introduction

Exemple 4.3.2. La matrice dadjacence du graphe de lexemple 4.3.1 est

M =

0 1 0 01 0 0 10 0 1 10 1 1 0

Sa liste dadjacence est

a bb a dc c dd b c

quon peut aussi crire sous la forme {{b}, {a, d}, {c, d}, {b, c}}.

4.4 Graphe partiel et sous-graphe

Dfinition 4.4.1. Le graphe partiel dun graphe G = (S,A), orient ou non, engendr par un sous-ensemble A de A, est le graphe G = (S,A).

Dfinition 4.4.2. Le sous-graphe dun graphe G = (S,A), orient ou non, engendr par un sous-ensemble de sommets S de S, est le graphe G = (S, AS) o (x, y) AS si et seulement si x S,y S et (x, y) A.

4.5 Thorme des poignes de mains

Thorme 4.5.1. Soit G = (S,A) un graphe orient. On axS

d(x) =xS

d+(x) = |A|

Si G = (S,A) est un graphe non orient, on axS

d(x) = 2|A|

Corollaire 4.5.1. Dans un graphe, le nombre de sommets de degr impair est toujours pair.

4.6 Chemin, chane, circuit et cycle

4.6.1 Vocabulaire

Dfinition 4.6.1. Soit G = (S,A) un graphe orient. Un chemin C de longueur k dun sommet x versun sommet y est une suite (x0, x1, . . . , xk) de sommets tels que x0 = x, xk = y et (xi1, xi) A pouri = 1, 2, . . . , k.

x est appel lorigine et y lextrmit du chemin C. La longueur dun chemin est le nombre darcs dans le chemin. Un sommet y est dit accessible partir dun sommet x sil existe un chemin de x vers y.

Dfinition 4.6.2. Soit G = (S,A) un graphe orient. Un circuit est un chemin de longueur non nulledont lextrmit et lorigine sont identiques.

4.7. Exercices 35

Dfinition 4.6.3. Un chemin ou un circuit est dit simple sil ne contient pas deux fois le mme arc ; lmentaire sil ne passe pas deux fois par le mme sommet ( lexception de lorigine et de lextr-mit pour un circuit)

Un chemin lmentaire est toujours simple. En effet, si un chemin passe deux fois par le mme arc, il passeobligatoirement plusieurs fois par les extrmits de cet arc.

Dfinition 4.6.4. Les notions correspondantes existent pour les graphes non orients. On utilise alorsplutt le vocabulaire suivant :

Orient Non orientarc arte

chemin chanecircuit cycle

4.6.2 Utilisation de la matrice dadjacence

Dfinition 4.6.5. On dfinit le produit de deux matrices dadjacence de mme ordre n de la faonsuivante : si A = (ai,j) et B = (bi,j), alors AB = (ci,j) avec

ci,j =nk=1

ai,kbk,j

On note A2 le produit AA et Ap le produit AA A p fois

.

Proposition 4.6.1. Soit G un graphe orient (respectivement non orient) dordre n et soitM sa matricedadjacence. Alors pour tout entier k > 0 et pour tout couple (i, j) {1, 2, . . . , n},

Llment Mk(i, j) est le nombre de chemins (respectivement chanes) de longueur k de i vers j. Llment Mk(i, i) est le nombre de circuits (respectivement cycles) de longueur k partir de i.

4.7 Exercices

Exercice 4.1 Reprendre lexemple 4.2.1 et donner pour chaque sommet x les quantits +(x), (x),d+(x), d(x) et d(x).Exercice 4.2 Dessiner le graphe (non orient) qui admet pour matrice

M =

0 1 1 01 0 1 01 1 0 10 0 1 0

1. Donner la reprsentation par liste dadjacence du graphe.2. Donnez les degrs de chaque sommet. Vrifier le lemme des poignes de main.3. Calculer M2, puis M3 et M +M2.4. Combien y a-t-il de chanes de longueur 2 menant 1 2 ? 2 4 ? 3 4 ?

36 Thorie des graphes : introduction

5. Combien y a-t-il de chanes de longueur 2 menant 1 2 ? 2 4 ? 3 4 ?6. Combien y a-t-il de chanes de longueur 3 menant 2 3 ? 2 1 ?7. Combien y a-t-il de cycles de longueur 3 ayant 3 comme sommet de dpart ? 4 comme sommet de

dpart ?8. Donner un exemple de cycle de longueur 4. Est-il lmentaire ?9. Donner tous les cycles de longueur 3 (y en a-t-il 1, 2, 3 ou 6 ?).

Exercice 4.3 tudions la modlisation dune station de ski de fond. Afin de simplifier, on supposera quetoutes les pistes ont la mme difficult et on sintressera donc seulement aux randonnes possibles.

La (petite) station comporte 6 lieux diffrents, quon numrotera de 1 6. Toutes les pistes sont double sens. Le tableau suivant indique les pistes existant :

lieu vers lieu1 2,42 1,3,53 2,54 1,5,65 2,3,4,5,66 4,5

1. Comment peut-on modliser les diffrentes pistes de ski ? Faites-le.2. Comment dterminer, par le calcul, le nombre de parcours diffrents empruntant deux pistes suc-

cessives au dpart du lieu 5. Calculer ce nombre.

Exercice 4.4Mr et Mme X assistent une runion. Il y a trois autres couples dans lassistance et plusieurspoignes de mains sont changes. Personne ne serre sa propre main et les poux ne se serrent pas lamain. Deux personnes quelconques de lassemble se serrent la main au plus une fois. Mr X constate queles 7 autres personnes ont chang des poignes de mains en nombres tous distincts. Combien de poignesde mains Mr et Mme X ont-ils chang avec les autres membres de la runion ?

Exercice 4.5 Une chvre, un chou et un loup se trouvent sur la rive dun fleuve ; un passeur souhaite lestransporter sur lautre rive mais, sa barque tant trop petite, il ne peut transporter quun seul dentreeux la fois. Comment doit-il procder afin de ne jamais laisser ensemble et sans surveillance le loup etla chvre, ainsi que la chvre et le chou ? (on demande un raisonnement utilisant la thorie des graphes)

4.7. Exercices 37

Un arbre est un type de graphe particulier

38 Thorie des graphes : introduction

Partie 5

Arithmtique

Larithmtique est la partie des mathmatiques qui tudie les nombres entiers.

5.1 Divisibilit

5.1.1 PGCD et PPCM

Dfinition 5.1.1. Soient a et b des entiers relatifs. On dit que a divise b, et on note a|b, si k Z; b = k.a

On dit aussi que b est un multiple de a. Ainsi, par exemple, 3 divise 12 mais 5 ne divise pas 7, cequon pourra noter 5 - 7.

Regardons comment se comporte la divisibilit avec les oprations usuelles :Proposition 5.1.1. Si a|b et a|c, alors

u, v Z, a|(bu+ cv)

Preuve. En effet, comme a|b et a|c, alors il existe des entiers k et l tels que b = a.k et c = a.l. On a alors u, v Z, bu+ cv = a.k.u+ a.l.v = a. (ku+ lv)

Z

et donc a divise bu+ cv.

On peut dsormais dfinir les notions de PGCD et de PPCM.Dfinition 5.1.2. Soient a et b des entiers relatifs.

On note a b ou PGCD(a, b) le plus grand entier naturel qui divise la fois a et b. On note a b ou PPCM(a, b) le plus petit entier naturel multiple commun de a et b.

5.1.2 Division euclidienne

Thorme 5.1.1. Soit (a, b) Z N, alors il existe un unique couple (q, r) dans Z N tel quea = bq + r

avec 0 r < b.q est appel le quotient et r les reste de la division euclidienne de a par b.

39

40 Arithmtique

Exemple 5.1.1. La division euclidienne de 17 par 4 est : 17 = 4 4 + 1.La division euclidienne de 17 par 4 est : 17 = 4 (5) + 3.

5.1.3 Algorithme dEuclide

Soient deux entiers naturels a et b dont on cherche le pgcd. Lalgorithme dEuclide 1 consiste effectuerdes divisions euclidiennes successives de la faon suivante :

a = bq1 + r1 avec 0 r1 < bb = r1q2 + r2 avec 0 r2 < r1r1 = r2q3 + r3 avec 0 r3 < r2...

...rn2 = rn1qn + rn avec 0 rn < rn1rn1 = rnqn+1 + 0

On remarque que les restes successifs forment une suite dentiers naturels strictement dcroissante, ce quiimplique quon tombe ncessairement sur un reste nul au bout dun certain nombre de divisions.

Rsultat : Le pgcd de a et b est alors le dernier reste non nul, cest--dire rn avec les notationsci-dessus.

Preuve. Notons d le pgcd de a et b.(1) d divise rn

On sait que d divise a et b, il divise donc, daprs la proposition 5.1.1, la quantit a bq1 = r1.Ceci signifie que d divise b et r1 donc de la mme faon, on sait que d doit diviser b r1q2 = r2. En

itrant ce raisonnement sur les divisions successives, on obtient finalement que d divise rn, ce qui signifieen particulier que d rn.

(2) rn divise a et bLa dernire division nous dit que rn1 = rnqn+1, donc rn divise rn1.

Dans la division prcdente, comme rn divise rn et rn1, on en dduit que rn divise rn2.En itrant ce raisonnement, on en dduit tout dabord que rn divise b puis que rn divise a, ce qui

prouve que rn est un diviseur commun de a et b.(3) conclusion

Nous avons montr au point (2) que rn est un diviseur commun de a et b. Or, on sait par la dfinition dupgcd que d est le plus grand diviseur commun de a et b, ce qui signifie donc que d est suprieur ou gal rn. Le point (1) donnant lingalit inverse, on en dduit lgalit d = rn.

Exemple 5.1.2. Calculons le pgcd de 17 et 9 en utilisant lalgorithme dEuclide :

17 = 9 1 + 89 = 8 1 + 18 = 1 8 + 0

Donc 17 9 = 1.

Pour calculer le ppcm, on pourra calculer le pgcd et utiliser la proposition suivante, qui fait le lienentre ces deux quantits :

Proposition 5.1.2. Soient a et b deux entiers naturels. Alors

(a b) (a b) = a b1. Euclide, voir chapitre 6 page 53

5.2. Nombres premiers 41

5.1.4 Identit de Bachet-Bzout

Thorme 5.1.2. Soient a et b deux entiers non nuls. Alors

u, v Z, au+ bv = a bExemple 5.1.3. Nous avons calcul tout lheure le pgcd de 17 et 9, qui vaut 1. On a bien lcriture

17 (1) + 9 2 = 1qui est une identit de Bachet-Bzout 2 avec u = 1 et v = 2.

La question qui se pose est videmment comment trouver u et v ? Cest encore une fois lalgorithmedEuclide qui va nous y aider. Lide est de remonter les divisions obetnues afin dexprimer le pgcd enfonction de a et b. On dit alors quon applique lalgorithme dEuclide tendu.

Sil y a beaucoup de divisions, il convient de procder avec mthode afin de minimiser les risquesderreur. Dans lexemple ci-dessous, je vous propose une faon de procder qui a le mrite de ne pasmanipuler les nombres qui apparaissent dans les divisions successives.

Exemple 5.1.4. Reprenons lexemple de 17 et 9. On applique lalgorithme dEuclide en donnant un nomaux restes successifs, puis on crit, ct de chaque division et en partant du haut, lexpression du resteen fonction de a et b :

a17 =

b9 1 +

c8 c = a b

b9 =

c8 1 +

d1 d = b c = b (a b) = 2b a

On sarrte ds quon atteint la ligne qui contient le pgcd, on obtient ainsi :

1 = d = a+ 2b = (17) + 2 9qui est une galit de Bachet-Bzout pour 17 et 9.

5.2 Nombres premiers

Dfinition 5.2.1. Un nombre premier est un entier naturel strictement suprieur 1 qui nest divisibleque par 1 et par lui-mme.

Exemple 5.2.1. Les premiers nombres premiers sont 2, 3, 5, 7, 11, etc.

Dfinition 5.2.2. On dit que deux entiers a et b sont premiers entre eux si a b = 1, autrement dit,sils nont que 1 comme diviseur commun.

Attention ne pas confondre ces deux notions : deux nombres peuvent tre premiers entre eux sansquaucun des deux soit premier, par exemple 9 et 16.

Les nombres premiers jouent un grand rle parmi les nombres entiers. Beaucoup de questions ou-vertes sont lies ces nombres et ils interviennent dans de nombreuses applications concrtes comme lacryptographie (voir chapitre 5.5).

2. Claude-Gaspard Bachet de Mziriac, voir chapitre 6 page 54

42 Arithmtique

Thorme 5.2.1. Lensemble P des nombres premiers est infini.

Preuve. La dmonstration que nous allons voir, qui est celle dEuclide, se fait par labsurde. Supposonsque lensemble P est fini et notons P = {p1, . . . , pn} ses lments tris par ordre croissant. Nous allonsmontrer quon peut alors en construire un nouveau qui nest pas dans P. Considrons lentier

q = p1p2 . . . pn + 1

Il y a alors deux possibilits : soit q est premier, mais alors, comme q est clairement suprieur pn, q est un nombre premier quinest pas dans P, ce qui est absurde.

sinon, q nest pas premier mais alors il possde un diviseur premier p. On remarque que p ne peuttre aucun des pi car sinon, on aurait p|(p1 . . . pn et p|q et donc p|1 ce qui est impossible. p est doncun nombre premier qui nest pas dans P, ce qui est absurde.

Lensemble P des nombres premiers est donc ncessairement infini.

Thorme 5.2.2 (Thorme de Gauss 3). Soient a, b et c des entiers.Si a|bc et si a b = 1, alors a|c.

Preuve. Commenons par expliciter les deux conditions :1. a|bc k Z; bc = ak2. a b = 1 u, v Z; au+ bv = 1 (identit de Bachet-Bzout)

En multipliqnt le 2) par c, il vient :acu+ bcv = c

acu+ akv = c a(cu+ kv) = c a|c

Malgr les espoirs fous des tudiants, on ne peut pas remplacer lhypothse a b = 1 par a - b, pour vousen convaincre, essayez avec a = 4, b = 6 et c = 10.

Le thorme suivant est un thorme fondamental pour les nombres premiers. Il nous dit que lesnombres premiers sont en quelque sorte les briques qui permettent de construire nimporte quel nombreentier.

Thorme 5.2.3 (Thorme de dcomposition en facteurs premiers). Tout entier n 2 admet unedcomposition unique en facteurs premiers

n = p11 p22 pkkavec p1, p2, . . . , pk P premiers distincts et 1, 2, . . . , k entiers strictement positifs.Exemple 5.2.2. La dcomposition de 198 en facteurs premiers est

198 = 2 32 113. Johann Carl Friedrich Gauss, voir chapitre 6 page 54

5.3. quation diophantienne ax+ by = c 43

On lobtient par exemple en cherchant ses diviseurs premiers du plus petit au plus grand et en effectuantles divisions :

198 299 333 311 111

Cette criture permet de trouver facilement le pgcd et le ppcm de deux entiers :1. on crit la dcomposition en facteurs premiers de a et b.

Par exemple, pour a = 198 et b = 924 :

a = 2 32 11b = 22 3 7 11

2. en utilisant lgalit p0 = 1, on crit a et b avec les mmes nombres premiers :

a = p11 p22 . . . p

kk

b = p11 p22 . . . p

kk

Sur lexemple, on obtient :a = 2 32 70 11b = 22 3 7 11

3. on a alors :a b = pmin(1,1)1 pmin(2,2)2 . . . pmin(k,k)k

eta b = pmax(1,1)1 pmax(2,2)2 . . . pmax(k,k)k

Sur lexemple, on obtient :a b = 2 3 11 = 66a b = 22 32 7 11 = 2772

5.3 quation diophantienne ax+ by = c

On appelle quations diophantiennes 4 les quations dont on cherche les solutions dans Z. On ntudieraici quun cas particulirement simple, les quations du type :

ax+ by = c

avec a, b, c Z.Thorme 5.3.1. Lquation ax+ by = c admet des solutions entires si et seulement si (a b)|c.

Preuve. Nous allons donner ici une preuve constructive, cest--dire quon obtiendra non seulement lapreuve de lexistence dune solution mais aussi le moyen de dterminer lensemble de toutes les solutionsde lquation.

Commenons par montrer la condition ncessaire : si x et y sont des solutions dans Z de lquationax+ by = c, ceci signifie que tout entier qui divise a et b divise ncessairement ax+ by, cest--dire c. Enparticulier, le pgcd de a et b, qui divise la fois a et b, est un diviseur de c.

Le point plus dlicat est la rciproque : si le pgcd d = a b de a et b divise c, nous devons prouverque lquation admet des solutions et donner explicitement lensemble de solutions.

4. Diophante dAlexandrie, voir chapitre 6 page 54

44 Arithmtique

Commenons par diviser toute lquation par d. Ceci est possible puisquon se place sous lhypothseque d divise c. En notant a1 = ad , b1 =

bd et c1 =

cd , on a :

(x, y) solution de ax+ by = c (x, y) solution de a1x+ b1y = c1

avec dsormais a1 b1 = 1 puisquon a divis par le pgcd de a et b.Lide ensuite est dutiliser lidentit de Bachet-Bzout qui nous donne facilement une solution de

cette quation. En effet, on sait quil existe u et v dans Z tels que a1u + b1v = 1, ce qui, en multipliantpar c1, nous dit que a1c1u+ b1c1v = c1. On a donc trouv une solution de lquation : le couple (x0, y0)dfini par x0 = c1u et y0 = c1v.

Afin de dterminer les autres solutions, nous allons utiliser la solution (x0, y0). En effet, une autresolution (x, y) vrifie :

a1x+ b1y = c1 = a1x0 + b1y0

ce qui est quivalent a1(x x0) = b1(y y0) ()

On a alors a1|(b1(y y0)), or on sait que a1 b1 = 1, donc daprs le thorme de Gauss, a1|(y y0),cest--dire :

k Z; y y0 = a1k y = y0 + a1kEn rinjectant cette valeur de y dans (), il vient :

a1(x x0) = b1a1k

soit, en simplifiant par a1 (qui est bien non nul),

x = x0 b1k

On en dduit donc que toute autre solution scrit ncessairement{x = x0 b1ky = y0 + a1k

avec k Z

Rciproquement, on vrifie que (x, y) dfini comme ci-dessus est solution de a1x+ b1y = c1 :

a1x+ b1y = a1(x0 b1k) + b1(y0 + a1k) = a1x0 + b1y0 = c1

Donc lensemble S des solutions de lquation ax+ by = c est

S = {(x0 b1k, y0 + a1k) | k Z}

o (x0, y0) est une solution particulire de lquation.

La mthode de rsolution de telles quations se fait donc en 3 tapes :(1) tout diviser par le pgcd de a et b

(2) trouver une solution particulire (par exemple en utilisant lalgorithme dEuclide tendu)(3) trouver les autres solutions en refaisant le raisonnement de la preuve.

5.4. Congruences 45

Exemple 5.3.1. On souhaite rsoudre dans Z lquation (E) 198x 924y = 330.

(1) Le pgcd de 198 et 924 est 66 et 66|330, donc on sait dj que lquation aura des solutions et onpeut la simplifier en divisant tout par 66 :

(E) 3x 14y = 5 (E)

(2) On cherche une solution particulire de (E). On crit dabord une identit de Bachet-Bzout pour3 et 14 (pas besoin de lalgorithme dEuclide ici, on trouve u et v au "feeling") :

3 5 14 1 = 1puis on multiplie par 5 pour obtenir une solution particulire de (E) :

3 25 14 5 = 5donc x0 = 25, y0 = 5 est une solution particulire de (E).

(3) Soit (x, y) une autre solution de (E). On a alors

3x 14y = 5 = 3 25 14 5ce qui est quivalent

3(x 25) = 14(y 5)Donc 3 divise 14(y 5), or 3 et 14 sont premiers entre eux, donc le thorme de Gauss nous dit quencessairement 3|(y 5), cest--dire

k Z; y 5 = 3k y = 5 + 3kce qui donne alors pour x :

3(x 25) = 14 (3k) x = 25 + 14kOn vrifie que x = 25 + 14k et y = 5 + 3k sont bien solutions de (E) :

3(25 + 14k) 14(5 + 3k) = 3 25 14 5 = 5Lensemble des solutions de (E) est donc

S = {(25 + 14k, 5 + 3k) | k Z}

5.4 Congruences

5.4.1 Modulo

Dfinition 5.4.1. Soient a, b et n trois entiers (n > 0). On dit que a et b sont congrus modulo n, et onnote a b mod n ou a b [n], si et seulement si a et b ont le mme reste dans la division euclidiennepar n.

a b mod n n|(a b) k Z; a = b+ knExemple 5.4.1. 29 16 3 10 mod 13

Proposition 5.4.1. Soient a, b, c, d Z et n N tels que{a b mod nc d mod n

Alors on a1. a+ c b+ d mod n2. a.c b.d mod n

46 Arithmtique

5.4.2 Z/nZ [o lon prend un peu daltitude]

Proposition 5.4.2. Soit n N, la relation de congruence modulo n est une relation dquivalence surZ.

On note a la classe dquivalence dun entier a et Z/nZ lensemble des classes dquivalences.

On a Z/nZ = {0, 1, . . . , n 1}.

Exemple 5.4.2. Z/5Z = {0, 1, 2, 3, 4}0 = {a Z | 5|a} = {0, 5, 10, 15, . . . ,5, 10, . . .}1 = {a Z | 5|(a 1)} = {1, 6, 11, 16, . . . ,4,9, . . .}2 = {a Z | 5|(a 2)} = {2, 7, 12, 17, . . . ,3,8, . . .}3 = {a Z | 5|(a 3)} = {3, 8, 13, 18, . . . ,2,7, . . .}4 = {a Z | 5|(a 4)} = {4, 9, 14, 19, . . . ,1,6, . . .}

Il faut savoir faire le lien entre lcriture avec les congruences modulo n et lcriture dans Z/nZ :

a b mod n a = b dans Z/nZ

Oprations dans Z/nZ

Soient x et y dans Z/nZ, on dfinit la somme et le produit par :

x+ y = x+ y

x.y = x.y

La proposition 5.4.1 nous assure que ces oprations sont bien dfinies, i.e. indpendantes du choix dureprsentant de chaque classe.

La division nexiste pas dans Z/nZ. Nanmoins, le concept dinverse va nous permettre de nous enpasser.

Inverse dans Z/nZ

Dfinition 5.4.2. On dit quun lment a Z/nZ est inversible si b Z/nZ; a.b = 1

On note alors cet lment a1 et on lappelle linverse de a.

5.4. Congruences 47

La proposition suivante donne un critre dinversibilit et nous donne mme un moyen dobtenirlinverse dun lment.

Proposition 5.4.3. Soit a Z/nZ, alorsa est inversible dans Z/nZ a n = 1

preuve. Si a est inversible, alors il existe un b vrifiant a.b = 1, ce qui peut encore scrire ab = 1 + knavec k Z. On en dduit que tout diviseur commun de a et n est un diviseur de 1, et donc le pgcd de aet n est 1.

Rciproquement, si a n = 1, alors on peut crire une identit de Bachet-Bzout : u, v Z; au+ nv = 1

En passant dans Z/nZ, on obtient, en remarquant que n = 0, a.u = 1, ce qui signifie que a est inversibleet que son inverse est le u obtenu dans lgalit de Bachet-Bzout.

Exemple 5.4.3. Dans Z/4Z, 1 est inversible (1.1 = 1 donc 11 = 1), 3 est inversible (3.3 = 9 = 1 donc31 = 3). En revanche, 2 et 4 ne le sont pas.

Corollaire 5.4.1. Soit p un nombre premier, alors tout lment de Z/pZ sauf 0 est inversible.

Corollaire 5.4.2. Soit p un nombre premier, alors dans Z/pZ, on a

x.y = 0 x = 0 ou y = 0

Ce rsultat nest plus vrai si p nest pas premier ! Par exemple, 2.2 = 0 dans Z/4Z.

5.4.3 Equations aux congruences

On sintresse ici aux quations dans Z/nZ. Traitons le cas dune quation une inconnue, du typea.x+b = c. La premire tape consiste faire passer le b de lautre ct, comme on le ferait pour la mmequation dans R, ce qui consiste en ralit ajouter b des deux cts de lgalit. On obtient alors

a.x = c b

Arriv ce point, il faut se retenir de diviser par a et se rappeler que la division nexiste pas dansZ/nZ ! Cependant, quand a est inversible, on peut multiplier par a1 ce qui revient se dbarrasser duterme devant le x.

Si a est inversible On multiplie donc par linverse de a et on obtient une unique solution dans Z/nZ :

x = a1(c b)

Si a nest pas inversible Il y a alors deux cas possibles : (1) le pgcd de a et n ne divise pas c b : lquation na alors pas de solution (2) le pgcd de a et n divise c b : on crit lquation dans Z laide des congruences et on divisetout par a n

ax

a n c ba n mod

n

a net on se retrouve alors dans le cas (1).

48 Arithmtique

5.5 Cryptographie

5.5.1 Introduction la cryptographie

La cryptographie est la science qui permet de faire transiter des informations en secret.

Alice BobPlus prcisment, Alice souhaite envoyer un message Bob mais veut sassurer que seul Bob sera capablede le dchiffrer, i.e. quune personne interceptant le message ne pourra le comprendre. Il y deux grandescatgories de systmes permettant de crypter une information : les systmes cl prive (Bob et Alice separtagent une cl permettant de dcoder le message) comme DES ou AES, et les systmes cl publiqueque nous allons tudier par le biais de RSA.

5.5.2 Fonction dEuler

Dfinition 5.5.1. Soit m 1 un entier, on dfinit(m) = ]{1 n m 1 | n m = 1}

Cette application est appele fonction dEuler.

La fonction dEuler (m), daprs la caractrisation des inversibles vue dans la proposition 5.4.3,compte le nombre dlments inversibles dans Z/mZ. Le thorme suivant indique comment la calculeren sappuyant sur la dcomposant en facteurs premiers.

Thorme 5.5.1 (calcul de ).

Si p est premier, alors (p) = p 1 et 1, (p) = p p1. Si a b = 1, alors (ab) = (a)(b).

Exemple 5.5.1. Pour calculer (18), on dcompose 18 en produit de facteurs premiers puis on utiliseles proprits prcdentes :

(18) = (2 32) = (2) (32) = (2 1) (32 3) = 6

En plus de donner des informations sur les inversibles dans Z/mZ, la fonction dEuler vrifie uneproprit qui nous permettra de calculer rapidement des grandes puissances dans Z/mZ.

Thorme 5.5.2 (Thorme dEuler). Si a m = 1, alorsa(m) 1 mod m

Remarque. Ce thorme gnralise le rsultat suivant connu sous le nom de petit thorme de Fermat :

p premier ap a mod p

Application au calcul de puissances modulo m

On souhaite connatre le reste de la division de 7602 par 18. Il est videmment hors de question deposer la division. . . En revanche, le thorme dEuler nous dit que, tant donn que 7 18 = 1, on a

7(18) 1 mod 18cest--dire

76 1 mod 18

5.5. Cryptographie 49

On peut alors crire7602 (76)10072 mod 18

72 mod 18 49 mod 18 1 mod 18

5.5.3 Thorme RSA et cryptographie

Du nom de Rivest, Shamir et Adleman, le thorme RSA est la base dune mthode de cryptographie cl publique.

Thorme 5.5.3 (Thorme RSA, 1977). Soient p et q deux nombres premiers et soit n = pq. Soit a unentier tel que 0 a n, alors

k N, ak(n)+1 a mod n

Le principe de fonctionnement du systme de cryptographie RSA est le suivant : chaque personnedisposera dune cl prive et dune cl publique construites en suivant les tapes suivantes.

1. choisir deux nombres premiers de grande taille 5, quon notera p et q2. calculer n = p q3. calculer (n) = (p 1)(q 1)4. choisir un entier e premier avec (n)5. calculer d linverse de e dans Z/(n)Z (i.e. ed 1 mod (n))6. (n, e) sera la cl publique et (n, d) sera la cl prive

Si Alice souhaite envoyer un message Bob, elle commence par associer un nombre chaque lettre dumessage : A=01, B=02, ... puis elle crypte chaque nombre obtenu en effectuant le calcul :

m me mod n

o (n, e) est la cl publique de Bob.

Bob reoit donc des nombres quil dcode en faisant le calcul :

m md mod n

On voit quil a besoin du couple (n, d) quil est le seul connatre. Le thorme RSA nous assure quilretrouvera bien le message de dpart m car il calcule md mod n, cest--dire med mod n et ed est congru 1 modulo (n).

Avec un peu dastuce, on peut assurer Bob que cest bien Alice qui lui a envoy le message, ce qui revient garantir lauthentification de lexpditeur. Avez-vous une ide de la mthode employer ?

5. ce jour, il est conseill de les choisir avec plus de 200 chiffres !

50 Arithmtique

1 nest pas premier ! mais 2 et 3 OUI !

Partie 6

Mais qui sont ces gens ?

Ce chapitre a t rempli grce lexcellent site internet http:///www.bibmath.net. Il vous permettrade mieux situer les mathmaticiens que nous rencontrons travers le cours et de confirmer votre intuitionque ces gens-l ne sont pas vraiment comme tout le monde. . .

Euler, Leonhard Paul (17071783) N Ble le 15 avril 1707, Leonhard Euler tudia les mathma-tiques sur les conseils de Johann Bernoulli, qui tait ami avec son pre. Il sinstalla Saint-Petersbourg,auprs de Pierre le Grand, puis Berlin sous le rgne de Frdric II, o a chaque fois il rencontra unenvironnement scientifique exceptionnel. Son oeuvre est considrable. Euler intervint dans les trois do-maines fondamentaux de la science de son poque : lastronomie (orbites plantaires, trajectoires descomtes), les sciences physiques (champs magntiques, hydrodynamique, optique, nature ondulatoire dela lumire,...), les mathmatiques, o il met au premier plan le concept de fonction. On lui doit aussi latrs jolie relation entre les nombres de sommets, dartes et de faces dun polydre convexe (ex : le cube,le ttradre,...).

La sant dEuler tait assez fragile. Il perdit son oeil droit en 1735, puis son oeil gauche en 1771 enraison dune cataracte. Il fut donc pendant 12 ans totalement aveugle. Cela obligeait ce mathmaticien trsprolixe, qui publia 886 ouvrages, le tout en 80 volumes, faire appel des personnes de son entourage qui il dictait ses mmoires. Il dcde le 18 septembre 1783 Saint-Petersbourg dune hmorragie crbrale.

Cantor, Georg (18451918) Georg Cantor est n le 3 mars 1845 St Petersbourg. Son pre est commer-ant prospre, sa mre est issue dune famille de musiciens ; tous les deux sont trs cultivs, et donnent leur fils une ducation srieuse, religieuse, et berce par les arts. En 1866, la famille sinstalle en Allemagne,o elle espre trouver un climat plus favorable la sant du pre.

Georg Cantor se rvle tre un tudiant brillant, notamment dans les matires manuelles. Malgr lesinjonctions de son pre, qui rve den faire un ingnieur, il part en 1862 Berlin tudier les mathmatiques,o ses matres sont Weierstrass et Kronecker. Il soutient son doctorat en 1867 (sur la thorie des nombres),mais nobtient pas immdiatement un poste complet. En 1874, il se marie (il aura 6 enfants).

Les premires recherches post-doctorales de Cantor sont consacres la dcomposition des fonctionsen sommes de sries trigonomtriques (les clbres sries de Fourier) et particulirement lunicit decette dcomposition. Afin de rsoudre compltement ce difficile problme, il est amen introduire et tudier des ensembles dits exceptionnels. Cela le conduit dfinir en 1872 trs prcisment ce quest unnombre rel, comme limite dune suite de nombres rationnels ; paralllement, son ami Dedekind donnela mme anne une autre dfinition de la droite des rels, partir des coupures. Cantor et Dedekindconstatent cette occasion quil y a beaucoup plus de rels que de rationnels, mais il ny a pas jusque-lde dfinition mathmatique ce "beaucoup plus".

En 1874, dans le prestigieux Journal de Crelle, Cantor donne une dfinition du nombre dlments

51

52 Mais qui sont ces gens ?

dun ensemble infini qui prolonge naturellement celle du cardinal dun ensemble fini. Il en dcoule, jus-quen 1897, une succession de dcouvertes tranges : il y autant dentiers pairs que dentiers tout court,autant de points sur un segment que dans un carr, beaucoup plus de nombres transcendants que denombres rationnels. Cette hirarchie dans les ensembles infinis conduit progressivement Cantor dfinirdes nouveaux nombres, les ordinaux transfinis, et dfinir une arithmtique sur ces nombres.

Les dcouvertes de Cantor soulvent la contestation des mathmaticiens constructivistes de lpoque,au premier rang desquels on trouve Poincar et surtout Kronecker, lequel nhsitera pas attaquerpersonnellement Cantor, bloquant ses publications dans le Journal de Crelle, et allant mme jusqu tenterde bloquer sa carrire. Malgr cela, Cantor obtient un poste de professeur temps plein luniversit deHalle en 1879.

Vient lanne 1884, et la premire crise de dpression de Cantor. Celui-ci perd alors la force daffronterses opposants, et na plus la confiance dentreprendre de nouvelles recherches. Il sintresse alors lhis-toire, la littrature anglaise, intervenant notamment dans une crise contemporaine autour des pices deShakespeare. En 1899, il obtient un poste administratif consacr des tches routinires qui lui permetde renoncer son enseignement. Peu peu, ses crises se font de plus en plus frquentes et longues, et ilpasse une large partie de son temps soigner sa schizophrnie dans des maisons de repos. Il dcde le 6juin 1918 Halle.

Les travaux de Cantor ont eu beaucoup dinfluence au XX s. On citera dabord, en 1903, un paradoxesoulev par Russell dans la thorie nave des ensembles : si A est lensemble de tous les ensembles quine sont pas lments deux-mmes, A est-il contenu dans A ? Les logiciens surmonteront cette difficultconceptuelle, sans rien changer des conclusions de Cantor. Citons aussi le problme de lhypothse ducontinu. Un des derniers axes de recherche de Cantor tait destimer le nombre dlments de la droiterelle. Plus prcisment, Cantor souhaitait prouver labsence de tout ensemble dont le cardinal soit stricte-ment compris entre le cardinal des entiers et celui des rels. Cest ce quon appelle lhypothse du continu.Tous les travaux de Cantor et de ses successeurs pour confirmer ou infirmer lhypothse du continu furentvains, et pour cause : en 1963, le logicien amricain Cohen prouva que, dans une thorie standard desensembles, lhypothse du continu est indcidable. On peut trs bien supposer quelle est vraie ou quelleest fausse sans obtenir de contradiction dans la thorie.

Boole, George (18151864) Issu dune famille pauvre, George Boole na pas les moyens financiersdaller luniversit. Ses capacits intellectuelles sont cependant remarquables ; seul (ou presque), il aappris le latin, lallemand, le franais et litalien. Oblig de travailler pour soutenir sa famille, il devientenseignant 16 ans.

Quatre ans plus tard, il fonde et dirige sa propre cole. Cest ce moment que le jeune autodidactese plonge dans ltude des mathmatiques auxquelles son pre lavait initi ds lenfance. Bnficiant desmoyens de lInstitut de mcanique de sa ville, il se confronte aux uvres dIsaac Newton, Pierre-SimonLaplace et Joseph-Louis Lagrange. Mais trs vite, il commence ses propres recherches. En 1839, il publieainsi sa premire tude dans le Cambridge Mathematical Journal. Cette publication et lappui quil obtientdu cercle des algbristes de Cambridge lui permettent de simposer petit petit comme une personnalitimportante du monde des mathmatiques. En 1844, aprs la publication dun mmoire danalyse dans lesPhilosophical Transactions, la Royal Society lui dcerne une mdaille.

Il pouse le 11 septembre 1855 Mary Everest, nice de sir George Everest, le responsable de la missioncartographique qui baptisa le mont Everest.

Cest le dbut dune srie de travaux posant les bases de ce quon nommera plus tard lalgbre deBoole. En 1847 sort Mathematical Analysis of Logic, puis An Investigation Into the Laws of Thought,on Which are Founded the Mathematical Theories of Logic and Probabilities en 1854. Boole y dveloppeune nouvelle forme de logique, la fois symbolique et mathmatique. Le but : traduire des ides et desconcepts en quations, leur appliquer certaines lois et retraduire le rsultat en termes logiques. Pour cela,il cre une algbre binaire nacceptant que deux valeurs numriques : 0 et 1. Cette algbre est dfiniepar la donne dun ensemble E (non vide) muni de deux lois de composition interne (le ET et le OU)satisfaisant un certain nombre de proprits (commutativit, distributivit...). Les travaux de Boole,

53

sils sont thoriques, nen trouveront pas moins des applications primordiales dans des domaines aussidivers que les systmes informatiques, la thorie des probabilits, les circuits lectriques et tlphoniques,etc. grce des scientifiques comme Peirce, Frege, Bertrand Russell, Alan Turing et Claude Shannon.

En 1849, George Boole se voit proposer une chaire de professeur des mathmatiques au Queens Collegede Cork, en Irlande. Et en 1857, il est nomm membre de la Royal Society. Il sintresse ensuite auxquations diffrentielles travers deux traits qui auront une influence certaine : Treatise on DifferentialEquations (1859) et Treatise on the Calculus of Finite Differences (1860). George Boole meurt dunepneumonie le 8 dcembre 1864. Il avait pris froid aprs stre rendu au Collge. Croyant au principedanalogie, Mary lavait alit et asperg deau pour le gurir.

Hasse, Helmut (18981979) Helmut Hasse est un mathmaticien allemand n le 25 aot 1898 Kasselet mort le 26 dcembre 1979 Ahrensburg.

Il fut un des plus grands algbristes et thoricien des nombres de son temps. En 1925 il devint directeurde linstitut Mathmatique de Halle puis en 1934 il travailla Gttingen. Sa carrire fut contrarie parlpisode nazi car il tait suspect davoir des ascendants juifs. Aprs la guerre, il travailla Berlin puis Hambourg.

Il laissa la postrit le diagramme de Hasse qui est un arbre logique de facteur et dfinissant unerelation dordre, ainsi que le thorme de la norme de Hasse nous dit que si L/K est une extension cycliquedes corps de nombres, alors, si un lment diffrent de zro de K est une norme locale partout, alors ilest une norme globale.

Euclide (-325 -265) Si lon devait se contenter de rdiger une notice biographique de la vie dEuclide,alors elle serait trs courte : on ne sait rien, ou presque, de celui que lon peut considrer comme leplus grand enseignant de mathmatiques de lhistoire. Tout juste pense-t-on quil tudia lcole dessuccesseurs de Platon Athnes, avant de stablir Alexandrie, sous linvitation de Ptolme I. Maiscomme ces suppositions reposent sur des crits de Proclus qui datent de 9 sicles aprs Euclide, on conoitquelles sont peu fiables !

Ce que lon connait bien dEuclide, ce sont les ouvrages qui nous sont parvenus signs de son nom,parmi lesquels Donnes, et surtout les 13 volumes des lments. Du reste, on ne sait pas trop quel estle rapport exact entre Euclide et les connaissances quil expose. Il semble bien quaucun des rsultatsdes Elments ne soit d Euclide, et que son oeuvre consiste en une remise plat de diffrentes notionsexhibes par des mathmaticiens divers. Au juste, personne ne peut affirmer avec certitude si Euclidetait un historien des sciences, chef dune cole, et sil crivit ses ouvrages pour son enseignement. Oubien sil confiait leur rdaction ses lves, qui auraient pu continuer publier sous le nom dEuclidemme aprs sa mort. On peut aller jusqu supposer quEuclide, la manire dun Nicolas Bourbaki, taitle prte-nom dun mathmaticien polycphal : plusieurs mathmaticiens crivant un mme trait sous unpseudonyme.

Attardons-nous alors quelque peu sur les lments, qui restent une oeuvre fondamentale de nos jours,car lessentiel du cours de mathmatiques du collge en est directement issu. Les 4 premiers tomes sontconsacrs la gomtrie plane. Euclide initie alors la mthode axiomatique en construisant la gomtriedans le plan laide daxiomes et de postulats. Plus clairement, Euclide dmontre les thormes degomtrie plane partir de propositions quil pose comme vraies (du type : deux quantits gales unemme troisime sont gale entre elles). Dans un langage mathmatique moderne, ces demandes seraientdes dfinitions dans la thorie que lon cherche construire.

Grce ce point de vue, Euclide fait preuve dune grande rigueur, trs inhabituelle pour son temps.Un des postulats formul par Euclide, le 5ime postulat, dit aussi postulat des parallles, a longtempspos problme. Il affirme que, par un point extrieur une droite, on peut mener une parallle cettedroite, et une seule. Jusquau XIX s., certains ont cru que ce postulat tait en trop, ie que ctait unthorme que lon pouvait dduire des autres axiomes et postulats. Mais les travaux de Gauss, Riemannet Lobachevsky ont alors montr que lon pouvait construire dautres types de gomtrie, o ce postulat

54 Mais qui sont ces gens ?

tait remplac par un autre : dans la gomtrie hyperbolique, par un point extrieur une droite, il passeune infinit de droites parallles cette droite.

Bachet de Mziriac, Claude-Gaspard (15811638) Claude Gaspard Bachet de Mziriac est n le 9octobre 1581 Bourg-en-Bresse. Il est issu dune vieille famille noble (son grand-pre tait conseillerdHenri II, son pre juriste auprs du duc de Savoie). Orphelin 6 ans, il est duqu chez les Jsuites enItalie o il est rput pour tre grand lecteur. De retour en France, il rsidera quasiment en permanencetout prs de Bourg en Bresse. Sa fortune assure par sa famille, il peut se consacrer ltude des lettreset des sciences. En 1621, il se marie et aura 7 enfants.

Bachet de Mziriac est rput pour tre un des plus grands humanistes du XVII s. Avec son frre,il est lauteur de (mdiocres) pomes, de chants religieux. Parfait connaisseur de la langue grecque, iltraduit de nombreux ouvrages classiques. Pour ce qui nous concerne, il est lauteur en 1612 dun livreintitul Problmes plaisants et dlectables qui se font par les nombres, qui est un recueil de rcrationsmathmatiques parmi lesquelles on trouve : le problme des maris jaloux : 3 couples doivent traverser unerivire, ils ont une seule barque leur disposition, qui ne peut transporter que 2 personnes. Les marissont jaloux et ne peuvent admettre que leur femme se retrouve seule en compagnie dun autre homme.Comment faire traverser tous les couples ? une mthode de construction de carrs magiques. des tours demagie avec les nombres.

Bachet publia en 1621 une traduction latine, avec commentaires, de lArithmtique de Diophante. Cestainsi que Fermat prit connaissance des travaux du mathmaticien grec, et cest en marge dun exemplairede la traduction de Bachet quil inscrivit sa fameuse note dans la marge : pour n>2, lquation en nombresentiers an + bn = cn na pas de solutions autre que la solution nulle. Les apports personnels de Bachetsont peu nombreux, et aussi oublis : ainsi, il semble quil soit le premier avoir conjectur que toutnombre est somme de 4 carrs, conjecture souvent attribue Waring, et dmontre pour la premire foispar Lagrange. De mme, il est le premier crire lidentit dite de Bzout (2 entiers a et b sont premiersentre eux si, et seulement si, il existe des entiers u et v avec au+bv=1) et donner une mthode dersolution algorithmique de celle-ci.

Claude Bachet souffra sa vie durant dune sant fragile, marque par les rhumatismes et les crises degoutte. Ainsi, lu membre de lAcadmie Franaise ds sa fondation en 1634, il ne peut se dplacer Parispour prononcer son discours inaugural. Il dcde le 26 fvrier 1638.

Gauss, Johann Carl Friedrich (17771855) Carl Friedrich Gauss, n le 30 avril 1777 Brunswick, estconsidr par ses pairs comme le prince des mathmaticiens. Il est la fois le dernier des classiques, etle premier des modernes, cest--dire quil a rsolu les problmes les plus classiques avec les mthodes lesplus modernes. Par exemple, il dmontra comment partager une tarte en 17 parts gales laide des seulsrgle et compas, ce qui tait un problme ouvert depuis les grecs. Mieux, il dmontra pour quels nombresce partage en parts gales est possible.

Gauss tait un gnie particulirement prcoce : 5 ans, le matre demandait de calculer 1+2+...+100,et Gauss inscrivit immdiatement le rsultat sur son ardoise : ce nest pas quil fut un gnial calculateur,mais il avait trouv une formule gnrale pour calculer de telles sommes. A luniversit, 19 ans, il fut lepremier dmontrer la loi de rciprocit quadratique, ce que ni Euler, ni Legendre navaient russi. Aucours de sa vie, il en donnera huit preuves ! ! ! Parmi ses autres prouesses, on peut citer la dmonstrationdu thorme fondamental de lalgbre, dans sa thse de doctorat en 1799, linvention de la thorie descongruences...

Le gnie de Gauss se manifesta dans dautres domaines : on lui doit dimportants travaux en lectricit,en optique, en thorie du potentiel. Ainsi, le "gauss" est devenu lunit dinduction magntique.

Il acheva sa carrire de mathmaticien en 1849, loccasion dun jubil en son honneur. Peu peu,sa sant se dtriore, et il meurt Gttingen le 23 fvrier 1855 pendant son sommeil.

55

Diophante dAlexandrie (200/214284/298 Diophante dAlexandrie, que lon appelle volontiers le prede lAlgbre, est un mathmaticien grec dont on ignore tout, ou presque, de la vie. On pense quil vivaitvers le 3 s. aprs J.C., mais on ne sait donner de dates plus prcises. Son oeuvre la plus clbre est untrait de 13 livres, les Arithmtiques, dont on ne connaissait que 6 volumes jusque rcemment. Quatreautres auraient t retrouvs en Iran en 1968.

Les Arithmtiques consistent en une collection de 130 problmes, en gnral des quations dont Dio-phante cherche les solutions positives fractionnaires. La grande avance de Diophante est son utilisationdun symbolisme dans lcriture mathmatique. Il est linventeur du Plethos, qui dsigne linconnue duproblme. Malgr cela, Diophante travaille toujours sur des exemples numriques, si bien quil ne donnesouvent quune seule solution possible un problme, e