INFO 1 Semestre 1 Anne 2012/2013

IUT de LAVAL
Dpartement Informatique
- Polycopi de cours -
Mathmatiques Discrtes
Yann Walkowiak
1
http://www.univ-lemans.fr/~ywalko
[email protected]
1. Merci Patricia Everaere et Serge Iovle dont les documents mont aid rdiger ce cours.
Table des matires
1 Thorie des ensembles 1
1.1 Ensembles et oprations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Proprits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Application entre deux ensembles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Cardinal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.5 Miscellannes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 Logique 13
2.1 Logique propositionnelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Prdicats et quanticateurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3 Thormes et dmonstrations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3 Relations sur un ensemble 21
3.1 Dnition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2 Oprations sur les relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.3 Proprits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.4 Relation dquivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.5 Relation dordre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4 Thorie des graphes : introduction 31
4.1 Graphes et modlisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.2 Graphe orient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.3 Graphe non orient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.4 Graphe partiel et sous-graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.5 Thorme des poignes de mains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.6 Chemin, chane, circuit et cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.7 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5 Arithmtique 39
5.1 Divisibilit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5.2 Nombres premiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
5.3 quation diophantienne ax +by = c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
i
ii Table des matires
5.4 Congruences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
5.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 Dnition - Exemples
Il est trs dlicat de donner une dnition rigoureuse de ce quest un ensemble. Nous nous contenterons
dune dnition intuitive bien susante pour nos besoins.
Dnition 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,
1
3
/ Z)
3. lensemble Q des nombres rationnels (
1
3
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 gure 1.1.
On a lhabitude de noter les ensembles avec des capitales majuscules et les lments dun ensemble avec
des minuscules. Un ensemble peut tre dni en extension, cest--dire en donnant la liste de ses lments,
ou en comprhension, cest--dire en donnant une proprit vrie par ses lments (et uniquement par
ses lments).
Exemple 1.1.3. 1. E = {2, 4, 6} est donn en extension
2. E = {x N | x est pair et 1 x 7} est le mme ensemble donn en comprhension.
Dnition 1.1.2. Il existe un ensemble ne contenant aucun lment. On appelle cet ensemble ensemble
vide 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 innit 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 peu
avec. Peut-on mettre un ensemble dans un autre ? Des lments peuvent-ils tre dans plusieurs ensembles
dirents ? Comment enlever des lments dun ensemble ? Bref, cest le moment de vous poser des
questions, je rpondrai certaines dans la suite, pour les autres, essayez dy rpondre par vous-mmes !
1.1.2 Inclusion, parties
Dnition 1.1.3. On dit que lensemble F est inclus dans lensemble E, et on note F E, si tous les
lments 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 gure 1.2)
Exemple 1.1.5. Soit lensemble E = {a, b, c}.
l lment a appartient lensemble E (a E)
l ensemble {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 B
et
B A
do la maxime, fort utile en pratique pour dmontrer une galit :
Une galit, cest deux inclusions
1.1.3 Oprations sur les ensembles
Dnition 1.1.4. Soient A et B deux ensembles inclus dans E. On dnit les oprations suivantes :
Intersection
A B = {x E / x A et x B}
Runion
A B = {x E / x A ou x B}
Complmentaire
A = {x E / x / A}
Dirence
A\ B = {x E / x A et x / B}
Exemple 1.1.6. Les diagrammes dEuler de la gure 1.3 illustrent ces direntes oprations.
Toutes ces oprations permettent de crer de nouveaux ensembles partir densembles de dpart. Le
rsultat 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 un
ordre 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) Dirence - A\ B = {a, b, g}
Figure 1.3 Oprations sur les ensembles
1.2 Proprits
Une fois ces oprations dnies, nous nous intressons leurs proprits. Citons tout dabord les
proprits 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, il
peut arriver que (A B) C = 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 vrierez bien que vous ne
drogez 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 que
trop vous conseiller de faire un diagramme dEuler illustrant chaque proprit an 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 dirents. Ce
concept dassociation entre deux objets est fondamental en mathmatiques et permet de modliser des
concepts comme des transformations, des relations. . . que nous rencontrerons dans les dirents cours.
1.3.1 Dnitions
Dnition 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 l antcdent de y par f.
1.3.2 Applications injectives, surjectives, bijectives
On distinguera parmi les applications entre deux ensembles celles qui nenvoient pas deux lments
dirents vers un mme lment (applications injectives) et celles qui occupent tout lespace darrive
(applications surjectives). La dnition suivante formalise ces notions.
Dnition 1.3.2. 1. f est dite injective si x
1
, x
2
A, (f(x
1
) = f(x
2
) x
1
= x
2
)
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 gure 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 un
unique antcdent x E. On peut donc dnir une application en associant tout lment y de F son
unique antcdent x dans E.
Cette application est alors appele application rciproque de f et est note f
1
.
Exemple 1.3.1. Lapplication f(x) = x
2
dnie de R
+
vers R
+
admet une rciproque quon note habi-
tuellement

x.
1.3.4 Compose
Dnition 1.3.3. Soient E, F et G trois ensembles et soient f une application de E vers F et g une
application 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 peut
faire correspondre un lment z de G par g. Lapplication de E dans G qui x de E fait correspondre
llment 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) = x
2
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 une
application 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
= f
1
g
1
.
1.4 Cardinal
1.4.1 Ensemble ni
Pour les ensembles contenant un nombre ni dlments, on souhaite tudier le lien entre les oprations
et le nombre dlments de chaque ensemble. Ceci nous permettra de faire du dnombrement et ainsi de
rsoudre des problmes complexes via une modlisation en thorie des ensembles.
Dnition 1.4.1. Si un ensemble A a un nombre ni dlments, on note |A| ou A, et on appelle
cardinal 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 sut de constater que quand on ajoute le nombre dlments
de A et le nombre dlments de B, on compte deux fois ceux qui sont la fois dans A et dans B. Le
seconde proprit est vidente puisque tout lment de A est galement dans B, donc B contient au
minimum autant dlment que A. La dernire proprit peut se dmontrer par rcurrence, je vous la
laisse en exercice, nous en dirons quelques mots en TD.
1.4.2 Proprits
Thorme 1.4.1. Soient E et F des ensembles nis.
1. |E| = |F| si et seulement sil existe une bijection de E sur F
2. |E| |F| si et seulement sil existe une injection de E sur F
3. |E| |F| si et seulement sil existe une surjection de E sur F
Thorme 1.4.2. Soient E et F des ensembles nis de mme cardinal et f une application de E vers
F. Alors
fbijective finjective fsurjective
1.4.3 Ensemble dnombrable
Dnition 1.4.2. Un ensemble E est dit dnombrable sil existe une bijection entre E et lensemble N
des 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 innis ? Peut-on les comparer ? Un dbut de rponse dans la section 1.5.2 et
suivantes
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 (P
1
) (P
2
), on suppose que (P
1
) est vraie et on cherche dmontrer (P
2
).
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 (P
1
) (P
2
), on dmontre donc que (P
1
) (P
2
) et (P
2
) (P
1
).
Remarque. Pour montrer quune implication est fausse, il sut de donner un contre-exemple, cest--
dire un cas particulier o lhypothse est vrie mais pas la conclusion.
1.5.2 Lhtel de linni
Monsieur et Madame Hilbert sont les grants dun htel, appel humblement Htel de linni. Ce
nom na pas t donn au hasard, leur htel comporte une innit de chambres, numrotes par les entiers
de 1 jusqu . . . linni.
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 puis
son chat, et dcide de demander au client de la chambre 1 de dmnager dans la chambre 2, en disant au
client de la chambre 2 daller dans la chambre 3. . . et ainsi de suite jusqu linni. Ainsi, la chambre 1
sera libre pour notre touriste allemand!
Mme Hilbert na pas ni de fliciter M Hilbert pour son ingnieuse ide quun car de touristes arrive
lhtel. De ce car, descend une innit de touristes hollandais qui veulent tous dormir lhtel !
Comment trouver une innit de places libres dans un htel complet ? Perplexe, Mme Hilbert regarde
son mari qui la regarde ainsi que son chat, quand Mr Hilbert fait un appel au micro dans toutes les
chambres. Il demande tous les clients de noter leur numro de chambre et daller dans la chambre qui
porte 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 ainsi
libres et peuvent accueillir tous les touristes hollandais !
1.5.3 Comparons les innis
Il y a autant dentiers pairs que dentiers impairs On la vu dans lhistoire prcdente, il semble dicile
de comparer des innis, mais nous allons tout de mme tenter de le faire. Que pensez-vous de lide quil
y a autant dentiers pairs que dentiers impairs ? Elle semble intuitivement valable mais il faut donner un
sens au mot autant dans un contexte densembles innis. Lide la plus naturelle est de considrer que
deux ensemble possdent autant dlments si on peut trouver une application bijective entre ces deux
ensembles. En eet, on cre ainsi une association 1--1 entre les lments des deux ensembles. Considrons
par exemple lapplication suivante, qui va de lensemble A des entiers pairs vers lensemble B des entiers
impairs :
f : A B
n n + 1
Vous vrierez 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 entiers
naturels vers lensemble A des entiers naturels pairs :
f : N A
n 2n
1.5. Miscellannes 9
Elle est injective puisque deux entiers distincts senvoient toujours sur des entiers pairs distincts. Elle est
surjective puisque tout entier pair scrit comme un multiple de 2. Elle est donc bijective, ce qui prouve
quil y a autant dentiers pairs que dentiers ! Etonnant non? Mais ce nest pas ni. . .
Il y a autant dentiers relatifs que dentiers naturels Si vous avez bien suivi jusquici, vous avez
compris quil sut de prouver que Z est en bijection avec N. Ce nest pas trop dicile, mme si un peu
plus technique crire proprement. Lide est de chercher un moyen dnumrer les lments de Z, ce
quon peut faire assez naturellement en alternant les entiers positifs et ngatifs : 0, 1, -1, 2, -2, 3, -3. . . Je
vous laisse vrier que lapplication suivante convient :
f : N Z
n
n+1
2
si n est impair
n
n
2
si n est pair
Il y a autant de rationnels que dentiers Intressons-nous dsormais lensemble des rationnels qui
est lensemble des fractions
p
q
avec p Z et q N

, p et q tant sans diviseur commun. Je ne vais

pas crire de faon explicite la bijection qui est plus dsagrable crire qu comprendre. Lide est
la suivante : on souhaite trouver un moyen dnumrer toutes les fractions possibles, on dresse alors
un 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 qui
peut tre fait en le lisant diagonale par diagonale :
H
H
H
H
H
p
q
1 2 3 . . .
1 1 2 6 . . .
2 3 5
3 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 les
rationnels ? Et bien la rponse est non, et la dmonstration, due Georg Cantor
2
, est particulirement
jolie. Il sagit dune preuve par labsurde : supposons en eet quil soit possible dtablir une liste numrote
(innie bien sr !) des rels de lintervalle [0, 1[.
1 0, x
1,1
x
1,2
x
1,3
. . .
2 0, x
2,1
x
2,2
x
2,3
. . .
3 0, x
3,1
x
3,2
x
3,3
. . .
.
.
.
.
.
.
Construisons maintenant le rel dont lcriture dcimale est
0, y
1
y
2
y
3
. . .
o les dcimales sont choisies telles que y
1
= x
1,1
, y
2
= x
2,2
, y
3
= x
3,3
. . .
Ce rel, par construction, nest pas dans la liste ! En eet, a ne peut pas tre le premier car la
premire dcimale est dirente, ni le second car la deuxime dcimale est dirente, et ainsi de suite. . .
Ceci prouve quil nest pas possible dtablir une liste numrote de tous les rels de [0, 1[. Il ny a donc
pas 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 linni des entiers est plus petit que linni 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 arme quil nexiste pas densemble dont le cardinal
est 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
Dnition 2.1.1. On appelle proposition logique une armation ayant une valeur de vrit, i.e. qui est
soit vraie soit fausse.
Exemple 2.1.1. Les armations suivantes sont des propositions logiques ; lesquelles sont vraies ? fausses ?
2 + 3 = 5
= 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 scientique consiste cherche connatre la valeur de vrit de direntes 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 valeur
de vrit dpendant des valeurs de vrit des propositions donnes.
Dnition 2.1.2. La ngation dune proposition p, note p, a pour valeur V si p a pour valeur
F et F si p a pour valeur V . Sa table de vrit est :
p p
V F
F 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 les
deux vraies. Sa table de vrit est :
p q p q
V V V
V F F
F V F
F F F
La disjonction de deux propositions p et q, note p q, a pour valeur V ssi p ou q (ou les deux) est
vraie. Sa table de vrit est :
p q p q
V V V
V F V
F V V
F 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 et
lquivalence.
Dnition 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 q
V V V
V F F
F V V
F F V
On crira p q si la proposition p q est vraie.
L quivalence de deux propositions p et q, note p q, a pour valeur V ssi p et q ont mme valeur
de vrit. Sa table de vrit est :
p q p q
V V V
V F F
F V F
F F V
On crira p q si la proposition p q est vraie.
Limplication est intuitivement la plus dicile apprhender : le faux implique nimporte quoi ! Par
exemple, 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 vrit
de q, simplement car p est faux.
2.1. Logique propositionnelle 15
2.1.3 Formules propositionnelles
Dnition 2.1.4. On appelle formule propositionnelle la combinaison de propositions logiques et de
connecteurs logiques. On peut crire la table de vrit dune telle formule en fonction des valeurs des
vrit 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) q
V V V
V F F
F V V
F 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) q
2. exercice : montrer que p q = (p q) (q p)
On distingue les formules propositionnelles qui sont toujours vraies et celles qui sont toujours fausses :
Dnition 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 dnis satisfont un certain nombre de proprits numres
dans la proposition suivante. Celles-ci nous permettront souvent de simplier 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) commutativit
p q = q p et p q = q p
(iv) idempotence
p 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 quanticateurs
2.2.1 Prdicats
Dnition 2.2.1. Un prdicat est une proposition logique P(x) qui dpend dune variable x. La valeur
de vrit de P(x) dpend du choix de x.
Exemple 2.2.1. 1. P
1
(x) =x est pair, alors P
1
(2) est vrai mais P
1
(3) est faux.
2. P
2
(x) =x > x 1, alors P
2
(x) est toujours vrai quand x est dans R.
3. P
3
(x) =x = x, alors P
3
(x) est toujours faux.
- Un prdicat peut dpendre de plusieurs variables (par ex. P(x, y) =x<y)
- On peut oprer logiquement sur les prdicats comme on le fait avec les propositions logiques.
2.2.2 Quanticateurs
(a) Quel que soit
Quand un prdicat P(x) est vrai pour toutes les valeurs de x dun ensemble E, on crit
x E, P(x)
et on dit Pour tout x dans E, P(x) ou Quel que soit x dans E, P(x)
Exemple 2.2.2. 1. x R, x = x
2. x ] 1, 1[, 0 x
2
< 1
Ce quon obtient est une proposition logique qui ne dpend plus de
x.
x est une variable muette, on peut la remplacer par nimporte quel autre nom de variable
(b) Il existe
Quand un prdicat P(x) est vrai pour au moins une valeur de x dun ensemble E, on crit
x E, P(x)
et on dit Il existe
1
x dans E, P(x)
Exemple 2.2.3. 1. x R, x
2
= x
2. x ] 1, 1[, x
2
= 0
1. sous-entendu au moins un
2.2. Prdicats et quanticateurs 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[, x
2
= 0
2.2.3 Quanticateurs et connecteurs logiques
Un prdicat auquel on applique un quanticateur devient une proposition logique. Vous tes certai-
nement impatients dappliquer les dirents connecteurs , et ces quanticateurs et dobserver ce
quon obtient. Il est alors urgent de faire trs attention ce que vous crivez car une erreur est trs vite
arrive 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 quanticateurs et connecteurs lo-
giques !
2) Ne jamais intervertir quanticateur et connecteur, ni deux quanticateurs sans avoir pris la peine de
rchir.
(i) eet de la ngation sur les quanticateurs

_
x E, P(x)
_
= x E, (P(x))

_
x E, P(x)
_
= x E, (P(x))
(ii) eet de la conjonction sur les quanticateurs
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) eet de la disjonction sur les quanticateurs
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 dmonstrations
rigoureuses. Un thorme est un rsultat obtenu en faisant oprer des oprations logiques sur des objets
mathmatiques (dnis dans des dnitions) et des rsultats connus. An dinitier la thorie, on dni
un 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 enrichit
lensemble 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 eet, dans le cas o P est fausse, limplication est toujours
vraie.
3. Disjonction de cas : quand le nombre de possibilit est ni, il est envisageable dtudier tous les cas
possibles.
Exemple 2.3.2. pour montrer que (P Q) R, il sut 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 A
5. 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 < 2
n
.
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 Dnition
3.1.1 Ensemble produit
Dnition 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 nis, alors AB aussi et
|AB| = |A| |B|
Si B = A, alors on note parfois AA = A
2
, AAA = A
3
. . .
Vous avez certainement dj rencontr les ensembles R
2
(le plan) et R
3
(lespace).
3.1.2 Relation binaire
Dnition 3.1.2. Une relation binaire R dun ensemble A sur un ensemble B est un sous-ensemble de
AB.
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 dnir une relation en donnant une condition ncessaire et susante pour que
deux lments x et y soient en relation.
Exemple 3.1.2. E = {1, 2, 3, 4} xRy x y
On a 2R1, 3R3 mais pas 1R4
3.1.3 Reprsentation matricielle
Dnition 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 0
1 1 0 0
1 1 1 0
1 1 1 1
_
_
_
_
3.1.4 Reprsentation sagittale
Dnition 3.1.4. Soit E lensemble {1, 2, . . . , n}. On appelle reprsentation sagittale ou graphe dune
relation R sur E le graphe dont les sommets sont les lments de E et pour lequel il y a une che du
sommet x vers le sommet y si xRy.
Exemple 3.1.4. E = {1, 2, 3, 4}, xSy x y
1

2
.
3

>
>
>
>
>
>
>

3.2 Oprations sur les relations

Les relations sur E tant des sous-ensembles de E E, on peut leur appliquer les oprations sur les
ensembles.
Soient R et S deux relations sur E. On dnit :
la runion : R S
a(R S)b (aRb) ou (aSb)
lintersection : R S
a(R S)b (aRb) et (aSb)
3.3. Proprits 23
le complmentaire : R
aRb (aRb)
La notion de relation binaire nest pas commutative, on introduit ainsi lopration de rciproque qui
change les variables :
la transpose : R
t
a(R
t
)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 direntes oprations dnies ci-dessus et don-
ner leur reprsentation matricielle et sagittale. Comment obtient-on la matrice et les graphes des relations
R S, R S, R, et R
t
en fonction des matrices et grpahes de R et S ?
3.3 Proprits
3.3.1 rexivit
Dnition 3.3.1. La relation R est dite rexive si
x E, xRx
Exemple 3.3.1. Sur lensemble E = {1, 2, 3, 4}, la relation R dnie par
xRy x|y (x divise y)
est rexive car 1|1, 2|2, 3|3 et 4|4.
Exemple 3.3.2. Sur lensemble E = {1, 2, 3, 4}, la relation R dnie par
xRy x < y
nest pas rexive car 1 nest pas strictement infrieur 1 !
Sur la matrice, la rexivit se traduit par une diagonale ne contenant que des 1. Dterminez dans
les matrices suivantes, lesquelles sont des matrices reprsentant une relation rexive :
M
1
=
_
_
1 0 1
1 1 0
0 0 1
_
_
M
2
=
_
_
1 0 1
0 0 1
1 0 1
_
_
M
3
=
_
_
_
_
1 1 0 1
1 1 0 0
1 1 1 1
0 1 1 0
_
_
_
_
M
4
=
_
_
_
_
_
_
1 0 1 0 0
0 1 0 0 0
1 0 1 0 0
0 1 1 1 0
0 0 0 1 1
_
_
_
_
_
_
Sur le graphe, cel se traduit par la prsence dune boucle sur chaque sommet. Dterminez dans
les graphes de la gure 3.1, lesquels sont des graphes reprsentant une relation rexive.
24 Relations sur un ensemble
G
1
: 1

2
.
3

>
>
>
>
>
>
>

G
2
: a
b
.
c

G
3
: 1

2
.
3

G
4
: a
.

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

3.3.2 Symtrie
Dnition 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 dnie par
xRy 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 dnie par
xRy 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 (sil
y 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 :
M
1
=
_
_
1 1 0
1 1 0
0 0 1
_
_
M
2
=
_
_
1 0 1
0 0 1
1 0 1
_
_
M
3
=
_
_
_
_
1 1 0 1
1 1 0 0
1 1 1 1
0 1 1 0
_
_
_
_
M
4
=
_
_
_
_
_
_
1 0 1 0 0
0 1 0 1 0
1 0 0 1 0
0 1 1 1 0
0 0 0 0 1
_
_
_
_
_
_
Sur le graphe, la symtrie se traduit par la non prsence de che simple. Autrement dit, ds quil
y a une che entre deux sommets, il doit y avoir galement la che dans lautre sens. Dterminez dans
les graphes de la gure 3.1, lesquels sont des graphes reprsentant une relation symtrique.
3.3.3 Antisymtrie
Dnition 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 dnie 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 dnie par
xRy x a la mme parit que y
nest pas antisymtrique car 2 et 4 ont la mme parit et pourtant 2 = 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 les
matrices suivantes, lesquelles sont des matrices reprsentant une relation antisymtrique :
M
1
=
_
_
1 0 1
1 1 0
0 0 1
_
_
M
2
=
_
_
1 0 1
0 0 1
1 0 1
_
_
M
3
=
_
_
_
_
1 1 0 1
0 1 0 0
1 1 1 1
0 1 0 0
_
_
_
_
M
4
=
_
_
_
_
_
_
1 0 1 0 0
0 1 0 0 0
1 0 1 0 0
0 1 1 1 0
0 0 0 1 1
_
_
_
_
_
_
Sur le graphe, cel se traduit par la non prsence de che double (il peut en revanche y avoir des
boucles). Dterminez dans les graphes de la gure 3.1, lesquels sont des graphes reprsentant une relation
antisymtrique.
3.3.4 Transitivit
Dnition 3.3.4. La relation R est dite transitive si
(x, y, z) E
3
, xRy et yRz xRz
Exemple 3.3.7. Sur lensemble E = {1, 2, 3, 4}, la relation R dnie 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 dnie 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 sur
la matrice. Il est toutefois possible de vrier toutes les relations possibles. Dterminez dans les matrices
suivantes, lesquelles sont des matrices reprsentant une relation transitive :
M
1
=
_
_
1 0 1
1 1 0
0 0 1
_
_
M
2
=
_
_
1 0 1
0 0 1
1 0 1
_
_
26 Relations sur un ensemble
M
3
=
_
_
_
_
1 1 0 1
1 1 0 0
1 1 1 1
0 1 1 0
_
_
_
_
M
4
=
_
_
_
_
_
_
1 0 1 0 0
0 1 0 0 0
1 0 1 0 0
0 1 1 1 0
0 0 0 1 1
_
_
_
_
_
_
Sur le graphe, cel se traduit par le fait suivant : sil y a une che dun sommet x un sommet y
et une che du sommet y un sommet z, alors la che raccourci de x z doit apparatre galement.
Dterminez dans les graphes de la gure 3.1, lesquels sont des graphes reprsentant une relation transitive.
3.4 Relation dquivalence
3.4.1 Dnition
Dnition 3.4.1. Une relation ayant les proprits de rexivit, 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 x
de 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 permet
par exemple de construire lensemble des rationnels (lide est de regrouper les direntes critures dune
mme fraction et de les identier un seul lment (cf. TD)). Les proprits qui suivent sont importantes
et 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 signie que zRx. Or on sait que xRy (car yRx
et la relation est symtrique), donc par transitivit, on en dduit que zRy, ce qui signie que z y.
Montrons maintenant linclusion inverse : y x. Soit z y, cel signie que zRy. Or on sait que
yRx, donc par transitivit, on en dduit que zRx, ce qui signie que z x.
Ce rsultat signie 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 reprsenter
la 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 dnie 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 Dnition
Dnition 3.5.1. Une relation ayant les proprits de rexivit, d antisymtrie et de transitivit est
appele 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.
Dnition 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 eet, on na ni
2 est un multiple de 3 ni 3 est un multiple de 2 par exemple.
3.5.2 Diagramme de Hasse
Dnition 3.5.3. Soit R une relation dordre sur E. On dit quun lment y E domine un lment
x E si
_
_
_
xRy
x = y
il nexiste pas dlment z E; xRz et zRy (z = 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
Dnition 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, aRx
1. 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

B
B
B
B
B
B
B
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 le
tableau suivant :
F = {1, 2, 5} G = {2, 6}
majorants 10,30 6,30
minorants 1 1,2
maximum - 6
minimum 1 2
borne suprieure 10 6
borne infrieure 1 2
lments maximaux 2,5 6
lments 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 direntes :
relation sur un ensemble ni (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 est
termine
Il existe dirents types de graphes, orients ou non, ou autorisant plusieurs arcs entre deux sommets.
4.2 Graphe orient
Dnition 4.2.1. Un graphe orient est un couple G = (S, A) o S est un ensemble ni appel ensemble
des 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 chaque
sommet et les arcs entre deux sommets sont reprsents par une che.
Exemple 4.2.1.
S = {a, b, c, d} A = {(a, b), (b, a), (b, d), (c, c), (c, d)}
a

c

d
Figure 4.1 Reprsentation sagittale du graphe de lexemple 4.2.1
Dnition 4.2.2 (Terminologie). Soient G = (S, A) un graphe orient et a = (x, y) A un arc de G.
x est appel l origine de a et y l extrmit 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 dnit alors
d
+
(x) = |
+
(x)| = degr extrieur de x
d

(x) = |

(x)| = degr intrieur de x

et
d(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 propre
prdcesseur.
Dnition 4.2.3. Soit G = (S, A) un graphe avec S = {x
1
, x
2
, . . . , x
n
}.
On appelle matrice dadjacence du graphe G la matrice M = (a
i,j
)
1in
1jn
carre dordre n dnie par
a
i,j
=
_
1 si (x
i
, x
j
) A
0 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 0
1 0 0 1
0 0 1 1
0 0 0 0
_
_
_
_
Sa liste dadjacence est
a b
b a d
c c d
d
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
Dnition 4.3.1. Un graphe non orient est un couple G = (S, A) o S est un ensemble ni appel
ensemble des sommets et A est un ensemble de paires (non ordonnes) de sommets appel ensemble des
artes.
Comme pour les graphes orients, on peut visualiser un graphe via sa reprsentation sagittale : on
dessine 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 remplaant
les 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
Dnition 4.3.2 (Terminologie). Soient G = (S, A) un graphe non orient et a = (x, y) A une arte
de 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 dnit alors le degr dun sommet x :
d(x) =
_
|(x)| sil ny a pas de boucle en x
|(x)| + 1 sinon
Dnition 4.3.3. Soit G = (S, A) un graphe non orient avec S = {x
1
, x
2
, . . . , x
n
}.
On appelle matrice dadjacence du graphe G la matrice M = (a
i,j
)
1in
1jn
carre dordre n dnie par
a
i,j
=
_
1 si (x
i
, x
j
) A
0 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 0
1 0 0 1
0 0 1 1
0 1 1 0
_
_
_
_
Sa liste dadjacence est
a b
b a d
c c d
d b c
quon peut aussi crire sous la forme {{b}, {a, d}, {c, d}, {b, c}}.
4.4 Graphe partiel et sous-graphe
Dnition 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

).
Dnition 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

, A
S
) o (x, y) A
S
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 a

xS
d

(x) =

xS
d
+
(x) = |A|
Si G = (S, A) est un graphe non orient, on a

xS
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
Dnition 4.6.1. Soit G = (S, A) un graphe orient. Un chemin C de longueur k dun sommet x vers
un sommet y est une suite (x
0
, x
1
, . . . , x
k
) de sommets tels que x
0
= x, x
k
= y et (x
i1
, x
i
) A pour
i = 1, 2, . . . , k.
x est appel l origine et y l extrmit 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.
Dnition 4.6.2. Soit G = (S, A) un graphe orient. Un circuit est un chemin de longueur non nulle
dont lextrmit et lorigine sont identiques.
4.7. Exercices 35
Dnition 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 eet, si un chemin passe deux fois par le mme arc, il passe
obligatoirement plusieurs fois par les extrmits de cet arc.
Dnition 4.6.4. Les notions correspondantes existent pour les graphes non orients. On utilise alors
plutt le vocabulaire suivant :
Orient Non orient
arc arte
chemin chane
circuit cycle
4.6.2 Utilisation de la matrice dadjacence
Dnition 4.6.5. On dnit le produit de deux matrices dadjacence de mme ordre n de la faon
suivante : si A = (a
i,j
) et B = (b
i,j
), alors AB = (c
i,j
) avec
c
i,j
=
n

k=1
a
i,k
b
k,j
On note A
2
le produit AA et A
p
le produit AA A
. .
p fois
.
Proposition 4.6.1. Soit G un graphe orient (respectivement non orient) dordre n et soit M sa matrice
dadjacence. Alors pour tout entier k > 0 et pour tout couple (i, j) {1, 2, . . . , n},
Llment M
k
(i, j) est le nombre de chemins (respectivement chanes) de longueur k de i vers j.
Llment M
k
(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 0
1 0 1 0
1 1 0 1
0 0 1 0
_
_
_
_
1. Donner la reprsentation par liste dadjacence du graphe.
2. Donnez les degrs de chaque sommet. Vrier le lemme des poignes de main.
3. Calculer M
2
, puis M
3
et M +M
2
.
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. An de simplier, on supposera que
toutes les pistes ont la mme dicult et on sintressera donc seulement aux randonnes possibles.
La (petite) station comporte 6 lieux dirents, quon numrotera de 1 6. Toutes les pistes sont
double sens. Le tableau suivant indique les pistes existant :
lieu vers lieu
1 2,4
2 1,3,5
3 2,5
4 1,5,6
5 2,3,4,5,6
6 4,5
1. Comment peut-on modliser les direntes pistes de ski ? Faites-le.
2. Comment dterminer, par le calcul, le nombre de parcours dirents empruntant deux pistes suc-
cessives au dpart du lieu 5. Calculer ce nombre.
Exercice 4.4 Mr et Mme X assistent une runion. Il y a trois autres couples dans lassistance et plusieurs
poignes de mains sont changes. Personne ne serre sa propre main et les poux ne se serrent pas la
main. Deux personnes quelconques de lassemble se serrent la main au plus une fois. Mr X constate que
les 7 autres personnes ont chang des poignes de mains en nombres tous distincts. Combien de poignes
de 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 euve ; un passeur souhaite les
transporter sur lautre rive mais, sa barque tant trop petite, il ne peut transporter quun seul dentre
eux la fois. Comment doit-il procder an de ne jamais laisser ensemble et sans surveillance le loup et
la 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
Dnition 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, ce
quon 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 eet, 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 dnir les notions de PGCD et de PPCM.
Dnition 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 que

a = 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 eectuer
des divisions euclidiennes successives de la faon suivante :
a = bq
1
+r
1
avec 0 r
1
< b
b = r
1
q
2
+r
2
avec 0 r
2
< r
1
r
1
= r
2
q
3
+r
3
avec 0 r
3
< r
2
.
.
.
.
.
.
r
n2
= r
n1
q
n
+r
n
avec 0 r
n
< r
n1
r
n1
= r
n
q
n+1
+ 0
On remarque que les restes successifs forment une suite dentiers naturels strictement dcroissante, ce qui
implique 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 r
n
avec les notations
ci-dessus.
Preuve. Notons d le pgcd de a et b.
(1) d divise r
n
On sait que d divise a et b, il divise donc, daprs la proposition 5.1.1, la quantit a bq
1
= r
1
.
Ceci signie que d divise b et r
1
donc de la mme faon, on sait que d doit diviser b r
1
q
2
= r
2
. En
itrant ce raisonnement sur les divisions successives, on obtient nalement que d divise r
n
, ce qui signie
en particulier que d r
n
.
(2) r
n
divise a et b
La dernire division nous dit que r
n1
= r
n
q
n+1
, donc r
n
divise r
n1
.
Dans la division prcdente, comme r
n
divise r
n
et r
n1
, on en dduit que r
n
divise r
n2
.
En itrant ce raisonnement, on en dduit tout dabord que r
n
divise b puis que r
n
divise a, ce qui
prouve que r
n
est un diviseur commun de a et b.
(3) conclusion
Nous avons montr au point (2) que r
n
est un diviseur commun de a et b. Or, on sait par la dnition du
pgcd que d est le plus grand diviseur commun de a et b, ce qui signie donc que d est suprieur ou gal
r
n
. Le point (1) donnant lingalit inverse, on en dduit lgalit d = r
n
.
Exemple 5.1.2. Calculons le pgcd de 17 et 9 en utilisant lalgorithme dEuclide :
17 = 9 1 + 8
9 = 8 1 +1
8 = 1 8 + 0
Donc 17 9 = 1.
Pour calculer le ppcm, on pourra calculer le pgcd et utiliser la proposition suivante, qui fait le lien
entre ces deux quantits :
Proposition 5.1.2. Soient a et b deux entiers naturels. Alors
(a b) (a b) = a b
1. 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 b
Exemple 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 = 1
qui 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 lalgorithme
dEuclide qui va nous y aider. Lide est de remonter les divisions obetnues an dexprimer le pgcd en
fonction de a et b. On dit alors quon applique lalgorithme dEuclide tendu.
Sil y a beaucoup de divisions, il convient de procder avec mthode an de minimiser les risques
derreur. Dans lexemple ci-dessous, je vous propose une faon de procder qui a le mrite de ne pas
manipuler 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 nom
aux restes successifs, puis on crit, ct de chaque division et en partant du haut, lexpression du reste
en fonction de a et b :
a
..
17 =
b
..
9 1 +
c
..
8 c = a b
b
..
9 =
c
..
8 1 +
d
..
1 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 9
qui est une galit de Bachet-Bzout pour 17 et 9.
5.2 Nombres premiers
Dnition 5.2.1. Un nombre premier est un entier naturel strictement suprieur 1 qui nest divisible
que par 1 et par lui-mme.
Exemple 5.2.1. Les premiers nombres premiers sont 2, 3, 5, 7, 11, etc.
Dnition 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 sans
quaucun 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 la
cryptographie (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 inni.
Preuve. La dmonstration que nous allons voir, qui est celle dEuclide, se fait par labsurde. Supposons
que lensemble P est ni et notons P = {p
1
, . . . , p
n
} ses lments tris par ordre croissant. Nous allons
montrer quon peut alors en construire un nouveau qui nest pas dans P. Considrons lentier
q = p
1
p
2
. . . p
n
+ 1
Il y a alors deux possibilits :
soit q est premier, mais alors, comme q est clairement suprieur p
n
, q est un nombre premier qui
nest 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 peut
tre aucun des p
i
car sinon, on aurait p|(p
1
. . . p
n
et p|q et donc p|1 ce qui est impossible. p est donc
un nombre premier qui nest pas dans P, ce qui est absurde.
Lensemble P des nombres premiers est donc ncessairement inni.
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 = ak
2. 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 vous
en 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 les
nombres premiers sont en quelque sorte les briques qui permettent de construire nimporte quel nombre
entier.
Thorme 5.2.3 (Thorme de dcomposition en facteurs premiers). Tout entier n 2 admet une
dcomposition unique en facteurs premiers
n = p

1
1
p

2
2
p

k
k
avec p
1
, p
2
, . . . , p
k
P premiers distincts et
1
,
2
, . . . ,
k
entiers strictement positifs.
Exemple 5.2.2. La dcomposition de 198 en facteurs premiers est
198 = 2 3
2
11
3. 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 eectuant
les divisions :
198 2
99 3
33 3
11 11
1
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 3
2
11
b = 2
2
3 7 11
2. en utilisant lgalit p
0
= 1, on crit a et b avec les mmes nombres premiers :
a = p

1
1
p

2
2
. . . p

k
k
b = p

1
1
p

2
2
. . . p

k
k
Sur lexemple, on obtient :
a = 2 3
2
7
0
11
b = 2
2
3 7 11
3. on a alors :
a b = p
min(
1
,
1
)
1
p
min(
2
,
2
)
2
. . . p
min(
k
,
k
)
k
et
a b = p
max(
1
,
1
)
1
p
max(
2
,
2
)
2
. . . p
max(
k
,
k
)
k
Sur lexemple, on obtient :
a b = 2 3 11 = 66
a b = 2
2
3
2
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 ntudiera
ici 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 la
preuve de lexistence dune solution mais aussi le moyen de dterminer lensemble de toutes les solutions
de lquation.
Commenons par montrer la condition ncessaire : si x et y sont des solutions dans Z de lquation
ax +by = c, ceci signie que tout entier qui divise a et b divise ncessairement ax +by, cest--dire c. En
particulier, 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 prouver
que 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 lhypothse
que d divise c. En notant a
1
=
a
d
, b
1
=
b
d
et c
1
=
c
d
, on a :
(x, y) solution de ax +by = c (x, y) solution de a
1
x +b
1
y = c
1
avec dsormais a
1
b
1
= 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 eet, on sait quil existe u et v dans Z tels que a
1
u + b
1
v = 1, ce qui, en multipliant
par c
1
, nous dit que a
1
c
1
u +b
1
c
1
v = c
1
. On a donc trouv une solution de lquation : le couple (x
0
, y
0
)
dni par x
0
= c
1
u et y
0
= c
1
v.
An de dterminer les autres solutions, nous allons utiliser la solution (x
0
, y
0
). En eet, une autre
solution (x, y) vrie :
a
1
x +b
1
y = c
1
= a
1
x
0
+b
1
y
0
ce qui est quivalent
a
1
(x x
0
) = b
1
(y y
0
) ()
On a alors a
1
|(b
1
(y y
0
)), or on sait que a
1
b
1
= 1, donc daprs le thorme de Gauss, a
1
|(y y
0
),
cest--dire :
k Z; y y
0
= a
1
k y = y
0
+a
1
k
En rinjectant cette valeur de y dans (), il vient :
a
1
(x x
0
) = b
1
a
1
k
soit, en simpliant par a
1
(qui est bien non nul),
x = x
0
b
1
k
On en dduit donc que toute autre solution scrit ncessairement
_
x = x
0
b
1
k
y = y
0
+a
1
k
avec k Z
Rciproquement, on vrie que (x, y) dni comme ci-dessus est solution de a
1
x +b
1
y = c
1
:
a
1
x +b
1
y = a
1
(x
0
b
1
k) +b
1
(y
0
+a
1
k) = a
1
x
0
+b
1
y
0
= c
1
Donc lensemble S des solutions de lquation ax +by = c est
S = {(x
0
b
1
k, y
0
+a
1
k) | k Z}
o (x
0
, y
0
) 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 on
peut la simplier 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 pour

3 et 14 (pas besoin de lalgorithme dEuclide ici, on trouve u et v au "feeling") :
3 5 14 1 = 1
puis on multiplie par 5 pour obtenir une solution particulire de (E

) :
3 25 14 5 = 5
donc x
0
= 25, y
0
= 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 5
ce 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 que
ncessairement 3|(y 5), cest--dire
k Z; y 5 = 3k y = 5 + 3k
ce qui donne alors pour x :
3(x 25) = 14 (3k) x = 25 + 14k
On vrie que x = 25 + 14k et y = 5 + 3k sont bien solutions de (E

) :
3(25 + 14k) 14(5 + 3k) = 3 25 14 5 = 5
Lensemble des solutions de (E) est donc
S = {(25 + 14k, 5 + 3k) | k Z}
5.4 Congruences
5.4.1 Modulo
Dnition 5.4.1. Soient a, b et n trois entiers (n > 0). On dit que a et b sont congrus modulo n, et on
note a b mod n ou a b [n], si et seulement si a et b ont le mme reste dans la division euclidienne
par n.
a b mod n n|(a b) k Z; a = b +kn
Exemple 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 n
c d mod n
Alors on a
1. a +c b +d mod n
2. 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 sur

Z.
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 dnit 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 dnies, i.e. indpendantes du choix du
reprsentant de chaque classe.
La division nexiste pas dans Z/nZ. Nanmoins, le concept dinverse va nous permettre de nous en
passer.
Inverse dans Z/nZ
Dnition 5.4.2. On dit quun lment a Z/nZ est inversible si
b Z/nZ; a.b = 1
On note alors cet lment a
1
et on lappelle linverse de a.
5.4. Congruences 47
La proposition suivante donne un critre dinversibilit et nous donne mme un moyen dobtenir
linverse dun lment.
Proposition 5.4.3. Soit a Z/nZ, alors
a est inversible dans Z/nZ a n = 1
preuve. Si a est inversible, alors il existe un b vriant a.b = 1, ce qui peut encore scrire ab = 1 + kn
avec k Z. On en dduit que tout diviseur commun de a et n est un diviseur de 1, et donc le pgcd de a
et 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 signie que a est inversible
et 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 1
1
= 1), 3 est inversible (3.3 = 9 = 1 donc
3
1
= 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 type
a.x+b = c. La premire tape consiste faire passer le b de lautre ct, comme on le ferait pour la mme
quation 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 dans
Z/nZ! Cependant, quand a est inversible, on peut multiplier par a
1
ce qui revient se dbarrasser du
terme devant le x.
Si a est inversible On multiplie donc par linverse de a et on obtient une unique solution dans Z/nZ :
x = a
1
(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 divise
tout par a n
ax
a n

c b
a n
mod
n
a n
et 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 Bob
Plus prcisment, Alice souhaite envoyer un message Bob mais veut sassurer que seul Bob sera capable
de le dchirer, i.e. quune personne interceptant le message ne pourra le comprendre. Il y deux grandes
catgories de systmes permettant de crypter une information : les systmes cl prive (Bob et Alice se
partagent une cl permettant de dcoder le message) comme DES ou AES, et les systmes cl publique
que nous allons tudier par le biais de RSA.
5.5.2 Fonction dEuler
Dnition 5.5.1. Soit m 1 un entier, on dnit
(m) = {1 n m1 | 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 calculer
en 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

p
1
.
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 utilise
les proprits prcdentes :
(18) = (2 3
2
) = (2) (3
2
) = (2 1) (3
2
3) = 6
En plus de donner des informations sur les inversibles dans Z/mZ, la fonction dEuler vrie une
proprit qui nous permettra de calculer rapidement des grandes puissances dans Z/mZ.
Thorme 5.5.2 (Thorme dEuler). Si a m = 1, alors
a
(m)
1 mod m
Remarque. Ce thorme gnralise le rsultat suivant connu sous le nom de petit thorme de Fermat :
p premier a
p
a mod p
Application au calcul de puissances modulo m
On souhaite connatre le reste de la division de 7
602
par 18. Il est videmment hors de question de
poser la division. . . En revanche, le thorme dEuler nous dit que, tant donn que 7 18 = 1, on a
7
(18)
1 mod 18
cest--dire
7
6
1 mod 18
5.5. Cryptographie 49
On peut alors crire
7
602
(7
6
)
100
7
2
mod 18
7
2
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 un
entier tel que 0 a n, alors
k N, a
k(n)+1
a mod n
Le principe de fonctionnement du systme de cryptographie RSA est le suivant : chaque personne
disposera 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 q
2. calculer n = p q
3. 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 du
message : A=01, B=02, ... puis elle crypte chaque nombre obtenu en eectuant le calcul :
m m
e
mod n
o (n, e) est la cl publique de Bob.
Bob reoit donc des nombres quil dcode en faisant le calcul :
m m
d
mod n
On voit quil a besoin du couple (n, d) quil est le seul connatre. Le thorme RSA nous assure quil
retrouvera bien le message de dpart m car il calcule m
d
mod n, cest--dire m
ed
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 lauthentication de lexpditeur. Avez-vous une ide de la mthode employer ?
5. ce jour, il est conseill de les choisir avec plus de 200 chires !
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 permettra
de mieux situer les mathmaticiens que nous rencontrons travers le cours et de conrmer votre intuition
que 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 un
environnement scientique exceptionnel. Son oeuvre est considrable. Euler intervint dans les trois do-
maines fondamentaux de la science de son poque : lastronomie (orbites plantaires, trajectoires des
comtes), les sciences physiques (champs magntiques, hydrodynamique, optique, nature ondulatoire de
la lumire,...), les mathmatiques, o il met au premier plan le concept de fonction. On lui doit aussi la
trs 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 en
raison dune cataracte. Il fut donc pendant 12 ans totalement aveugle. Cela obligeait ce mathmaticien trs
prolixe, 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 ls 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 les
injonctions 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 fonctions
en sommes de sries trigonomtriques (les clbres sries de Fourier) et particulirement lunicit de
cette dcomposition. An de rsoudre compltement ce dicile problme, il est amen introduire et
tudier des ensembles dits exceptionnels. Cela le conduit dnir en 1872 trs prcisment ce quest un
nombre rel, comme limite dune suite de nombres rationnels ; paralllement, son ami Dedekind donne
la mme anne une autre dnition de la droite des rels, partir des coupures. Cantor et Dedekind
constatent cette occasion quil y a beaucoup plus de rels que de rationnels, mais il ny a pas jusque-l
de dnition mathmatique ce "beaucoup plus".
En 1874, dans le prestigieux Journal de Crelle, Cantor donne une dnition du nombre dlments
51
52 Mais qui sont ces gens ?
dun ensemble inni qui prolonge naturellement celle du cardinal dun ensemble ni. 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 de
nombres rationnels. Cette hirarchie dans les ensembles innis conduit progressivement Cantor dnir
des nouveaux nombres, les ordinaux transnis, et dnir 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 attaquer
personnellement Cantor, bloquant ses publications dans le Journal de Crelle, et allant mme jusqu tenter
de bloquer sa carrire. Malgr cela, Cantor obtient un poste de professeur temps plein luniversit de
Halle en 1879.
Vient lanne 1884, et la premire crise de dpression de Cantor. Celui-ci perd alors la force daronter
ses opposants, et na plus la conance dentreprendre de nouvelles recherches. Il sintresse alors lhis-
toire, la littrature anglaise, intervenant notamment dans une crise contemporaine autour des pices de
Shakespeare. En 1899, il obtient un poste administratif consacr des tches routinires qui lui permet
de renoncer son enseignement. Peu peu, ses crises se font de plus en plus frquentes et longues, et il
passe une large partie de son temps soigner sa schizophrnie dans des maisons de repos. Il dcde le 6
juin 1918 Halle.
Les travaux de Cantor ont eu beaucoup dinuence au XX s. On citera dabord, en 1903, un paradoxe
soulev par Russell dans la thorie nave des ensembles : si A est lensemble de tous les ensembles qui
ne sont pas lments deux-mmes, A est-il contenu dans A? Les logiciens surmonteront cette dicult
conceptuelle, sans rien changer des conclusions de Cantor. Citons aussi le problme de lhypothse du
continu. Un des derniers axes de recherche de Cantor tait destimer le nombre dlments de la droite
relle. 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 conrmer ou inrmer lhypothse du continu furent
vains, et pour cause : en 1963, le logicien amricain Cohen prouva que, dans une thorie standard des
ensembles, lhypothse du continu est indcidable. On peut trs bien supposer quelle est vraie ou quelle
est fausse sans obtenir de contradiction dans la thorie.
Boole, George (18151864) Issu dune famille pauvre, George Boole na pas les moyens nanciers
daller luniversit. Ses capacits intellectuelles sont cependant remarquables ; seul (ou presque), il a
appris le latin, lallemand, le franais et litalien. Oblig de travailler pour soutenir sa famille, il devient
enseignant 16 ans.
Quatre ans plus tard, il fonde et dirige sa propre cole. Cest ce moment que le jeune autodidacte
se plonge dans ltude des mathmatiques auxquelles son pre lavait initi ds lenfance. Bnciant des
moyens de lInstitut de mcanique de sa ville, il se confronte aux uvres dIsaac Newton, Pierre-Simon
Laplace et Joseph-Louis Lagrange. Mais trs vite, il commence ses propres recherches. En 1839, il publie
ainsi sa premire tude dans le Cambridge Mathematical Journal. Cette publication et lappui quil obtient
du cercle des algbristes de Cambridge lui permettent de simposer petit petit comme une personnalit
importante du monde des mathmatiques. En 1844, aprs la publication dun mmoire danalyse dans les
Philosophical 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 mission
cartographique qui baptisa le mont Everest.
Cest le dbut dune srie de travaux posant les bases de ce quon nommera plus tard lalgbre de
Boole. 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 dveloppe
une nouvelle forme de logique, la fois symbolique et mathmatique. Le but : traduire des ides et des
concepts 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 dnie
par 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 aussi
divers que les systmes informatiques, la thorie des probabilits, les circuits lectriques et tlphoniques,
etc. grce des scientiques 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 College
de Cork, en Irlande. Et en 1857, il est nomm membre de la Royal Society. Il sintresse ensuite aux
quations direntielles travers deux traits qui auront une inuence certaine : Treatise on Dierential
Equations (1859) et Treatise on the Calculus of Finite Dierences (1860). George Boole meurt dune
pneumonie le 8 dcembre 1864. Il avait pris froid aprs stre rendu au Collge. Croyant au principe
danalogie, Mary lavait alit et asperg deau pour le gurir.
Hasse, Helmut (18981979) Helmut Hasse est un mathmaticien allemand n le 25 aot 1898 Kassel
et mort le 26 dcembre 1979 Ahrensburg.
Il fut un des plus grands algbristes et thoricien des nombres de son temps. En 1925 il devint directeur
de linstitut Mathmatique de Halle puis en 1934 il travailla Gttingen. Sa carrire fut contrarie par
lpisode 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 dnissant une
relation dordre, ainsi que le thorme de la norme de Hasse nous dit que si L/K est une extension cyclique
des corps de nombres, alors, si un lment dirent de zro de K est une norme locale partout, alors il
est 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 le
plus grand enseignant de mathmatiques de lhistoire. Tout juste pense-t-on quil tudia lcole des
successeurs de Platon Athnes, avant de stablir Alexandrie, sous linvitation de Ptolme I. Mais
comme ces suppositions reposent sur des crits de Proclus qui datent de 9 sicles aprs Euclide, on conoit
quelles sont peu ables !
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 est
le rapport exact entre Euclide et les connaissances quil expose. Il semble bien quaucun des rsultats
des Elments ne soit d Euclide, et que son oeuvre consiste en une remise plat de direntes notions
exhibes par des mathmaticiens divers. Au juste, personne ne peut armer avec certitude si Euclide
tait un historien des sciences, chef dune cole, et sil crivit ses ouvrages pour son enseignement. Ou
bien sil conait leur rdaction ses lves, qui auraient pu continuer publier sous le nom dEuclide
mme aprs sa mort. On peut aller jusqu supposer quEuclide, la manire dun Nicolas Bourbaki, tait
le prte-nom dun mathmaticien polycphal : plusieurs mathmaticiens crivant un mme trait sous un
pseudonyme.
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 sont
consacrs la gomtrie plane. Euclide initie alors la mthode axiomatique en construisant la gomtrie
dans le plan laide daxiomes et de postulats. Plus clairement, Euclide dmontre les thormes de
gomtrie plane partir de propositions quil pose comme vraies (du type : deux quantits gales une
mme troisime sont gale entre elles). Dans un langage mathmatique moderne, ces demandes seraient
des dnitions 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 longtemps
pos problme. Il arme que, par un point extrieur une droite, on peut mener une parallle cette
droite, et une seule. Jusquau XIX s., certains ont cru que ce postulat tait en trop, ie que ctait un
thorme que lon pouvait dduire des autres axiomes et postulats. Mais les travaux de Gauss, Riemann
et 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 passe
une innit de droites parallles cette droite.
Bachet de Mziriac, Claude-Gaspard (15811638) Claude Gaspard Bachet de Mziriac est n le 9
octobre 1581 Bourg-en-Bresse. Il est issu dune vieille famille noble (son grand-pre tait conseiller
dHenri II, son pre juriste auprs du duc de Savoie). Orphelin 6 ans, il est duqu chez les Jsuites en
Italie o il est rput pour tre grand lecteur. De retour en France, il rsidera quasiment en permanence
tout prs de Bourg en Bresse. Sa fortune assure par sa famille, il peut se consacrer ltude des lettres
et 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, il
traduit de nombreux ouvrages classiques. Pour ce qui nous concerne, il est lauteur en 1612 dun livre
intitul Problmes plaisants et dlectables qui se font par les nombres, qui est un recueil de rcrations
mathmatiques parmi lesquelles on trouve : le problme des maris jaloux : 3 couples doivent traverser une
rivire, ils ont une seule barque leur disposition, qui ne peut transporter que 2 personnes. Les maris
sont 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 de
magie avec les nombres.
Bachet publia en 1621 une traduction latine, avec commentaires, de lArithmtique de Diophante. Cest
ainsi que Fermat prit connaissance des travaux du mathmaticien grec, et cest en marge dun exemplaire
de la traduction de Bachet quil inscrivit sa fameuse note dans la marge : pour n>2, lquation en nombres
entiers a
n
+ b
n
= c
n
na pas de solutions autre que la solution nulle. Les apports personnels de Bachet
sont peu nombreux, et aussi oublis : ainsi, il semble quil soit le premier avoir conjectur que tout
nombre est somme de 4 carrs, conjecture souvent attribue Waring, et dmontre pour la premire fois
par Lagrange. De mme, il est le premier crire lidentit dite de Bzout (2 entiers a et b sont premiers
entre eux si, et seulement si, il existe des entiers u et v avec au+bv=1) et donner une mthode de
rsolution algorithmique de celle-ci.
Claude Bachet soura sa vie durant dune sant fragile, marque par les rhumatismes et les crises de
goutte. Ainsi, lu membre de lAcadmie Franaise ds sa fondation en 1634, il ne peut se dplacer Paris
pour prononcer son discours inaugural. Il dcde le 26 fvrier 1638.
Gauss, Johann Carl Friedrich (17771855) Carl Friedrich Gauss, n le 30 avril 1777 Brunswick, est
considr par ses pairs comme le prince des mathmaticiens. Il est la fois le dernier des classiques, et
le premier des modernes, cest--dire quil a rsolu les problmes les plus classiques avec les mthodes les
plus modernes. Par exemple, il dmontra comment partager une tarte en 17 parts gales laide des seuls
rgle et compas, ce qui tait un problme ouvert depuis les grecs. Mieux, il dmontra pour quels nombres
ce 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 le
premier dmontrer la loi de rciprocit quadratique, ce que ni Euler, ni Legendre navaient russi. Au
cours de sa vie, il en donnera huit preuves ! ! ! Parmi ses autres prouesses, on peut citer la dmonstration
du thorme fondamental de lalgbre, dans sa thse de doctorat en 1799, linvention de la thorie des
congruences...
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 pre
de lAlgbre, est un mathmaticien grec dont on ignore tout, ou presque, de la vie. On pense quil vivait
vers le 3 s. aprs J.C., mais on ne sait donner de dates plus prcises. Son oeuvre la plus clbre est un
trait de 13 livres, les Arithmtiques, dont on ne connaissait que 6 volumes jusque rcemment. Quatre
autres 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 utilisation
dun symbolisme dans lcriture mathmatique. Il est linventeur du Plethos, qui dsigne linconnue du
problme. Malgr cela, Diophante travaille toujours sur des exemples numriques, si bien quil ne donne
souvent quune seule solution possible un problme, et sans mettre forcment en exergue une mthode
gnrale de rsolution. Tous ces progrs ont longtemps t oublis dans le monde occidental, mais heu-
reusement il furent prservs par les Arabes. Ce nest qu la Renaissance que lon travaille raliser une
traduction latine, la plus fameuse tant celle acheve en 1621 par Bachet de Mzirac.
Diophante sintresse notamment aux problmes suivants : rsolution dquations quadratiques (du
type ax
2
= bx + c). dtermination de valeurs faisant de 2 expressions linaires des carrs (ex : trouver x
tel que 10x+9 et 5x+4 sont tous deux des carrs). dcomposition dun nombre en somme de 2 carrs. Il
semble que Diophante sache dexprience que les entiers de la forme 4n+1 scrivent comme la somme
de 2 carrs. partage dun carr en 2 carrs : il explique notamment comment partager 16 = 4
2
en somme
de 2 carrs : (16/5)
2
+ (12/5)
2
. Cest en marge de ce problme que Fermat inscrit sur son exemplaire
des Arithmtiques sa fameuse note : "il est impossible de partager un cube en 2 cubes, un bicarr en 2
bicarrs, et plus gnralement une puissance quelconque sauf le carr, en 2 puissance de mme exposant.
Il faudra attendre 1995 pour avoir une dmonstration de ce rsultat.
Signalons pour terminer une lgende au sujet de Diophante : une anthologie grecque (datant de 500
aprs J-C) rapporte quil tait crit sur sa tombe lpitaphe suivante (la traduction en alexandrins est
dEmile Fourrey dans ses Rcrations mathmatiques) :
Passant sous ce tombeau repose Diophante.
Ces quelques vers tracs par une main savante
Vont te faire connatre quel ge il est mort.
Des jours assez nombreux que lui compta le sort,
Le sixime marqua le temps de son enfance ;
Le douzime fut pris par son adolescence.
Des septs parts de sa vie, une encore scoula,
Puis stant mari, sa femme lui donna
Cinq ans aprs un ls, qui, du destin svre,
Reut de jours hlas ! deux fois moins que son pre.
De quatre ans, dans les pleurs, celui-ci survcut.
Dis, si tu sais compter, quel ge il mourut.
56 Mais qui sont ces gens ?
Bibliographie
[1] J-P. Ramis et A. Warusfel, Mathmatiques tout-en-un pour la licence, niveau L1, Dunod, 2006
[2] M. Marchand, Outils mathmatiques pour linformaticien, De Boeck, 2005 (2
e
dition)
[3] J. Vlu, Mthodes mathmatiques pour linformatique, Dunod, 2005 (4
e
dition)
57