Livre Mooc Exo7
Livre Mooc Exo7
I Le cours du MOOC 3
1 Arithmétique 4
1 Division euclidienne et pgcd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 Théorème de Bézout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3 Nombres premiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4 Congruences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2 Cryptographie 17
1 Le chiffrement de César . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2 Le chiffrement de Vigenère . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3 La machine Enigma et les clés secrètes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4 La cryptographie à clé publique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
5 L’arithmétique pour RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
6 Le chiffrement RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3 Algorithmes et mathématiques 43
1 Premiers pas avec . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2 Écriture des entiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3 Calculs de sinus, cosinus, tangente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4 Les réels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5 Arithmétique – Algorithmes récursifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
6 Polynômes – Complexité d’un algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5 Ensembles et applications 79
1 Ensembles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
2 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
3 Injection, surjection, bijection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
4 Ensembles finis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
5 Relation d’équivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
1
–
–
–
2
Première partie
Le cours du MOOC
3
Exo7
■
■
■
■
Z
Préambule
Une motivation : l’arithmétique est au cœur du cryptage des communication. Pour crypter un message
on commence par le transformer en un –ou plusieurs– nombres. Le processus de codage et décodage fait
appel à plusieurs notions de ce chapitre :
– On choisit deux nombres premiers p et q que l’on garde secrets et on pose n p × q. Le principe
étant que même connaissant n il est très difficile de retrouver p et q (qui sont des nombres ayant des
centaines de chiffres).
– La clé secrète et la clé publique se calculent à l’aide de l’algorithme d’Euclide et des coefficients
de Bézout.
– Les calculs de cryptage se feront modulo n.
– Le décodage fonctionne grâce à une variante du petit théorème de Fermat.
4
1 Division euclidienne et pgcd
a bq
a bq + r et 0…rb
6789 34 × 199 + 23
On a bien 0 … 23 34 (sinon c’est que l’on n’a pas été assez loin dans les calculs).
6789 34
34 dividende diviseur
338
306
199 quotient
329
306 reste
23
}
Démonstration. Existence. On peut supposer a 0 pour simplifier. Soit N n N | bn … a . C’est un
ensemble non vide car n 0 N . De plus pour n N , on a n … a. Il y a donc un nombre fini d’éléments
dans N , notons q max N le plus grand élément.
Alors qb … a car q N , et (q + 1)b a car q + 1 N donc
qb … a (q + 1)b qb + b.
5
1.2 pgcd de deux entiers
Dénition 2. Soient a, b Z deux entiers, non tous les deux nuls. Le plus grand entier qui divise à la
fois a et b s’appelle le plus grand diviseur commun de a, b et se note pgcd(a, b).
Exemple 3. – pgcd(21, 14) 7, pgcd(12, 32) 4, pgcd(21, 26) 1.
– pgcd(a, ka) a, pour tout k Z et a 0.
– Cas particuliers. Pour tout a 0 : pgcd(a, 0) a et pgcd(a, 1) 1.
En fait on a même pgcd(a, b) pgcd(b, a − qb) pour tout q Z. Mais pour optimiser l’algorithme d’Euclide
on applique le lemme avec q le quotient.
Démonstration. Nous allons montrer que les diviseurs de a et de b sont exactement les mêmes que les
diviseurs de b et r. Cela impliquera le résultat car les plus grands diviseurs seront bien sûr les mêmes.
– Soit d un diviseur de a et de b. Alors d divise b donc aussi bq, en plus d divise a donc d divise
bq − a r.
– Soit d un diviseur de b et de r. Alors d divise aussi bq + r a.
Algorithme d’Euclide.
On souhaite calculer le pgcd de a, b N∗ . On peut supposer a b. On calcule des divisions euclidiennes
successives. Le pgcd sera le dernier reste non nul.
– division de a par b, a bq 1 + r 1 . Par le lemme 1, pgcd(a, b) pgcd(b, r 1 ) et si r 1 0 alors pgcd(a, b) b
sinon on continue :
– b r 1 q 2 + r 2 , pgcd(a, b) pgcd(b, r 1 ) pgcd(r 1 , r 2 ),
– r 1 r 2 q 3 + r 3 , pgcd(a, b) pgcd(r 2 , r 3 ),
– ...
– r k−2 r k−1 q k + r k , pgcd(a, b) pgcd(r k−1 , r k ),
– r k−1 r k q k + 0. pgcd(a, b) pgcd(r k , 0) r k .
Comme à chaque étape le reste est plus petit que le quotient on sait que 0 … r i+1 r i . Ainsi l’algo-
rithme se termine car nous sommes sûr d’obtenir un reste nul, les restes formant une suite décroissante
d’entiers positifs ou nuls : b r 1 r 2 . . . 0
Exemple 4. Calculons le pgcd de a 600 et b 124.
600 124 × 4 + 104
124 104 × 1 + 20
104 20 × 5 + 4
20 4 × 5 + 0
Ainsi pgcd(600, 124) 4.
6
1.4 Nombres premiers entre eux
Dénition 3. Deux entiers a, b sont premiers entre eux si pgcd(a, b) 1.
Exemple 6. Pour tout a Z, a et a + 1 sont premiers entre eux. En effet soit d un diviseur commun à
a et à a + 1. Alors d divise aussi a + 1 − a. Donc d divise 1 mais alors d −1 ou d +1. Le plus grand
diviseur de a et a + 1 est donc 1. Et donc pgcd(a, a + 1) 1.
Si deux entiers ne sont pas premiers entre eux, on peut s’y ramener en divisant par leur pgcd :
Exemple 7. Pour deux entiers quelconques a, b Z, notons d pgcd(a, b). La décomposition suivante
est souvent utile :
{
a a′ d
avec a′ , b′ Z et pgcd(a′ , b′ ) 1
b b′ d
1.5 Mini-exercices
1. Écrire la division euclidienne de 111 111 par 20xx, où 20xx est l’année en cours.
2. Montrer qu’un diviseur positif de 10 008 et de 10 014 appartient nécessairement à {1, 2, 3, 6}.
3. Calculer pgcd(560, 133), pgcd(12 121, 789), pgcd(99 999, 1110).
4. Trouver tous les entiers 1 … a … 50 tels que a et 50 soient premiers entre eux. Même question avec
52.
2 Théorème de Bézout
au + bv pgcd(a, b)
La preuve découle de l’algorithme d’Euclide. Les entiers u, v ne sont pas uniques. Les entiers u, v sont
des coefficients de Bézout. Ils s’obtiennent en «remontant» l’algorithme d’Euclide.
Exemple 8. Calculons les coefficients de Bézout pour a 600 et b 124. Nous reprenons les calculs
effectués pour trouver pgcd(600, 124) 4. La partie gauche est l’algorithme d’Euclide. La partie droite
s’obtient de bas en haut. On exprime le pgcd à l’aide de la dernière ligne où le reste est non nul. Puis on
remplace le reste de la ligne précédente, et ainsi de suite jusqu’à arriver à la première ligne.
600 124 × 4 + 104 4 124 × (−5) + (600 − 124 × 4) × 6 600 × 6 + 124 × (−29)
124 104 × 1 + 20 4 104 − (124 − 104 × 1) × 5 124 × (−5) + 104 × 6
104 20 × 5 + 4 4 104 − 20 × 5
20 4 × 5 + 0
Remarque. – Soignez vos calculs et leur présentation. C’est un algorithme : vous devez aboutir au bon
résultat ! Dans la partie droite, il faut à chaque ligne bien la reformater. Par exemple 104 − (124 −
104 × 1) × 5 se réécrit en 124 × (−5) + 104 × 6 afin de pouvoir remplacer ensuite 104.
– N’oubliez de vérifier vos calculs ! C’est rapide et vous serez certain que vos calculs sont exacts. Ici on
vérifie à la fin que 600 × 6 + 124 × (−29) 4.
7
Exemple 9. Calculons les coefficients de Bézout correspondant à pgcd(9945, 3003) 39.
Exemple : 4|16 et 4|24 donc 4 doit divisé pgcd(16, 24) qui effectivement vaut 8.
Démonstration. Comme d |au et d | bv donc d |au + bv. Par le théorème de Bézout d | pgcd(a, b).
Corollaire 2. Soient a, b deux entiers. a, b sont premiers entre eux si et seulement si il existe u, v Z
tels que
au + bv 1
Remarque. Si on trouve deux entiers u′ , v′ tels que au′ + bv′ d, cela n’implique pas que d pgcd(a, b).
On sait seulement alors que pgcd(a, b)| d. Par exemple a 12, b 8 ; 12 × 1 + 8 × 3 36 et pgcd(a, b) 4.
Si a| bc et pgcd(a, b) 1 alors a| c
2.3 Équations ax + b y c
Proposition 1.
Considérons l’équation
ax + b y c (E)
où a, b, c Z.
1. L’équation (E) possède des solutions (x, y) Z2 si et seulement si pgcd(a, b)| c.
2. Si pgcd(a, b)| c alors il existe même une infinité de solutions entières et elles sont exactement les
(x, y) (x0 + k, y0 + k) avec x0 , y0 , , Z fixés et k parcourant Z.
Le premier point est une conséquence du théorème de Bézout. Nous allons voir sur un exemple comment
prouver le second point et calculer explicitement les solutions. Il est bon de refaire toutes les étapes de
la démonstration à chaque fois.
8
– Première étape. Y a-t’il de solutions ? L’algorithme d’Euclide. On effectue l’algorithme d’Eu-
clide pour calculer le pgcd de a 161 et b 368.
368 161 × 2 + 46
161 46 × 3 + 23
46 23 × 2 + 0
Donc pgcd(368, 161) 23. Comme 115 5 × 23 alors pgcd(368, 161)|115. Par le théorème de Bézout,
l’équation (E) admet des solutions entières.
– Deuxième étape. Trouver une solution particulière : la remontée de l’algorithme d’Euclide.
On effectue la remontée de l’algorithme d’Euclide pour calculer les coefficients de Bézout.
On trouve donc 161 × 7 + 368 × (−3) 23. Comme 115 5 × 23 en multipliant par 5 on obtient :
(on n’a aucun intérêt à remplacer x0 et y0 par leurs valeurs). La différence de ces deux égalités conduit
à
161 × (x − x0 ) + 368 × (y − y0 ) 0
⇒ 23 × 7 × (x − x0 ) + 23 × 16 × (y − y0 ) 0
⇒ 7(x − x0 ) −16(y − y0 ) (∗ )
Nous avons simplifier par 23 qui est le pgcd de 161 et 368. (Attention, n’oubliez surtout pas cette
simplification, sinon la suite du raisonnement serait fausse.)
Ainsi 7|16(y − y0 ), or pgcd(7, 16) 1 donc par le lemme de Gauss 7| y − y0 . Il existe donc k Z tel que
y − y0 7 × k. Repartant de l’équation (∗) : 7(x − x0 ) −16(y − y0 ). On obtient maintenant 7(x − x0 )
−16 × 7 × k. D’où x − x0 −16k. (C’est le même k pour x et pour y.) Nous avons donc (x, y) (x0 −
16k, y0 + 7k). Il n’est pas dur de voir que tout couple de cette forme est solution de l’équation (E). Il
reste donc juste à substituer (x0 , y0 ) par sa valeur et nous obtenons :
Les solutions entières de 161x + 368y 115 sont les (x, y) (35 − 16k, −15 + 7k), k parcourant Z.
Pour se rassurer, prenez une valeur de k au hasard et vérifiez que vous obtenez bien une solution de
l’équation.
2.4 ppcm
Dénition 4. Le ppcm(a, b) (plus petit multiple commun) est le plus petit entier 0 divisible par a
et par b.
Proposition 2.
Si a, b sont des entiers (non tous les deux nuls) alors
9
pgcd(a, b) × ppcm(a, b) |ab|
|ab|
Démonstration. Posons d pgcd(a, b) et m pgcd(a,b) . Pour simplifier on suppose a 0 et b 0. On écrit
2 ′ ′
a da et b db . Alors ab d a b et donc m da b . Ainsi m ab′ a′ b est un multiple de a et de b.
′ ′ ′ ′
Il reste à montrer que c’est le plus petit multiple. Si n est un autre multiple de a et de b alors n ka ` b
donc kda′ ` db′ et ka′ ` b′ . Or pgcd(a′ , b′ ) 1 et a′ |` b′ donc a′ |`. Donc a′ b|` b et ainsi m a′ b|` b
n.
Voici un autre résultat concernant le ppcm qui se démontre en utilisant la décomposition en facteurs
premiers :
Proposition 3.
Si a| c et b| c alors ppcm(a, b)| c.
Il serait faux de penser que ab| c. Par exemple 6|36, 9|36 mais 6 × 9 ne divise pas 36. Par contre
ppcm(6, 9) 18 divise bien 36.
2.5 Mini-exercices
1. Calculer les coefficients de Bézout correspondant à pgcd(560, 133), pgcd(12 121, 789).
2. Montrer à l’aide d’un corollaire du théorème de Bézout que pgcd(a, a + 1) 1.
3. Résoudre les équations : 407x + 129y 1 ; 720x + 54 y 6 ; 216x + 92 y 8.
4. Trouver les couples (a, b) vérifiant pgcd(a, b) 12 et ppcm(a, b) 360.
3 Nombres premiers
Les nombres premiers sont –en quelque sorte– les briques élémentaires des entiers : tout entier s’écrit
comme produit de nombres premiers.
Proposition 4.
Il existe une infinité de nombres premiers.
Démonstration. Par l’absurde, supposons qu’il n’y ait qu’un nombre fini de nombres premiers que l’on
note p 1 2, p 2 3, p 3 ,. . . , p n . Considérons l’entier N p 1 × p 2 ×· · ·× p n + 1. Soit p un diviseur premier de
N (un tel p existe par le lemme précédent), alors d’une part p est l’un des entiers p i donc p| p 1 ×· · ·× p n ,
d’autre part p| N donc p divise la différence N − p 1 ×· · ·× p n 1. Cela implique que p 1, ce qui contredit
que p soit un nombre premier.
Cette contradiction nous permet de conclure qu’il existe une infinité de nombres premiers.
10
3.2 Eratosthène et Euclide
Comment trouver les nombres premiers ? Le crible d’Eratosthène permet de trouver les premiers
nombres premiers. Pour cela on écrit les premiers entiers : pour notre exemple de 2 à 25.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
Rappelons-nous qu’un diviseur positif d’un entier n est inférieur ou égal à n. Donc 2 ne peut avoir
comme diviseurs que 1 et 2 et est donc premier. On entoure 2. Ensuite on raye (ici en grisé) tous les
multiples suivants de 2 qui ne seront donc pas premiers (car divisible par 2) :
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
Le premier nombre restant de la liste est 3 et est nécessairement premier : il n’est pas divisible par un
diviseur plus petit (sinon il serait rayé). On entoure 3 et on raye tous les multiples de 3 (6, 9, 12, . . . ).
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
Le premier nombre restant est 5 et est donc premier. On raye les multiples de 5.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
7 est donc premier, on raye les multiples de 7 (ici pas de nouveaux nombres à barrer). Ainsi de suite :
11, 13, 17, 19, 23 sont premiers.
2 3 4 5 6 7 8 9 10
11 12
13 14 15 16
17 18
19 20 21 22 23 24 25
p
Remarque. Si un nombre n n’est pas premier alors un de ses facteurs est … n. En effet si n a × b
p p
avec a, b 2 alors a … n ou b … n (réfléchissez par l’absurde !). Par exemple pour tester si un nombre
… 100 est premier il suffit de tester les diviseurs … 10. Et comme il suffit de tester les diviseurs premiers,
il suffit en fait de tester la divisibilité par 2, 3, 5 et 7. Exemple : 89 n’est pas divisible par 2, 3, 5, 7 et est
donc un nombre premier.
Démonstration. Si p ne divise pas a alors p et a sont premiers entre eux (en effet les diviseurs de p
sont 1 et p, mais seul 1 divise aussi a, donc pgcd(a, p) 1). Ainsi par le lemme de Gauss p| b.
p
Exemple 11. Si p est un nombre premier, p n’est pas un nombre rationnel.
p 2
La preuve se fait par l’absurde : écrivons p ab avec a Z, b N∗ et pgcd(a, b) 1. Alors p ab2 donc
pb2 a2 . Ainsi p|a2 donc par le lemme d’Euclide p|a. On peut alors écrire a pa′ avec a′ un entier. De
l’équation pb2 a2 on tire alors b2 pa′2 . Ainsi p| b2 et donc p| b. Maintenant p|a et p| b donc a et b ne
p
sont pas premiers entre eux. Ce qui contredit pgcd(a, b) 1. Conclusion p n’est pas rationnel.
Remarque. La principale raison pour laquelle on choisit de dire que 1 n’est pas un nombre premier,
c’est que sinon il n’y aurait plus unicité de la décomposition : 24 23 × 3 1 × 23 × 3 12 × 23 × 3 · · ·
11
Démonstration. Existence. Nous allons démontrer l’existence de la décomposition par une récurrence
sur n.
L’entier n 2 est déjà décomposé. Soit n 3, supposons que tout entier n admette une décomposition
en facteurs premiers. Notons p 1 le plus petit nombre premier divisant n (voir le lemme 2). Si n est
un nombre premier alors n p 1 et c’est fini. Sinon on définit l’entier n′ pn1 n et on applique notre
hypothèse de récurrence à n′ qui admet une décomposition en facteurs premiers. Alors n p 1 × n′ admet
aussi une décomposition.
Unicité. Nous allons démontrer qu’une telle décomposition est unique en effectuant cette fois une récur-
rence sur la somme des exposants σ ri1 i .
Si σ 1 cela signifie n p 1 qui est bien l’unique écriture possible.
Soit σ 2. On suppose que les entiers dont la somme des exposants est σ ont une unique décomposi-
tion. Soit n un entier dont la somme des exposants vaut σ. Écrivons le avec deux décompositions :
n p1 1 × p2 2 × · · · × p r r q1 1 × q2 2 × · · · × q s s .
(On a p 1 p 2 · · · et q 1 q 2 · · · .)
Si p 1 q 1 alors p 1 q j pour tous les j 1, . . . , s. Ainsi p 1 divise p 1 1 × p 2 2 × · · · × p r r n mais ne divise
pas q 1 1 × q 2 2 × · · · × q s s n. Ce qui est absurde. Donc p 1 q 1 .
Si p 1 q 1 un même raisonnement conduit aussi à une contradiction. On conclut que p 1 q 1 . On pose
alors
n −1 −1
n′
p1 1 × p2 2 × · · · × p r r q1 1 × q2 2 × · · · × q s s
p1
L’hypothèse de récurrence qui s’applique à n′ implique que ces deux décompositions sont les mêmes.
Ainsi r s et p i q i , i i , i 1, . . . , r.
Exemple 12.
504 23 × 32 × 7, 300 22 × 3 × 52 .
Pour calculer le pgcd on réécrit ces décompositions :
504 23 × 32 × 50 × 71 , 300 22 × 31 × 52 × 70 .
Le pgcd est le nombre obtenu en prenant le plus petit exposant de chaque facteur premier :
3.4 Mini-exercices
1. Montrer que n! + 1 n’est divisible par aucun des entiers 1, . . . , n. Est-ce toujours un nombre pre-
mier ?
2. Trouver tous les nombres premiers … 103.
3. Décomposer a 2 340 et b 15 288 en facteurs premiers. Calculer leur pgcd et leur ppcm.
4. Décomposer 48 400 en produit de facteurs premiers. Combien 48 400 admet-il de diviseurs ?
5. Soient a, b 0. À l’aide de la décomposition en facteurs premiers, reprouver la formule pgcd(a, b) ×
ppcm(a, b) a × b.
12
4 Congruences
4.1 Dénition
Dénition 6. Soit n 2 un entier. On dit que a est congru à b modulo n, si n divise b − a. On note
alors
a ≡ b (mod n).
a ≡ b (mod n) ⇐⇒ ∃k Z a b + kn.
N est divisible par 9 si et seulement si la somme de ses chiffres est divisible par 9.
Pour prouver cela nous utilisons les congruences. Remarquons d’abord que 9| N équivaut à N ≡ 0
(mod 9) et notons aussi que 10 ≡ 1 (mod 9), 102 ≡ 1 (mod 9), 103 ≡ 1 (mod 9),...
Nous allons donc calculer N modulo 9. Écrivons N en base 10 : N a k · · · a 2 a 1 a 0 (a 0 est le chiffre des
unités, a 1 celui des dizaines,...) alors N 10k a k + · · · + 102 a 2 + 101 a 1 + a 0 . Donc
Donc N est congru à la somme de ses chiffres modulo 9. Ainsi N ≡ 0 (mod 9) si et seulement si la somme
des chiffres vaut 0 modulo 9.
13
Voyons cela sur un exemple : N 488 889. Ici a 0 9 est le chiffre des unités, a 1 8 celui des dizaines,...
Cette écriture décimale signifie N 4 · 105 + 8 · 104 + 8 · 103 + 8 · 102 + 8 · 10 + 9.
Ainsi nous savons que 488 889 est divisible par 9 sans avoir effectué de division euclidienne.
Remarque. Pour trouver un «bon» représentant de a (mod n) on peut aussi faire la division euclidienne
de a par n : a bn + r alors a ≡ r (mod n) et 0 … r n.
Exemple 15. Les calculs bien menés avec les congruences sont souvent très rapides. Par exemple on
souhaite calculer 221 (mod 37) (plus exactement on souhaite trouver 0 … r 37 tel que 221 ≡ r (mod 37)).
Plusieurs méthodes :
1. On calcule 221 , puis on fait la division euclidienne de 221 par 37, le reste est notre résultat. C’est
laborieux !
2. On calcule successivement les 2k modulo 37 : 21 ≡ 2 (mod 37), 22 ≡ 4 (mod 37), 23 ≡ 8 (mod 37),
24 ≡ 16 (mod 37), 25 ≡ 32 (mod 37). Ensuite on n’oublie pas d’utiliser les congruences : 26 ≡ 64 ≡ 27
(mod 37). 27 ≡ 2 · 26 ≡ 2 · 27 ≡ 54 ≡ 17 (mod 37) et ainsi de suite en utilisant le calcul précédent à
chaque étape. C’est assez efficace et on peut raffiner : par exemple on trouve 28 ≡ 34 (mod 37)
mais donc aussi 28 ≡ −3 (mod 37) et donc 29 ≡ 2 · 28 ≡ 2 · (−3) ≡ −6 ≡ 31 (mod 37),...
3. Il existe une méthode encore plus efficace : on écrit l’exposant 21 en base 2 : 21 24 + 22 + 20
16 + 4 + 1. Alors 221 216 · 24 · 21 . Et il est facile de calculer successivement chacun de ces termes
car les exposants sont des puissances de 2. Ainsi 28 ≡ (24 )2 ≡ 162 ≡ 256 ≡ 34 ≡ −3 (mod 37) et
2
216 ≡ 28 ≡ (−3)2 ≡ 9 (mod 37). Nous obtenons 221 ≡ 216 · 24 · 21 ≡ 9 × 16 × 2 ≡ 288 ≡ 29 (mod 37).
3x − 8k 2.
Pour le calcul du pgcd et d’une solution particulière nous utilisons normalement l’algorithme d’Euclide
et sa remontée. Ici il est facile de trouver une solution particulière (x0 6, k 0 2) à la main.
On termine comme pour les équations de la section 2.3. Si (x, k) est une solution de 3x − 8k 2 alors
par soustraction on obtient 3(x − x0 ) − 8(k − k 0 ) 0 et on trouve x x0 + 8`, avec ` Z (le terme k ne
nous intéresse pas). Nous avons donc trouvé les x qui sont solutions de 3x − 8k 2, ce qui équivaut à
9x − 24k 6, ce qui équivaut encore à 9x ≡ 6 (mod 24). Les solutions sont de la forme x 6 + 8`. On
préfère les regrouper en 3 classes modulo 24 :
14
Remarque. Expliquons le terme de «classe» utilisé ici. Nous avons considérer ici que l’équation 9x ≡ 6
(mod 24) est une équation d’entiers. On peut aussi considérer que 9, x, 6 sont des classes d’équivalence
modulo 24, et l’on noterait alors 9x 6. On trouverait comme solutions trois classes d’équivalence :
x1 6, x2 14, x3 22.
Démonstration. 1.
Nous avons juste transformé notre équation ax ≡ b (mod n) en une équation ax − kn b étudiée
auparavant (voir section 2.3), seules les notations changent : au + bv c devient ax − kn b.
2. Supposons qu’il existe des solutions. Nous allons noter d pgcd(a, n) et écrire a da′ , n dn′
et b db′ (car par le premier point d | b). L’équation ax − kn b d’inconnues x, k Z est alors
équivalente à l’équation a′ x − kn′ b′ , notée (?). Nous savons résoudre cette équation (voir de
nouveau la proposition 1), si (x0 , k 0 ) est une solution particulière de (?) alors on connaît tous les
(x, k) solutions. En particulier x x0 + ` n′ avec ` Z (les k ne nous intéressent pas ici).
Ainsi les solutions x Z sont de la forme x x0 + ` pgcd(na,n) , ` Z où x0 est une solution particulière
de ax ≡ b (mod n). Et modulo n cela donne bien pgcd(a, n) classes distinctes.
a p ≡ a (mod p)
a p−1 ≡ 1 (mod p)
Lemme 3. p divise kp pour 1 … k … p − 1, c’est-à-dire kp ≡ 0 (mod p).
p!
Démonstration. kp k!( p−k)! donc p! k!(p − k)! kp . Ainsi p| k!(p − k)! kp . Or comme 1 … k … p − 1 alors p
ne divise pas k! (sinon p divise l’un des facteurs de k! mais il sont tous p). De même p ne divise pas
(p − k)!, donc par le lemme d’Euclide p divise kp .
15
– Par le principe de récurrence nous avons démontré le petit théorème de Fermat pour tout a 0. Il
n’est pas dur d’en déduire le cas des a … 0.
Exemple 17. Calculons 143141 (mod 17). Le nombre 17 étant premier on sait par le petit théorème de
Fermat que 1416 ≡ 1 (mod 17). Écrivons la division euclidienne de 3141 par 16 :
3141 16 × 196 + 5.
Alors
196
143141 ≡ 1416×196+5 ≡ 1416×196 × 145 ≡ 1416 × 145 ≡ 1196 × 145 ≡ 145 (mod 17)
Il ne reste plus qu’à calculer 145 modulo 17. Cela peut se faire rapidement : 14 ≡ −3 (mod 17) donc
142 ≡ (−3)2 ≡ 9 (mod 17), 143 ≡ 142 × 14 ≡ 9 × (−3) ≡ −27 ≡ 7 (mod 17), 145 ≡ 142 × 143 ≡ 9 × 7 ≡ 63 ≡ 12
(mod 17). Conclusion : 143141 ≡ 145 ≡ 12 (mod 17).
4.4 Mini-exercices
1. Calculer les restes modulo 10 de 122 + 455, 122 × 455, 122455 . Mêmes calculs modulo 11, puis
modulo 12.
2. Prouver qu’un entier est divisible par 3 si et seulement si la somme de ses chiffres est divisible
par 3.
3. Calculer 310 (mod 23).
4. Calculer 3100 (mod 23).
5. Résoudre les équations 3x ≡ 4 (mod 7), 4x ≡ 14 (mod 30).
Auteurs
Arnaud Bodin
Benjamin Boutin
Pascal Romon
16
Exo7
1 Le chiffrement de César . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.1 César a dit... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.2 Des chiffres et des lettres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.3 Modulo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.4 Chiffrer et déchiffrer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.5 Espace des clés et attaque . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.6 Algorithmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2 Le chiffrement de Vigenère . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.1 Chiffrement mono-alphabétique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2 Le chiffrement de Vigenère . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3 Algorithmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3 La machine Enigma et les clés secrètes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.1 Un secret parfait . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 La machine Enigma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.3 La ronde des chiffres : DES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4 La cryptographie à clé publique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.1 Le principe de Kerckhoffs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.2 Factorisations des entiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.3 Fonctions à sens unique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.4 Chiffrement à clé privée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.5 Chiffrement à clé publique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5 L’arithmétique pour RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
5.1 Le petit théorème de Fermat amélioré . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
5.2 L’algorithme d’Euclide étendu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5.3 Inverse modulo n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5.4 L’exponentiation rapide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
6 Le chiffrement RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
6.1 Calcul de la clé publique et de la clé privée . . . . . . . . . . . . . . . . . . . . . . . . 38
6.2 Chiffrement du message . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
6.3 Déchiffrement du message . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
6.4 Schéma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
6.5 Lemme de déchiffrement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
6.6 Algorithmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
■
■
1 Le chiffrement de César
17
1.1 César a dit...
Jules César a-t-il vraiment prononcé la célèbre phrase :
DOHD MDFWD HVW
ou bien comme le disent deux célèbres Gaulois : « Ils sont fous ces romains ! ».
En fait César, pour ses communications importantes à son armée, cryptait ses messages. Ce que l’on
appelle le chiffrement de César est un décalage des lettres : pour crypter un message, A devient D, B
devient E, C devient F,...
Nous adopterons la convention suivante, en vert c’est la partie du message à laquelle tout le monde a
accès (ou qui pourrait être intercepté), c’est donc le message crypté. Alors qu’en rouge c’est la partie du
message confidentiel, c’est le message en clair.
Pour prendre en compte aussi les dernières lettres de l’alphabet, il est plus judicieux de représenté
l’alphabet sur un anneau. Ce décalage est un décalage circulaire sur les lettres de l’alphabet.
Pour déchiffrer le message de César, il suffit de décaler les lettres dans l’autre sens, D se déchiffre en
A, E en B,...
Et la célèbre phrase de César est :
ALEA JACTA EST
qui traduite du latin donne « Les dés sont jetés ».
18
par
A 7−→ 0 B 7−→ 1 C 7−→ 2 ... Z 7−→ 25
Ainsi "A L E A" devient "0 11 4 0".
Le chiffrement de César est un cas particulier de chiffrement mono-alphabétique, c’est-à-dire un
chiffrement lettre à lettre.
Quel est l’intérêt ? Nous allons voir que le chiffrement de César correspond à une opération mathéma-
tique très simple. Pour cela, rappelons la notion de congruence et l’ensemble Z/26Z.
1.3 Modulo
Soit n 2 un entier fixé.
a ≡ b (mod n).
Pour nous n 26. Ce qui fait que 28 ≡ 2 (mod 26), car 28 − 2 est bien divisible par 26. De même 85
3 × 26 + 7 donc 85 ≡ 7 (mod 26).
On note Z/26Z l’ensemble de tous les éléments de Z modulo 26. Cet ensemble peut par exemple être
représenté par les 26 éléments {0, 1, 2, . . . , 25}. En effet, puisqu’on compte modulo 26 :
0, 1, 2, . . . , 25, puis 26 ≡ 0, 27 ≡ 1, 28 ≡ 2, . . . , 52 ≡ 0, 53 ≡ 1, . . .
Plus généralement Z/nZ contient n éléments. Pour un entier a Z quelconque, son représentant dans
{0, 1, 2, . . . , n − 1} s’obtient comme le reste k de la division euclidienne de a par n : a bn + k. De sorte que
a ≡ k (mod n) et 0 … k n.
19
{
Z/26Z −→ Z/26Z
Dk :
x 7−→ x− k
En effet, si 1 a été chiffré en 4, par la fonction C 3 alors D 3 (4) 4 − 3 1. On retrouve le nombre original.
Mathématiquement, D k est la bijection réciproque de C k , ce qui implique que pour tout x Z/26Z :
D k C k (x) x
En d’autres termes, si x est un nombre, on applique la fonction de chiffrement pour obtenir le nombre
crypté y C k (x) ; ensuite la fonction de déchiffrement fait bien ce que l’on attend d’elle D k (y) x, on
retrouve le nombre original x.
Ck
Z/26Z Z/26Z
Dk
Une autre façon de voir la fonction de déchiffrement est de remarquer que D k (x) C −k (x). Par exemple
C −3 (x) x + (−3) ≡ x + 23 (mod 26).
Voici le principe du chiffrement : Alice veut envoyer des messages secrets à Bruno. Ils se sont d’abord
mis d’accord sur une clé secrète k, par exemple k 11. Alice veut envoyer le message "COUCOU"
à Bruno. Elle transforme "COUCOU" en "2 14 20 2 14 20". Elle applique la fonction de chiffrement
C 11 (x) x + 11 à chacun des nombres : "13 25 5 13 25 5" ce qui correspond au mot crypté "NZFNZF".
Elle transmet le mot crypté à Bruno, qui selon le même principe applique la fonction de déchiffrement
D 11 (x) x − 11.
ALICE BRUNO
Ck Dk
2 14 20 2 14 20 13 25 5 13 25 5 13 25 5 13 25 5 2 14 20 2 14 20
Exemple 18. Un exemple classique est le "rot13" (pour rotation par un décalage de 13) :
C 13 (x) x + 13
et comme −13 ≡ 13 (mod 26) alors D 13 (x) x + 13. La fonction de déchiffrement est la même que la
fonction de chiffrement !
Exemple : déchiffrez le mot "PRFNE".
Notons ici deux points importants pour la suite : tout d’abord nous avons naturellement considéré un
mot comme une succession de lettres, et chaque opération de chiffrement et déchiffrement s’effectue sur
un bloc d’une seule lettre. Ensuite nous avons vu que chiffrer un message est une opération mathéma-
tique (certes sur un ensemble un peu spécial).
20
1.5 Espace des clés et attaque
Combien existe-t-il de possibilités de chiffrement par la méthode de César ? Il y a 26 fonctions C k dif-
férentes, k 0, 1, . . . , 25. Encore une fois, k appartient à Z/26Z, car par exemple les fonctions C 29 et
C 3 sont identiques. Le décalage k s’appelle la clé de chiffrement, c’est l’information nécessaire pour
crypter le message. Il y a donc 26 clés différentes et l’espace des clés est Z/26Z.
Il est clair que ce chiffrement de César est d’une sécurité très faible. Si Alice envoie un message secret
à Bruno et que Chloé intercepte ce message, il sera facile pour Chloé de le décrypter même si elle ne
connaît pas la clé secrète k. L’attaque la plus simple pour Chloé est de tester ce que donne chacune
des 26 combinaisons possibles et de reconnaître parmi ces combinaisons laquelle donne un message
compréhensible.
1.6 Algorithmes
Les ordinateurs ont révolutionné la cryptographie et surtout le décryptage d’un message intercepté.
Nous montrons ici, à l’aide du langage comment programmer et attaquer le chiffrement de
César. Tout d’abord la fonction de chiffrement se programme en une seule ligne :
Ici est un nombre de {0, 1, . . . , 25} et est le décalage. renvoie le reste modulo 26 de la somme
. Pour le décryptage, c’est aussi simple :
Pour chiffrer un mot ou un phrase, il n’y a pas de problèmes théoriques, mais seulement des difficultés
techniques :
– Un mot ou une phrase est une chaîne de caractères, qui en fait se comporte comme une liste. Si
est une chaîne alors est la première lettre, la deuxième lettre... et la boucle
permet de parcourir chacune des lettres.
– Pour transformer une lettre en un nombre, on utilise le code Ascii qui à chaque caractère associe un
nombre, vaut 65, vaut 66... Ainsi renvoie le rang de la lettre
entre 0 et 25 comme nous l’avons fixé dès le départ.
– La transformation inverse se fait par la fonction : renvoie le caractère ,
renvoie ...
– Pour ajouter une lettre à une liste, faites . Enfin pour transformer une liste
de caractères en une chaîne, faites .
Ce qui donne :
21
Pour l’attaque on parcourt l’intégralité de l’espace des clés : k varie de 0 à 25. Noter que pour décrypter
les messages on utilise ici simplement la fonction de César avec la clé − k.
2 Le chiffrement de Vigenère
Nous avons vu que le chiffrement de César présente une sécurité très faible, la principale raison est que
l’espace des clés est trop petit : il y a seulement 26 clés possibles, et on peut attaquer un message chiffré
en testant toutes les clés à la main.
Au lieu de faire correspondre circulairement les lettres, on associe maintenant à chaque lettre une autre
lettre (sans ordre fixe ou règle générale).
Par exemple :
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
F Q B M X I T E P A L W H S D O Z K V G R C N Y J U
Avantage : nous allons voir que l’espace des clés est gigantesque et qu’il n’est plus question d’énumérer
toutes les possibilités.
Inconvénients : la clé à retenir est beaucoup plus longue, puisqu’il faut partager la clé constituée des 26
lettres "FQBMX...". Mais surtout, nous allons voir que finalement ce protocole de chiffrement est assez
simple à « craquer ».
22
Espace des clés
}
Mathématiquement, le choix d’une clé revient au choix d’une bijection de l’ensemble A, B, . . . , Z vers le
}
même ensemble A, B, . . . , Z . Il y a 26! choix possibles. En effet pour la lettre A de l’ensemble de départ,
il y a 26 choix possibles (nous avions choisi F), pour B il reste 25 choix possibles (tout sauf F qui est
déjà choisi), pour C il reste 24 choix... enfin pour Z il ne reste qu’une seule possibilité, la seule lettre non
encore choisie. Au final il y a : 26 × 25 × 24 × · · · × 2 × 1 soit 26! choix de clés. Ce qui fait environ 4 × 1026
clés. Il y a plus de clés différentes que de grains de sable sur Terre ! Si un ordinateur pouvait tester
1 000 000 de clés par seconde, il lui faudrait alors 12 millions d’années pour tout énumérer.
Attaque statistique
La principale faiblesse du chiffrement mono-alphabétique est qu’une même lettre est toujours chiffrée
de la même façon. Par exemple, ici E devient X. Dans les textes longs, les lettres n’apparaissent pas
avec la même fréquence. Ces fréquences varient suivant la langue utilisée. En français, les lettres les
plus rencontrées sont dans l’ordre :
ESAINTRULODCPMVQGFHBXJYZKW
avec les fréquences (souvent proches et dépendant de l’échantillon utilisé) :
E S A I N T R U L O D
14.69% 8.01% 7.54% 7.18% 6.89% 6.88% 6.49% 6.12% 5.63% 5.29% 3.66%
Voici la méthode d’attaque : dans le texte crypté, on cherche la lettre qui apparaît le plus, et si le texte
est assez long cela devrait être le chiffrement du E, la lettre qui apparaît ensuite dans l’étude des
fréquences devrait être le chiffrement du S, puis le chiffrement du A... On obtient des morceaux de
texte clair sous la forme d’une texte à trous et il faut ensuite deviner les lettres manquantes.
L’espace des clés du chiffrement mono-alphabétique est immense, mais le fait qu’une lettre soit toujours
cryptée de la même façon représente une trop grande faiblesse. Le chiffrement de Vigenère remédie à
ce problème. On regroupe les lettres de notre texte par blocs, par exemple ici par blocs de longueur 4 :
CETTE PHRASE NE VEUT RIEN DIRE
devient
CETT EPHR ASEN EVEU TRIE NDIR E
(les espaces sont purement indicatifs, dans la première phrase ils séparent les mots, dans la seconde ils
séparent les blocs).
Si k est la longueur d’un bloc, alors on choisit une clé constituée de k nombres de 0 à 25 : (n 1 , n 2 , . . . , n k ).
Le chiffrement consiste à effectuer un chiffrement de César, dont le décalage dépend du rang de la lettre
dans le bloc :
– un décalage de n 1 pour la première lettre de chaque bloc,
23
– un décalage de n 2 pour la deuxième lettre de chaque bloc,
– ...
– un décalage de n k pour la k-ème et dernière lettre de chaque bloc.
Pour notre exemple, si on choisit comme clé (3, 1, 5, 2) alors pour le premier bloc "CETT" :
– un décalage de 3 pour C donne F,
– un décalage de 1 pour E donne F,
– un décalage de 5 pour le premier T donne Y,
– un décalage de 2 pour le deuxième T donne V.
Ainsi "CETT" de vient "FFYV". Vous remarquez que les deux lettres T ne sont pas cryptées par la
même lettre et que les deux F ne cryptent pas la même lettre. On continue ensuite avec le deuxième
bloc...
Mathématiques
L’élément de base n’est plus une lettre mais un bloc, c’est-à-dire un regroupement de lettres. La fonction
de chiffrement associe à un bloc de longueur k, un autre bloc de longueur k, ce qui donne en mathéma-
tisant les choses :
{
Z/26Z × Z/26Z × · · · × Z/26Z −→ Z/26Z × Z/26Z × · · · × Z/26Z
C n1 ,n2 ,...,n k :
(x1 , x2 , . . . , xk ) 7−→ (x1 + n 1 , x2 + n 2 , . . . , xk + n k )
Chacune des composantes de cette fonction est un chiffrement de César. La fonction de déchiffrement
est juste C −n1 ,−n2 ,...,−n k .
Il y a 26k choix possibles de clés, lorsque les blocs sont de longueur k. Pour des blocs de longueur k 4
cela en donne déjà 456 976, et même si un ordinateur teste toutes les combinaisons possibles sans
problème, il n’est pas question de parcourir cette liste pour trouver le message en clair, c’est-à-dire celui
qui est compréhensible !
Il persiste tout de même une faiblesse du même ordre que celle rencontrée dans le chiffrement mono-
alphabétique : la lettre A n’est pas toujours cryptée par la même lettre, mais si deux lettres A sont
situées à la même position dans deux blocs différents (comme par exemple "ALPH ABET") alors elles
seront cryptées par la même lettre.
Une attaque possible est donc la suivante : on découpe notre message en plusieurs listes, les premières
lettres de chaque bloc, les deuxièmes lettres de chaque bloc... et on fait une attaque statistique sur
chacun de ces regroupements. Ce type d’attaque n’est possible que si la taille des blocs est petite devant
la longueur du texte.
2.3 Algorithmes
Voici un petit algorithme qui calcule la fréquence de chaque lettre d’une phrase.
24
Et voici le chiffrement de Vigenère.
Voici le principe du chiffrement : Alice veut envoyer à Bruno le message secret M suivant :
ATTAQUE LE CHATEAU
Alice a d’abord choisi une clé secrète C qu’elle a transmise à Bruno. Cette clé secrète est de la même
longueur que le message (les espaces ne comptent pas) et composée d’entiers de 0 à 25, tirés au hasard.
Par exemple C :
[4, 18, 2, 0, 21, 12, 18, 13, 7, 11, 23, 22, 19, 2, 16, 9]
Elle crypte la première lettre par un décalage de César donné par le premier entier : A est décalé de
4 lettres et devient donc E. La seconde lettre est décalée du second entier : le premier T devient L. Le
second T est lui décalé de 2 lettres, il devient V. Le A suivant est décalé de 0 lettre, il reste A... Alice
obtient un message chiffré X qu’elle transmet à Bruno :
ELVALGW YL NEWMGQD
Pour le décrypter, Bruno, qui connaît la clé, n’a qu’à faire le décalage dans l’autre sens.
Notez que deux lettres identiques (par exemples les T) n’ont aucune raison d’être cryptées de la même
façon. Par exemple, les T du message initial sont cryptés dans l’ordre par un L, un V et un M.
Formalisons un peu cette opération. On identifie A avec 0, B avec 1, ..., Z avec 25. Alors le message
crypté X est juste la "somme" du message M avec la clé secrète C, la somme s’effectuant lettre à lettre,
terme à terme, modulo 26.
Notons cette opération M ⊕ C X .
25
A T T A Q U E L E C H A T E A U
0 19 19 0 16 20 4 11 4 2 7 0 19 4 0 20
⊕
4 18 2 0 21 12 18 13 7 11 23 22 19 2 16 9
= 4 11 21 0 11 6 22 24 11 13 4 22 12 6 16 3
E L V A L G W Y L N E W M G Q D
26
déchiffrer les messages transmis par les allemands. Ce long travail d’études et de recherches a nécessité
tout le génie d’Alan Turing et l’invention de l’ancêtre de l’ordinateur.
2. Première lettre. L’opérateur tape la première lettre du message : B, la machine affiche la corre-
spondance W.
3. Rotation. L’anneau intérieur tourne de 1/26ème de tour, maintenant le A extérieur et fixe est en
face du W, le B en face du Q,...
27
4. Deuxième lettre. L’opérateur tape la deuxième lettre du message A, la machine affiche la corre-
spondance, c’est de nouveau W.
5. Rotation. L’anneau intérieur tourne de 1/26ème de tour, maintenant le A extérieur et fixe est en
face du Q, le B en face du R, le C en face du U,...
6. Troisième lettre. L’opérateur tape la troisième lettre du message C, la machine affiche la corre-
spondance U.
7. Rotation. L’anneau intérieur effectue sa rotation.
8. Message chiffré. Le message crypté est donc "WWU"
Cette méthode de chiffrement est identique à un chiffrement de type Vigenère pour une clé de longueur
26. Il y a 26 clés différents à disposition avec un seul anneau intérieur et identifiées par lettre de la
position initiale : G, W, Q... T correspondant aux alphabets : "GWQ...PT", "WQR...TG", "QRU...GW"...
En fait, la machine Enigma était beaucoup plus sophistiquée, il n’y avait pas un mais plusieurs anneaux
intérieurs. Par exemple pour deux anneaux intérieurs comme sur la figure : B s’envoie sur W, qui
s’envoie sur A ; la lettre B est cryptée en A. Ensuite l’anneau intérieur numéro 1 effectue 1/26ème de
tour. La lettre A s’envoie sur W, qui s’envoie sur A ; la lettre A est cryptée en A. Lorsque l’anneau
intérieur numéro 1 a fait une rotation complète (26 lettres ont été tapées) alors l’anneau intérieur
numéro 2 effectue 1/26ème de tour. C’est comme sur un compteur kilométrique, lorsque le chiffre des
kilomètres parcourt 0, 1, 2, 3, ..., 9, alors au kilomètre suivant, le chiffre des kilomètres est 0 et celui des
dizaines de kilomètres est augmenté d’une unité.
S’il y a trois anneaux, lorsque l’anneau intérieur 2 a fait une rotation complète, l’anneau intérieur 3
tourne de 1/26ème de tour. Il y a alors 263 clés différentes facilement identifiables par les trois lettres
des positions initiales des anneaux.
28
Il fallait donc pour utiliser cette machine, d’abord choisir les disques (nos anneaux intérieurs) les placer
dans un certain ordre, fixer la position initiale de chaque disque. Ce système était rendu largement plus
complexe avec l’ajout de correspondances par fichage entre les lettres du clavier (voir photo). Le nombre
de clés possibles dépassait plusieurs milliards de milliards !
Commençons par rappeler que l’objectif est de générer une clé aléatoire de grande longueur. Pour ne
pas avoir à retenir l’intégralité de cette longue clé, on va la générer de façon pseudo-aléatoire à partir
d’une petite clé.
Voyons un exemple élémentaire de suite pseudo-aléatoire.
Soit (u n ) la suite définie par la donnée de (a, b) et de u 0 et la relation de récurrence
6 17 13 5 15 9 23 25 3 11 1 7 19 17 13 5
Les trois nombres (a, b, u 0 ) représentent la clé principale et la suite des (u n )nN les clés secondaires.
Avantages : à partir d’une clé principale on a généré une longue liste de clés secondaires. Inconvénients :
la liste n’est pas si aléatoire que cela, elle se répète ici avec une période de longueur 12 : 17, 13, 5, ..., 17, 13, 5, ...
Le système DES est une version sophistiquée de ce processus : à partir d’une clé courte et d’opérations
élémentaires on crypte un message. Comme lors de l’étude de la machine Enigma, nous allons présenter
une version très simplifiée de ce protocole afin d’en expliquer les étapes élémentaires.
Pour changer, nous allons travailler modulo 10. Lorsque l’on travaille par blocs, les additions se font bit
par bit. Par exemple : [1 2 3 4] ⊕ [7 8 9 0] [8 0 2 4] car (1 + 7 ≡ 8 (mod 10), 2 + 8 ≡ 0 (mod 10),...)
Notre message est coupé en blocs, pour nos explications ce seront des blocs de longueur 8. La clé est de
longueur 4.
Voici le message (un seul bloc) : M [1 2 3 4 5 6 7 8] et voici la clé : C [3 1 3 2].
Étape 0. Initialisation. On note M0 M et on découpe M en une partie gauche et une partie droite
M0 [G 0 ‖ D 0 ] [1 2 3 4 ‖ 5 6 7 8]
29
1. On échange la partie droite et la partie gauche de M0 :
M0 7−→ [5 6 7 8 ‖ 1 2 3 4]
7−→ [5 6 7 8 ‖ 2 3 4 1]
7−→ [5 6 7 8 ‖ 5 4 7 3] M1
On va recommencer le même processus. Cela revient à appliquer la formule de récurrence, qui partant
de M i [G i ‖ D i ], définit
M i+1 [D i ‖ C ⊕ σ(G i )]
Étape 2. Deuxième tour. On part de M1 [5 6 7 8 ‖ 5 4 7 3].
1. On échange la partie droite et la partie gauche de M0 :
M0 7−→ [5 4 7 3 ‖ 5 6 7 8]
7−→ [5 4 7 3 ‖ 6 7 8 5]
7−→ [5 4 7 3 ‖ 9 8 1 7] M2
Voici le texte original d’Auguste Kerckhoffs de 1883 «La cryptographie militaire» paru dans le Journal
des sciences militaires.
Il traite notamment des enjeux de sécurité lors des correspondances :
30
«Il faut distinguer entre un système d’écriture chiffré, imaginé pour un échange momen-
tané de lettres entre quelques personnes isolées, et une méthode de cryptographie destinée
à régler pour un temps illimité la correspondance des différents chefs d’armée entre eux.»
Le principe fondamental est le suivant :
«Dans le second cas, [. . . ] il faut que le système n’exige pas le secret, et qu’il puisse
sans inconvénient tomber entre les mains de l’ennemi.»
Ce principe est novateur dans la mesure où intuitivement il semble opportun de dissimuler le maximum
de choses possibles : clé et système de chiffrement utilisés. Mais l’objectif visé par Kerckhoffs est plus
académique, il pense qu’un système dépendant d’un secret mais dont le mécanisme est connu de tous
sera testé, attaqué, étudié, et finalement utilisé s’il s’avère intéressant et robuste.
Formalisons ceci avec la notion de complexité. La complexité est le temps de calculs (ou le nombre
d’opérations élémentaires) nécessaire pour effectuer une opération.
Commençons par la complexité de l’addition : disons que calculer la somme de deux chiffres (par exemple
6 + 8) soit de complexité 1 (par exemple 1 seconde pour un humain, 1 milliseconde pour un ordinateur).
Pour calculer la somme de deux entiers à n chiffres, la complexité est d’ordre n (exemple : 1234 + 2323,
il faut faire 4 additions de chiffres, donc environ 4 secondes pour un humain).
La multiplication de deux entiers à n chiffres est de complexité d’ordre n2 . Par exemple pour multiplier
1234 par 2323 il faut faire 16 multiplications de chiffres (chaque chiffre de 1234 est à multiplier par
chaque chiffre de 2323).
1
Par contre la meilleure méthode de factorisation connue est de complexité d’ordre exp(4n 3 ) (c’est moins
que exp(n), mais plus que n d pour tout d, lorsque n tend vers +∞).
Voici un tableau pour avoir une idée de la difficulté croissante pour multiplier et factoriser des nombres
à n chiffres :
n multiplication factorisation
3 9 320
4 16 572
5 25 934
10 100 5 528
50 2 500 2 510 835
100 10 000 115 681 968
200 40 000 14 423 748 780
31
Dans le cadre de la cryptographie, posséder une fonction à sens unique qui joue le rôle de chiffrement
n’a que peu de sens. En effet, il est indispensable de trouver un moyen efficace afin de pouvoir déchiffrer
les messages chiffrés. On parle alors de fonction à sens unique avec trappe secrète.
– Connaissant x, trouver y f (x) est facile, cela nécessite deux multiplications et deux divisions.
– Connaissant y image par f d’un élément x (y f (x)), retrouver x est difficile.
– soit utiliser la trappe secrète : y 7−→ y7 (mod 100) qui fournit directement le résultat !
La morale est la suivante : le problème est dur à résoudre, sauf pour ceux qui connaissent la trappe
secrète. (Attention, dans le cas de cet exemple, la fonction f n’est pas bijective.)
BRUNO
ALICE
En effet, jusqu’ici, les deux interlocuteurs se partageaient une même clé qui servait à chiffrer (et
déchiffrer) les messages. Cela pose bien sûr un problème majeur : Alice et Bruno doivent d’abord se
communiquer la clé.
BRUNO ALICE
Message crypté X
Chiffrement C Déchiffrement D
32
4.5 Chiffrement à clé publique
Les fonctions à sens unique à trappe donnent naissance à des protocoles de chiffrement à clé publique.
L’association «clé» et «publique» peut paraître incongrue, mais il signifie que le principe de chiffrement
est accessible à tous mais que le déchiffrement nécessite une clé qu’il faut bien sûr garder secrète.
BRUNO
ALICE
De façon imagée, si Bruno veut envoyer un message à Alice, il dépose son message dans la boîte aux let-
tres d’Alice, seule Alice pourra ouvrir sa boîte et consulter le message. Ici la clé publique est symbolisée
par la boîte aux lettre, tout le monde peut y déposer un message, la clé qui ouvre la boîte aux lettres est
la clé privée d’Alice, que Alice doit conserver à l’abri.
BRUNO ALICE
Clé publique
Message M Clé privée Message M
Message crypté X
Chiffrement C Déchiffrement D
En prenant appui sur l’exemple précédent, si le message initial est 71 et que la fonction f de chiffrement
est connue de tous, le message transmis est 11 et le déchiffrement sera rapide si la trappe secrète 7 est
connue du destinataire.
Les paramètres d’un protocole de chiffrement à clé publique sont donc :
– les fonctions de chiffrement et de déchiffrement : C et D ,
– la clé publique du destinataire qui va permettre de paramétrer la fonction C ,
– la clé privée du destinataire qui va permettre de paramétrer la fonction D .
Dans le cadre de notre exemple Bruno souhaite envoyer un message à Alice, ces éléments sont :
– C : x 7−→ x? (mod 100) et D : x 7−→ x? (mod 100),
– 3 : la clé publique d’Alice qui permet de définir complètement la fonction de chiffrement :
Dans la pratique, un chiffrement à clé publique nécessite plus de calculs et est donc assez lent, plus lent
qu’un chiffrement à clé privée. Afin de gagner en rapidité, un protocole hybride peut être mis en place
de la façon suivante :
– à l’aide d’un protocole de chiffrement à clé publique, Alice et Bruno échangent une clé,
– Alice et Bruno utilise cette clé dans un protocole de chiffrement à clé privée.
33
5 L’arithmétique pour RSA
Pour un entier n, sachant qu’il est le produit de deux nombres premiers, il est difficile de retrouver les
facteurs p et q tels que n pq. Le principe du chiffrement RSA, chiffrement à clé publique, repose sur
cette difficulté.
Dans cette partie nous mettons en place les outils mathématiques nécessaires pour le calcul des clés
publique et privée ainsi que les procédés de chiffrement et déchiffrement RSA.
a p ≡ a (mod p)
et sa variante :
a p−1 ≡ 1 (mod p)
Nous allons voir une version améliorée de ce théorème dans le cas qui nous intéresse :
On note ϕ(n) (p − 1)(q − 1), la fonction d’Euler. L’hypothèse pgcd(a, n) 1 équivaut ici à ce que a ne
soit divisible ni par p, ni par q. Par exemple pour p 5, q 7, n 35 et ϕ(n) 4 · 6 20. Alors pour
a 1, 2, 3, 4, 6, 8, 9, 11, 12, 13, 16, 17, 18, ... on a bien a20 ≡ 1 (mod 35).
où l’on appliquer le petit théorème de Fermat : a p−1 ≡ 1 (mod p), car p ne divise pas a.
Calculons ce même c mais cette fois modulo q :
où l’on appliquer le petit théorème de Fermat : a q−1 ≡ 1 (mod q), car q ne divise pas a.
Conclusion partielle : c ≡ 1 (mod p) et c ≡ 1 (mod q).
34
5.2 L’algorithme d’Euclide étendu
Nous avons déjà étudié l’algorithme d’Euclide qui repose sur le principe que pgcd(a, b) pgcd(b, a
(mod b)).
Voici sa mise en œuvre informatique.
On profite que assure les affectations simultanées, ce qui pour nous correspond aux suites
{
a i +1 bi
b i +1 ≡ ai (mod b i )
initialisée par a 0 a, b 0 b.
Nous avons vu aussi comment « remonter » l’algorithme d’Euclide à la main pour obtenir les coefficients
de Bézout u, v tels que au + bv pgcd(a, b). Cependant il nous faut une méthode plus automatique pour
obtenir ces coefficients, c’est l’algorithme d’Euclide étendu.
On définit deux suites (x i ), (yi ) qui vont aboutir aux coefficients de Bézout.
L’initialisation est :
x0 1 x1 0 y0 0 y1 1
et la formule de récurrence pour i 1:
x i +1 x i −1 − q i x i yi+1 yi−1 − q i yi
Cet algorithme renvoie d’abord le pgcd, puis les coefficients u, v tels que au + bv pgcd(a, b).
Proposition 8.– a admet un inverse modulo n si et seulement si a et n sont premiers entre eux.
– Si au + nv 1 alors u est un inverse de a modulo n.
En d’autres termes, trouver un inverse de a modulo n revient à calculer les coefficients de Bézout
associés à la paire (a, n).
35
Démonstration. La preuve est essentiellement une reformulation du théorème de Bézout :
pgcd(a, n) 1 ⇐⇒ ∃ u, v Z au + nv 1
⇐⇒ ∃u Z au ≡ 1 (mod n)
Voici le code :
511 58 × 52 × 51 .
i
Calculons donc les 52 (mod 14) :
5 ≡ 5 (mod 14)
52 ≡ 25 ≡ 11 (mod 14)
54 ≡ 52 × 52 ≡ 11 × 11 ≡ 121 ≡ 9 (mod 14)
58 ≡ 54 × 54 ≡ 9 × 9 ≡ 81 ≡ 11 (mod 14)
Nous obtenons donc un calcul de 511 (mod 14) en 5 opérations au lieu de 10 si on avait fait 5 × 5 × 5 · · · .
Voici une formulation générale de la méthode. On écrit le développement de l’exposant k en base 2 :
(k ` , . . . , k 2 , k 1 , k 0 ) avec k i {0, 1} de sorte que
∑
`
k k i 2i .
i 0
On obtient alors
` i ∏
` i
xk x i 0 k i 2 (x2 )k i .
i 0
Voici un autre exemple : calculons 17154 (mod 100). Tout d’abord on décompose l’exposant k 154 en
base 2 : 154 128 + 16 + 8 + 2 27 + 24 + 23 + 21 , il s’écrit donc en base 2 : (1, 0, 0, 1, 1, 0, 1, 0).
36
Ensuite on calcule 17, 172 , 174 , 178 , ..., 17128 modulo 100.
17 ≡ 17 (mod 100)
172 ≡ 17 × 17 ≡ 289 ≡ 89 (mod 100)
174 ≡ 172 × 172 ≡ 89 × 89 ≡ 7921 ≡ 21 (mod 100)
178 ≡ 174 × 174 ≡ 21 × 21 ≡ 441 ≡ 41 (mod 100)
1716 ≡ 178 × 178 ≡ 41 × 41 ≡ 1681 ≡ 81 (mod 100)
1732 ≡ 1716 × 1716 ≡ 81 × 81 ≡ 6561 ≡ 61 (mod 100)
1764 ≡ 1732 × 1732 ≡ 61 × 61 ≡ 3721 ≡ 21 (mod 100)
17128 ≡ 1764 × 1764 ≡ 21 × 21 ≡ 441 ≡ 41 (mod 100)
17154 ≡ 17128 × 1716 × 178 × 172 ≡ 41 × 81 × 41 × 89 ≡ 3321 × 3649 ≡ 21 × 49 ≡ 1029 ≡ 29 (mod 100)
En fait sait faire l’exponentiation rapide : pour le calcul de a k modulo n, il faut donc
éviter qui n’est pas adapté.
6 Le chiffrement RSA
Voici le but ultime de ce cours : la chiffrement RSA. Il est temps de relire l’introduction du chapitre
« Arithmétique » pour s’apercevoir que nous sommes prêts !
Dans cette section, c’est Bruno qui veut envoyer un message secret à Alice. La processus se décompose
ainsi :
1. Alice prépare une clé publique et une clé privée,
2. Bruno utilise la clé publique d’Alice pour crypter son message,
3. Alice reçoit le message crypté et le déchiffre grâce à sa clé privée.
37
6.1 Calcul de la clé publique et de la clé privée
Choix de deux nombres premiers
Alice effectue, une fois pour toute, les opérations suivantes (en secret) :
– elle choisit deux nombres premiers distincts p et q (dans la pratique ce sont de très grand nombres,
jusqu’à des centaines de chiffres),
– Elle calcule n p × q,
– Elle calcule ϕ(n) (p − 1) × (q − 1).
Exemple 1.
– p 5 et q 17
– n p × q 85
– ϕ(n) (p − 1) × (q − 1) 64
Vous noterez que le calcul de ϕ(n) n’est possible que si la décomposition de n sous la forme p × q est
connue. D’où le caractère secret de ϕ(n) même si n est connu de tous.
Exemple 2.
– p 101 et q 103
– n p × q 10 403
– ϕ(n) (p − 1) × (q − 1) 10 200
Alice continue :
– elle choisit un exposant e tel que pgcd(e, ϕ(n)) 1,
– elle calcule l’inverse d de e module ϕ(n) : d × e ≡ 1 (mod ϕ(n)). Ce calcul se fait par l’algorithme
d’Euclide étendu.
Exemple 1.
– Alice choisit par exemple e 5 et on a bien pgcd(e, ϕ(n)) pgcd(5, 64) 1,
– Alice applique l’algorithme d’Euclide étendu pour calculer les coefficients de Bézout correspondant à
pgcd(e, ϕ(n)) 1. Elle trouve 5 × 13 + 64 × (−1) 1. Donc 5 × 13 ≡ 1 (mod 64) et l’inverse de e modulo
ϕ(n) est d 13.
Exemple 2.
– Alice choisit par exemple e 7 et on a bien pgcd(e, ϕ(n)) pgcd(7, 10 200) 1,
– L’algorithme d’Euclide étendu pour pgcd(e, ϕ(n)) 1 donne 7 × (−1457) + 10 200 × 1 1. Mais −1457 ≡
8743 (mod ϕ(n)), donc pour d 8743 on a d × e ≡ 1 (mod ϕ(n)).
Clé publique
n et e
Et comme son nom l’indique Alice communique sa clé publique au monde entier.
Exemple 1. n 85 et e 5
Exemple 2. n 10 403 et e 7
38
Clé privée
Alice détruit en secret p, q et ϕ(n) qui ne sont plus utiles. Elle conserve secrètement sa clé privée.
Exemple 1. d 13
Exemple 2. d 8743
Message
Message chiffré
Bruno récupère la clé publique d’Alice : n et e avec laquelle il calcule, à l’aide de l’algorithme d’exponen-
tiation rapide, le message chiffré :
x ≡ m e (mod n)
39
6.3 Déchiffrement du message
Alice reçoit le message x chiffré par Bruno, elle le décrypte à l’aide de sa clé privée d, par l’opération :
m ≡ x d (mod n)
Calculons à la main 4013 ≡ (mod 85) on note que 13 8 + 4 + 1, donc 4013 408 × 404 × 40.
Exemple 2. c 10 378, d 8743, n 10 403. On calcule par ordinateur x d ≡ (10 378)8743 (mod 10 403)
qui vaut exactement le message original de Bruno m 1234.
6.4 Schéma
n, e d
? x ≡ m e (mod n) ?
m - C - D - m ≡ x d (mod n)
Bruno Alice
Clés d’Alice :
– publique : n, e
– privée : d
Ce lemme prouve bien que le message original m de Bruno, chiffré par clé publique d’Alice (e, n) en le
message x, peut-être retrouvé par Alice à l’aide de sa clé secrète d.
Démonstration. – Que d soit l’inverse de e modulo ϕ(n) signifie d · e ≡ 1 (mod ϕ(n)). Autrement dit, il
existe k Z tel que d · e 1 + k · ϕ(n).
40
– On rappelle que par le petit théorème de Fermat généralisé : lorsque m et n sont premiers entre eux
(m e )d ≡ m (mod n)
6.6 Algorithmes
La mise en œuvre est maintenant très simple. Alice choisit deux nombres premiers p et q et un exposant
e.
Voici le calcul de la clé secrète :
Le chiffrement d’un message m est possible par tout le monde, connaissant la clé publique (n, e).
41
Pour continuer...
Bibliographie commentée :
1. Histoire des codes secrets de Simon Singh, Le livre de Poche.
Les codes secrets racontés comme un roman policier. Passionnant. Idéal pour les plus littéraires.
2. Comprendre les codes secrets de Pierre Vigoureux, édition Ellipses.
Un petit livre très clair et très bien écrit, qui présente un panorama complet de la cryptographie
sans rentrer dans les détails mathématiques. Idéal pour les esprits logiques.
3. Codage et cryptographie de Joan Gómez, édition Le Monde – Images des mathématiques. Un
autre petit livre très clair et très bien, un peu de maths, des explications claires et des encarts
historiques intéressants.
4. Introduction à la cryptographie de Johannes Buchmann, édition Dunod.
Un livre d’un niveau avancé (troisième année de licence) pour comprendre les méthodes mathé-
matiques de la cryptographie moderne. Idéal pour unifier les points de vue des mathématiques
avec l’informatique.
5. Algèbre - Première année de Liret et Martinais, édition Dunod.
Livre qui recouvre tout le programme d’algèbre de la première année, très bien adapté aux étudi-
ants des l’université. Pas de cryptographie.
Auteurs
Arnaud Bodin
François Recher
42
Exo7
■
■
■
■
■
■
43
1 Premiers pas avec
Dans cette partie on vérifie d’abord que fonctionne, puis on introduira les boucles ( et ),
le test et les fonctions.
Travaux pratiques 1.
1. Définir deux variables prenant les valeurs 3 et 6.
2. Calculer leur somme et leur produit.
1.
44
Voici ce que l’on fait pour calculer S n avec n 10.
– On affecte d’abord la valeur 0 à la variable , cela correspond à l’initialisation S 0 0.
– Nous avons défini une boucle avec l’instruction qui fait varier i entre 1 et n.
– Nous calculons successivement S 1 , S 2 ,. . . en utilisant la formule de récurrence S i S i−1 + i 3 .
Comme nous n’avons pas besoin de conserver toutes les valeurs des S i alors on garde le même
nom pour toutes les sommes, à chaque étape on affecte à l’ancienne valeur de la somme
3
plus i : .
– est l’ensemble des entiers {1, 2, . . . , n}. C’est bien les entiers strictement in-
férieurs à n + 1. La raison est que désigne {0, 1, 2, . . . , n − 1} qui contient n éléments.
n( n+1)
2. Nous savons que Σn 1 + 2 + 3 + · · · + n 2 donc nous n’avons pas besoin de faire une boucle :
Une fonction en informatique est similaire à une fonction mathématique, c’est un objet qui prend
en entrée des variables (dites variables formelles ou variables muettes, ici n) et retourne une
valeur (un entier, une liste, une chaîne de caractères,... ici n(n2+1) ).
3. Voici la fonction qui retourne la somme des cubes :
2
n( n+1)
4. Et enfin on vérifie que pour les premiers entiers S n 2 , par exemple pour n 12 :
On retient :
– Les puissances se calculent aussi avec : 52 s’écrit ou , 53 s’écrit ou ,...
– Une fonction se définit par et se termine par .
– exécute le premier bloc d’instructions si la condition est vraie ; si la
condition est fausse cela exécute l’autre bloc.
– Exemple de conditions
– : a b,
– : a … b,
– : a b,
– : a 6 b.
– Attention ! Il est important de comprendre que vaut soit vraie ou faux (on compare a et b) alors
qu’avec on affecte dans a la valeur de b.
– Enfin en (contrairement aux autres langages) c’est l’indentation (les espaces en début de
chaque ligne) qui détermine les blocs d’instructions.
45
1.3 Calcul de π au hasard
Nous allons voir qu’il est possible de calculer les premières décimales de π par la méthode de Monte-
Carlo, c’est à dire avec l’aide du hasard. On considère le carré de coté 1, le cercle de rayon 1 centré à
l’origine, d’équation x2 + y2 1, et la portion de disque dans le carré (voir la figure).
(0, 1)
(0, 0) (1, 0)
Travaux pratiques 3.
1. Calculer l’aire du carré et de la portion de disque.
2. Pour un point (x, y) tiré au hasard dans le carré, quelle est la probabilité que le point soit en fait
dans la portion de disque ?
3. Tirer un grand nombre de points au hasard, compter ceux qui sont dans la portion de disque.
4. En déduire les premières décimales de π.
Voici le code :
Commentaires :
– Un petit calcul prouve que l’aire de la portion de disque est π4 , l’aire du carré est 1. Donc la probabilité
de tomber dans le disque est π4 .
– Pour tirer un nombre au hasard on utilise une fonction qui renvoie un nombre réel de
l’intervalle [0, 1[. Bien sûr à chaque appel de la fonction le nombre obtenu est différent !
– Cette fonction n’est pas connue par défaut de , il faut lui indiquer le nom du module où elle se
trouve. En début de fichier on ajoute pour le module qui gère les tirages au hasard.
Et pour indiquer qu’une fonction vient d’un module il faut l’appeler par donc ici
(module et fonction portent ici le même nom !).
– La boucle est Tant que la condition est vérifiée les instructions de la boucle
sont exécutées. Ici est le compteur que l’on a initialisé à 0. Ensuite on commence à exécuter la
boucle. Bien sûr la première chose que l’on fait dans la boucle est d’incrémenter le compteur . On
46
continue jusqu’à ce que l’on atteigne 999. Pour 1000 la condition n’est plus vraie et le bloc d’in-
structions du n’est pas exécuté. On passe aux instructions suivantes pour afficher le résultat.
– À chaque tir on teste si on est dans la portion de disque ou pas à l’aide de l’inégalité x2 + y2 … 1.
– Cette méthode n’est pas très efficace, il faut beaucoup de tirs pour obtenir le deux premières décimales
de π.
1.5 Mini-exercices
1. Soit le produit P n (1 − 12 ) × (1 − 13 ) × (1 − 14 ) ×· · ·× (1 − n1 ). Calculer une valeur approchée de P n pour
les premiers entiers n.
2. Que vaut la somme des entiers i qui apparaissent dans l’instruction .
Idem pour . Idem pour . Idem pour .
Idem pour .
3. On considère le cube [0, 1] × [0, 1] × [0, 1] et la portion de boule de rayon 1 centrée à l’origine incluse
dans ce cube. Faire les calculs de probabilité pour un point tiré au hasard dans le cube d’être en
fait dans la portion de boule. Faire une fonction pour le vérifier expérimentalement.
4. On lance deux dés. Expérimenter quelle est la probabilité que la somme soit 7, puis 6, puis
3 ? Quelle est la probabilité que l’un des deux dés soit un 6 ? d’avoir un double ? La fonction
du module retourne un entier k au hasard, vérifiant a … k … b.
5. On lance un dé jusqu’à ce que l’on obtienne un 6. En moyenne au bout de combien de lancer
s’arrête-t-on ?
a bq + r et 0…rb
47
Les calculs avec les modulos sont très pratiques. Par exemple si l’on souhaite tester si un entier est pair,
ou impair cela revient à un test modulo 2. Le code est . Si on besoin
de calculer cos(n π2 ) alors il faut discuter suivant les valeurs de .
Commentaires :
– Comment obtient-on le chiffre des unités d’un entier N ? C’est le reste modulo 10, d’où l’instruction
.
– Comment obtient-on le chiffre des dizaines ? C’est plus délicat, on commence par effectuer la division
euclidienne de N par 10 (cela revient à supprimer le chiffre des unités, par exemple si N 251 alors
retourne 25). Il ne reste plus qu’à calculer le reste modulo 10, (par exemple
retourne le chiffre des dizaines 5.
– Pour le chiffre des centaines on divise d’abord par 100.
48
La formule mathématique est simplement N a n 10n + a n−1 10n−1 + · · · + a 2 102 + a 1 10 + a 0 . Par exemple
renvoie l’entier 1234.
Expliquons les bases sur les listes (qui s’appelle aussi des tableaux)
– En une liste est présentée entre des crochets. Par exemple pour alors on
accède aux valeurs par : vaut 4, vaut 3, vaut 2, vaut 1.
– Pour parcourir les éléments d’un tableau le code est simplement , x vaut alors succes-
sivement 4, 3, 2, 1.
– La longueur du tableau s’obtient par . Pour notre exemple vaut 4. Pour
parcourir toutes les valeurs d’un tableau on peut donc aussi écrire , puis
utiliser , ici i variant ici de 0 à 3.
– La liste vide est seulement notée avec deux crochets : . Elle est utile pour initialiser une liste.
– Pour ajouter un élément à une liste existante on utilise la fonction . Par exemple définis-
sons la liste vide , pour ajouter une valeur à la fin de la liste on saisit : . Main-
tenant notre liste est [4], elle contient un seul élément. Si on continue avec . Alors
maintenant notre liste a deux éléments : [4, 3].
Voici l’écriture d’un entier en base 10 :
Par exemple renvoie le tableau [4, 3, 2, 1]. Nous avons expliqué tout ce
dont nous avions besoin sur les listes au-dessus, expliquons les mathématiques.
– Décomposons N∗ sous la forme [1, 10[ [10, 100[ [100, 1000[ [1 000, 10 000[ · · · Chaque intervalle
est du type [10n , 10n+1 [. Pour N N∗ il existe donc n N tel que 10n … N 10n+1 . Ce qui indique que
le nombre de chiffres de N est n + 1.
Par exemple si N 1234 alors 1 000 103 … N 104 10 000, ainsi n 3 et le nombre de chiffres est
4.
– Comment calculer n à partir de N ? Nous allons utiliser le logarithme décimal log10 qui vérifie
log10 (10) 1 et log10 (10 i ) i. Le logarithme est une fonction croissante, donc l’inégalité 10n … N
10n+1 devient log10 (10n ) … log10 (N) log10 (10n+1 ). Et donc n … log10 (N) n + 1. Ce qui indique donc
que n E(log10 (N)) où E(x) désigne la partie entière d’un réel x.
2.3 Module
Quelques commentaires informatiques sur un module important pour nous. Les fonctions mathéma-
tiques ne sont pas définies par défaut dans (à part | x| et x n ), il faut faire appel à une librairie
spéciale : le module contient les fonctions mathématiques principales.
49
| x|
xn
p
x
exp x
ln x logarithme népérien
log x logarithme décimal
cos x, sin x, tan x en radians
arccos x, arcsin x, arctan x en radians
partie entière E(x) :plus grand entier n … x (floor = plancher)
plus petit entier n x (ceil = plafond)
0 1 2 3 4 5 6 7
On numérote les lampes de 0 à 7. On souhaite contrôler cette rampe : afficher toutes les combinaisons
possibles, faire défiler une combinaison de la gauche à droite (la “chenille”), inverser l’état de toutes
les lampes,... Voyons comment l’écriture binaire des nombres peut nous aider. L’écriture binaire d’un
nombre c’est son écriture en base 2.
Comment calculer un nombre qui est écrit en binaire ? Le chiffre des “dizaines” correspond à 2 (au lieu
de 10), le chiffre des “centaines” à 4 22 (au lieu de 100 102 ), le chiffres des “milliers” à 8 23 (au lieu
de 1000 103 ),... Pour le chiffre des unités cela correspond à 20 1 (de même que 100 1).
Par exemple 10011b vaut le nombre 19. Car
10011b 1 · 24 + 0 · 23 + 0 · 22 + 1 · 21 + 1 · 20 16 + 2 + 1 19.
N a n 2 n + a n −1 2 n −1 + · · · + a 2 22 + a 1 2 + a 0 et a i {0, 1}
On note alors N a n a n−1 . . . a 1 a 0 b (avec un indice b pour indiquer que c’est son écriture binaire).
Travaux pratiques 6.
1. Écrire une fonction qui à partir d’une liste [a 0 , a 1 , . . . , a n ] calcule l’entier N correspondant à l’écri-
ture binaire a n a n−1 . . . a 1 a 0 b .
2. Écrire une fonction qui à partir de N calcule son écriture binaire sous la forme [a 0 , a 1 , . . . , a n ].
La seule différence avec la base 10 c’est que l’on calcule avec des puissances de 2.
50
Idem pour le sens inverse où l’on a besoin du logarithme en base 2, qui vérifie log2 (2) 1 et log2 (2 i ) i.
Maintenant appliquons ceci à notre problème de lampes. Si une lampe est allumée on lui attribut 1, et
si elle est éteinte 0. Pour une rampe de 8 lampes on code [a 0 , a 1 , . . . , a 7 ] l’état des lampes.
Par exemple la configuration suivante :
20 21 22 23 24 25 26 27
51
Où est similaire à , mais en affichant
aussi les zéros non significatifs, par exemple 7 en binaire s’écrit 111b , mais codé sur 8 chiffres on
ajoute devant des 0 non significatifs : 00000111b .
2. En écriture décimale, multiplier par 10 revient à décaler le nombre initial et rajouter un zéro.
Par exemple 10 × 19 190. C’est la même chose en binaire ! Multiplier un nombre par 2 revient
sur l’écriture à un décalage vers la gauche et ajout d’un zéro sur le chiffre des unités. Exemple :
19 10011b et 2 × 19 38 donc 2 × 10011b 100110b .
3. Partant de N a n a n−1 . . . a 1 a 0 b . Notons N ′ 2N, son écriture est N ′ a n a n−1 . . . a 1 a 0 0 b . Alors
N ′ (mod 2n+1 ) s’écrit exactement a n−1 a n−2 . . . a 1 a 0 0 b et on ajoute a n qui est le quotient de N ′ par
2 n +1 .
Preuve : N ′ a n · 2n+1 + a n−1 · 2n + · · · + a 0 · 2. Donc N ′ (mod 2n+1 ) a n−1 · 2n + · · · + a 0 · 2. Donc N ′
(mod 2n+1 ) + a n a n−1 · 2n + · · · + a 0 · 2 + a n .
4. Ainsi l’écriture en binaire de N ′ (mod 2n+1 ) + a n s’obtient comme permutation circulaire de celle
de N. D’où l’algorithme :
5. On remarque que si l’on a deux configurations opposées alors leur somme vaut 2n+1 − 1 : par ex-
emple avec [1, 0, 0, 1, 0, 1, 1, 1] et [0, 1, 1, 0, 1, 0, 0, 0], les deux nombres associés sont N 11101001b
et N ′ 00010110b (il s’agit juste de les réécrire de droite à gauche). La somme est N + N ′
11101001b + 00010110b 11111111b 28 − 1. L’addition en écriture binaire se fait de la même
façon qu’en écriture décimale et ici il n’y a pas de retenue. Si M est un nombre avec n + 1 fois le
chiffres 1 alors M + 1 2n+1 . Exemple si M 11111b alors M + 1 100000b 25 ; ainsi M 25 − 1.
Donc l’opposé de N est N ′ 2n+1 − 1 − N (remarquez que dans Z/(2n+1 − 1)Z alors N ′ ≡ − N).
Cela conduit à :
2.5 Mini-exercices
1. Pour un entier n fixé, combien y-a-t-il d’occurrences du chiffre 1 dans l’écriture des nombres de 1
à n?
2. Écrire une fonction qui calcule l’écriture décimale d’un entier, sans recourir au log (une boucle
est la bienvenue).
3. Écrire un algorithme qui permute cycliquement une configuration de rampe vers la droite.
4. On dispose de n + 1 lampes, chaque lampe peut s’éclairer de trois couleurs : vert, orange, rouge
(dans cet ordre). Trouver toutes les combinaisons possibles. Comment passer toutes les lampes à
la couleur suivante ?
5. Générer toutes les matrices 4 × 4 n’ayant que des 0 et des 1 comme coefficients. On codera une
matrice sous la forme de lignes [[1, 1, 0, 1], [0, 0, 1, 0], [1, 1, 1, 1], [0, 1, 0, 1]].
52
6. On part du point (0, 0) Z2 . A chaque pas on choisit au hasard un direction Nord, Sud, Est, Ouest.
Si on va au Nord alors on ajoute (0, 1) à sa position (pour Sud on ajoute (0, −1) ; pour Est (1, 0) ; pour
Ouest (−1, 0)). Pour un chemin d’une longueur fixée de n pas, coder tous les chemins possibles.
Caractériser les chemins qui repassent par l’origine. Calculer la probabilité p n de repasser par
l’origine. Que se passe-t-il lorsque n → +∞ ?
7. Écrire une fonction, qui pour un entier N, affiche son écriture en chiffres romains : M 1000,
D 500, C 100, X 10, V 5, I 1. Il ne peut y avoir plus de trois symboles identiques à
suivre.
+∞
∑ x 2 k +1 x3 x5 x7
Arctan x (−1)k x− + − +···
k 0 2k + 1 3 5 7
Travaux pratiques 8.
1. Calculer Arctan 1.
2. Calculer θ i Arctan 10− i (avec 8 chiffres après la virgule) pour i 1, . . . , 8.
3. Pour quelles valeurs de i, l’approximation Arctan x ' x était-elle suffisante ?
– La série qui permet de calculer Arctan x est une somme infinie, mais si x est petit alors chacun
2 k +1
1
des termes (−1)k 2xk+1 est très très petit dès que
∣ k devient ∣ grand. Par exemple si 0 … x … 10 alors
∣ 2 k +1 ∣
x2k+1 … 1021k+1 et donc pour k 4 nous aurons ∣(−1)k 2xk+1 ∣ 10−9 . Chacun des termes suivants ne
contribue pas aux 8 premiers chiffres après la virgule. Attention : il se pourrait cependant que la
somme de beaucoup de termes finissent par y contribuer, mais ce n’est pas le cas ici (c’est un bon
exercice de le prouver).
– Dans la pratique on calcule la somme à un certain ordre 2k + 1 jusqu’à ce que les 8 chiffres après
la virgules ne bougent plus. Et en fait on s’aperçoit que l’on a seulement besoin d’utiliser Arctan x '
3 5 7
x − x3 + x5 − x7 .
– Pour i 4, Arctan x ' x donne déjà 8 chiffres exacts après la virgule !
On remplit les valeurs des angles θ i obtenus dans une liste nommée .
53
3.2 Calcul de tan x
Le principe est le suivant : on connaît un certain nombre d’angles avec leur tangente : les angles θ i
(calculés ci-dessus) avec par définition tan θ i 10− i . Fixons un angle a [0, π2 ]. Partant du point M0
(1, 0), nous allons construire des points M1 , M2 , . . . , M n jusqu’à ce que M n soit (à peu près) sur la demi-
y
droite correspondant à l’angle a. Si M n a pour coordonnées (xn , yn ) alors tan a xnn . L’angle pour passer
d’un point M k à M k+1 est l’un des angles θ i .
Mn
M n −1
M2
M1
a
θi n
θi2
θi1
O M0
Rappelons que si l’on a un point M(x, y) alors la rotation centrée à l’origine et d’angle θ envoie M(x, y)
sur le point N(x′ , y′ ) avec
′ { ′
x cos θ − sin θ x x x cos θ − y sin θ
c’est-à-dire
y′ sin θ cos θ y y′ x sin θ + y cos θ
Pour un point M, on note M ′ le point de la demi-droite [ON) tel que les droites (OM) et (M M ′ ) soient
perpendiculaires en M.
M′
Mn
N
y
tan a ' xn
n
yn
a
θ
O M
O xn
Travaux pratiques 9.
1. (a) Calculer la longueur OM ′ .
(b) En déduire les coordonnées de M ′ .
(c) Exprimez-les uniquement en fonction de x, y et tan θ .
2. Faire une boucle qui décompose l’angle a en somme d’angles θ i (à une précision de 10−8 ; avec un
minimum d’angles, les angles pouvant se répéter).
3. Partant de M0 (1, 0) calculer les coordonnées des différents M k , jusqu’au point M n (xn , yn ) corre-
y
spondant à l’approximation de l’angle a. Renvoyer la valeur xnn comme approximation de tan a.
– D’autre part comme la rotation d’angle θ conserve les distances alors OM ON. Si les coordonnées
de M ′ sont (x′′ , y′′ ) alors x′′ cos1 θ x′ et y′′ cos1 θ y′ .
54
– Ainsi {
x′′ cos1 θ x′ cos1 θ x cos θ − y sin θ x − y tan θ
y′′ cos1 θ y′ cos1 θ x sin θ + y cos θ x tan θ + y
Autrement dit :
x′′ 1 − tan θ x
y′′ tan θ 1 y
Voici une boucle simple pour décomposer l’angle θ : on commence par retirer le plus grand angle θ0
autant de fois que l’on peut, lorsque ce n’est plus possible on passe à l’angle θ1 ,...
Ici est la précision souhaité (pour nous 10−9 ). Et le tableau contient les valeurs des
angles θ i .
x0 1 − tan θ
Posons x0 1, y0 0 et M0 . Alors on définit par récurrence M k+1 P(θ i )· M k où P(θ ) .
y0 tan θ 1
Les θ i sont ceux apparaissant dans la décomposition de l’angle en somme de θ i , donc on connaît tan θ i
10− i . Ainsi si l’on passe d’un point M k à M k+1 par un angle θ i on a simplement :
{
xk+1 xk − yk · 10− i
yk+1 xk · 10− i + yk
y
La valeur xnn est la tangente de la somme des angles θ i , donc une approximation de tan a.
Le code est maintenant le suivant.
55
– Notez à quel point les opérations du calcul de tan x sont simples : il n’y a quasiment que des additions
à effectuer. Par exemple l’opération xk+1 xk − yk · 10− i peut être fait à la main : multiplier par 10− i
c’est juste décaler la virgule à droite de i chiffres, puis on additionne. C’est cet algorithme «CORDIC»
qui est implémenté dans les calculatrices, car il nécessite très peu de ressources. Bien sûr, si les
nombres sont codés en binaire on remplace les 10− i par 2− i pour n’avoir qu’à faire des décalages à
droite.
3.4 Mini-exercices
1. On dispose de billets de 1, 5, 20 et 100 euros. Trouvez la façon de payer une somme de n euros
avec le minimum de billets.
2. Faire un programme qui pour n’importe quel x R, calcule sin x, cos x, tan x.
2t
3. Pour t tan 2x montrer que tan x 1− t 2
. En déduire une fonction qui calcule tan x. (Utiliser que
pour x assez petit tan x ' x).
4. Modifier l’algorithme de la tangente pour qu’il calcule aussi directement le sinus et le cosinus.
4 Les réels
Dans cette partie nous allons voir différentes façons de calculer la constante d’Euler. C’est un nombre
assez mystérieux car personne ne sait si est un nombre rationnel ou irrationnel. Notre objectif est
d’avoir le plus de décimales possibles après la virgule en un minimum d’étapes. Nous verrons ensuite
comment les ordinateurs stockent les réels et les problèmes que cela engendre.
1 1 1 1
Hn + + +···+
1 2 3 n
et définissons
u n H n − ln n.
Cette suite (u n ) admet une limite lorsque n → +∞ : c’est la constante d’Euler.
56
Vous remarquez que la somme est calculée à partir de la fin. Nous expliquerons pourquoi en fin de
section.
Voici le code :
57
C 1
Pour obtenir N décimales il faut résoudre l’inéquation e4n
… 10 N
. On «passe au log» pour obtenir n
N ln(10)+ln(C )
4 .
On ne connaît pas C mais ce n’est pas si important. Moralement pour une itération de plus
on obtient (à peu près) une décimale de plus (c’est-à-dire un facteur 10 sur la précision !). Pour n 800
on obtient 1000 décimales exactes de la constante d’Euler :
0,
57721566490153286060651209008240243104215933593992 35988057672348848677267776646709369470632917467495
14631447249807082480960504014486542836224173997644 92353625350033374293733773767394279259525824709491
60087352039481656708532331517766115286211995015079 84793745085705740029921354786146694029604325421519
05877553526733139925401296742051375413954911168510 28079842348775872050384310939973613725530608893312
67600172479537836759271351577226102734929139407984 30103417771778088154957066107501016191663340152278
93586796549725203621287922655595366962817638879272 68013243101047650596370394739495763890657296792960
10090151251959509222435014093498712282479497471956 46976318506676129063811051824197444867836380861749
45516989279230187739107294578155431600500218284409 60537724342032854783670151773943987003023703395183
28690001558193988042707411542227819716523011073565 83396734871765049194181230004065469314299929777956
93031005030863034185698032310836916400258929708909 85486825777364288253954925873629596133298574739302
Pour obtenir plus de décimales que la précision standard de , il faut utiliser le module
qui permet de travailler avec une précision arbitraire fixée.
pour ±1, 234 . . . × 10±123 . La mantisse est un nombre décimal (positif ou négatif) appartenant à [1, 10[
et l’exposant est un entier (lui aussi positif ou négatif). En la mantisse à une précision de 16
chiffres après la virgule.
Cette réalité informatique fait que des erreurs de calculs peuvent apparaître même avec des opérations
simples. Pour voir un exemple de problème faites ceci :
Comme est très précis nous allons faire une routine qui permet de limiter drastiquement le
nombre de chiffres et mettre en évidence les erreurs de calculs.
Voici le code :
Comme on l’a déjà vu auparavant l’exposant se récupère à l’aide du logarithme en base 10. Et pour
tronquer un nombre avec 6 chiffres, on commence par le décaler vers la gauche pour obtenir 6 chiffres
avant la virgule (123, 456789 devient 123456, 789) il ne reste plus qu’à prendre la partie entière (123456)
et le redécaler vers la droite (pour obtenir 123, 456).
58
Absorption
Chacun des nombres 1234, 56 et 0, 007 est bien un nombre s’écrivant avec moins de 6 décimales mais
leur somme 1234, 567 a besoin d’une décimale de plus, l’ordinateur ne retient pas la 7-ème décimale et
ainsi le résultat obtenu est 1234, 56. Le 0, 007 n’apparaît pas dans le résultat : il a été victime d’une
absorption.
Élimination
Comme x − y 22, 6555 qui n’a que 6 chiffres alors on peut penser que l’ordinateur va obtenir ce résultat.
Il n’en est rien, l’ordinateur ne stocke pas x mais , idem pour y. Donc l’ordinateur effectue
en fait le calcul suivant : , il calcule donc 1234, 87 − 1212, 22
22, 65. Quel est le problème ? C’est qu’ensuite l’utilisateur considère –à tort– que le résultat est calculé
avec une précision de 6 chiffres. Donc on peut penser que le résultat est 22, 6500 mais les 2 derniers
chiffres sont une pure invention.
C’est un phénomène d’élimination. Lorsque l’on calcule la différence de deux nombres proches, le
résultat a en fait une précision moindre. Cela peut être encore plus dramatique avec l’exemple
1234, 569 − 1234, 55 la différence est 0, 01900 alors que l’ordinateur retournera 0, 01000. Il y a presque
un facteur deux, et on aura des problèmes si l’on a besoin de diviser par .
Signalons au passage une erreur d’interprétation fréquente : ne pas confondre la précision d’affichage
(exemple : on calcule avec 10 chiffres après la virgule) avec l’exactitude du résultat (combien de déci-
males sont vraiment exactes ?).
Enfin le problème le plus troublant est que les nombres flottants sont stockés en écriture binaire et pas
en écriture décimale.
La raison est simple mais néanmoins troublante. L’ordinateur ne stocke pas 0, 1, ni 0, 2 en mémoire mais
le nombre en écriture binaire qui s’en rapproche le plus.
En écriture décimale, il est impossible de coder 1/3 0, 3333 . . . avec un nombre fini de chiffres après la
virgule. Il en va de même ici : l’ordinateur ne peut pas stocker exactement 0, 2. Il stocke un nombre en
écriture binaire qui s’en rapproche le plus ; lorsqu’on lui demande d’afficher le nombre stocké, il retourne
l’écriture décimale qui se rapproche le plus du nombre stocké, mais ce n’est plus 0, 2, mais un nombre
très très proche :
...
59
4.4 Somme des inverses des carrés
Voyons une situation concrète où ces problèmes apparaissent.
Travaux pratiques 18.
1
1. Faire une fonction qui calcule la somme S n 12
+ 212 + 312 + · · · + n12 .
2. Faire une fonction qui calcule cette somme mais en utilisant seulement une écriture décimale à 6
chiffres (à l’aide de la fonction vue au-dessus).
3. Reprendre cette dernière fonction, mais en commençant la somme par les plus petits termes.
4. Comparez le deux dernières méthodes, justifier et conclure.
La première fonction ne pose aucun problème et utilise toute la précision de .
Dans la seconde on doit, à chaque calcul, limiter notre précision à 6 chiffres (ici 1 avant la virgule et 5
après).
4.5 Mini-exercices
1. Écrire une fonction qui approxime la constante qui vérifie (ln − 1) 1. Pour cela poser f (x)
x(ln x − 1) − 1 et appliquer la méthode de Newton : fixer u 0 (par exemple ici u 0 4) et u n+1
f (u )
u n − f ′ (unn ) .
2. Pour chacune des trois méthodes, calculer le nombre approximatif d’itérations nécessaires pour
obtenir 100 décimales de la constante d’Euler.
k)!]3 An Cn
3. Notons C n 41n 2kn0 (k!)[(2 1
4 (16 n)2 k . La formule de Brent-McMillan affirme B − B 2 − ln n + O( e 8 n )
n n
où cette fois les sommations pour A n et B n vont jusqu’à E( n) avec 4, 970625759 . . . la solution
de (ln − 1) 3. La notation O( e18n ) indique que l’erreur est … eC8n pour une certaine constante
C. Mettre en œuvre cette formule. En 1999 cette formule a permis de calculer 100 millions de
décimales. Combien a-t-il fallu d’itérations ?
60
1
4. Faire une fonction qui renvoie le terme u n de la suite définie par u 0 3 et u n+1 4u n − 1. Que
vaut u 100 ? Faire l’étude mathématique et commenter.
Voyons comment fonctionne cette boucle. On initialise la variable à 1, on fait varier un indice i
de 1 à n. À chaque étape on multiplie par i et on affecte le résultat dans . Par exemple
si n 5 alors la variable s’initialise à 1, puis lorsque i varie la variable produit devient 1 × 1 1,
2 × 1 2, 3 × 2 6, 4 × 6 24, 5 × 24 120. Vous avez bien sûr reconnus le calcul de 5!
Que fait cet algorithme ? Voyons cela pour n 5. Pour n 5 la condition du «si» (if) n’est pas vérifiée donc
on passe directement au «sinon» (else). Donc renvoie comme résultat : .
On a plus ou moins progressé : le calcul n’est pas fini car on ne connaît pas encore mais
on s’est ramené à un calcul au rang précédent, et on itère :
u1 1 et u n n × u n−1 si n 2.
61
Faites-le calcul de . Voici la version mathématique des nombres de Fibonacci.
F0 1, F1 1 et F n F n −1 + F n −2 si n 2.
1 1 2 3 5 8 13 21 34 ...
Voici le code pour l’algorithme d’Euclide récursif. Notez à quel point le code est succinct et épuré !
Deux entiers a, b sont premiers entre eux ssi pgcd(a, b) 1, donc voici l’algorithme :
62
On tire au hasard deux entiers a et b entre 1 et n et on effectue cette opération fois. Par exem-
ple entre 1 et 1000 si l’on effectue 10 000 tirage on trouve une probabilité mesurée par
de 0, 60 . . . (les décimales d’après dépendent des tirages).
Lorsque n tend vers +∞ alors p n → π62 0.607927 . . . et on dit souvent que : «la probabilité que deux
entiers tirés au hasard soient premiers entre eux est π62 .»
Notez qu’il vaut mieux écrire la condition plutôt que : il est beaucoup
plus rapide de calculer le carré d’un entier plutôt qu’extraire une racine carrée.
Nous avons utilisé un nouveau type de variable : un booléen est une variable qui ne peut prendre
que deux états Vrai ou Faux (ici True or False, souvent codé 1 et 0). Ainsi
renvoie , alors que renvoie .
63
2. Pour le crible d’Eratosthène le plus dur est de trouver le bon codage de l’information.
À gauche le début de la spirale (de n 1 à 37) en rouge les nombres premiers (en noir les nombres
non premiers) ; à droite le motif obtenu jusqu’à de grandes valeurs (en blanc les nombres non
premiers).
5.4 Mini-exercices
1. Écrire une version itérative et une version récursive pour les fonctions suivantes : (a) la somme
des carrés des entiers de 1 à n ; (b) 2n (sans utiliser d’exposant) ; (c) la partie entière d’un réel
x 0 ; (d) le quotient de la division euclidienne de a par b (avec a N, b N∗ ) ; (e) le reste de cette
division euclidienne (sans utiliser les commandes ni ).
64
2. Écrire une version itérative de la suite de Fibonacci.
3. Écrire une version itérative de l’algorithme d’Euclide. Faire une version qui calcule les coefficients
de Bézout.
4. Écrire une fonction itérative, puis récursive, qui pour un entier n renvoie la liste de ses diviseurs.
Dessiner une spirale d’Ulam, dont l’intensité de la couleur dépend du nombre de diviseurs.
5. Une suite de Syracuse est définie ainsi : partant d’un entier s’il est pair on le divise par deux, s’il
est impair on le multiplie par 3 et on ajoute 1. On itère ce processus. Quelle conjecture peut-on
faire sur cette suite ?
1
6. Dessiner le triangle de Pascal 1 1 Ensuite effacer tous les coefficients pairs (ou mieux : rem-
1 2 1
···
placer les coefficients pairs par un carré blanc et les coefficients impairs par un carré rouge).
Quelle figure reconnaissez-vous ?
6.2 Polynômes
Travaux pratiques 21. On code un polynôme a 0 +a 1 X +· · ·+a n X n sous la forme d’une liste [a 0 , a 1 , . . . , a n ].
1. Écrire une fonction correspondant à la somme de deux polynômes. Calculer la complexité de
cet algorithme (en terme du nombre d’additions sur les coefficients, en fonctions du degré des
polynômes).
2. Écrire une fonction correspondant au produit de deux polynômes. Calculer la complexité de cet
algorithme (en terme du nombre d’additions et de multiplications sur les coefficients).
3. Écrire une fonction correspondant au quotient et au reste de la division euclidienne de A par B où
B est un polynôme unitaire (son coefficient de plus haut degré est 1). Majorer la complexité de cet
algorithme (en terme du nombre d’additions et de multiplications sur les coefficients).
1. La seule difficulté est de gérer les indices, en particulier on ne peut appeler un élément d’une liste
en dehors des indices où elle est définie. Une bonne idée consiste à commencer par définir une
fonction , qui renvoie le degré du polynôme (attention au 0 non significatifs).
Voici le code dans le cas simple où deg A deg B :
65
Calculons sa complexité, on suppose deg A … n et deg B … n : il faut faire l’addition des coefficients
a i + b i , pour i variant de 0 à n : donc la complexité est de n + 1 additions (dans Z ou R).
n
2. Pour le produit il faut se rappeler que si A(X ) m i
i 0 a i X , B(X )
j
j 0 b j X et C A × B
m+ n
k 0 k
c X k alors le k-ème coefficient de C est c k i+ jk a i × b j . Dans la pratique on fait attention
de ne pas accéder à des coefficients qui n’ont pas été définis.
Pour la complexité on commence par compter le nombre de multiplications (dans Z ou R). Notons
m deg A et n deg B. Alors il faut multiplier les m + 1 coefficients de A par les n + 1 coefficients
de B : il y a donc (m + 1)(n + 1) multiplications.
Comptons maintenant les additions : les coefficients de A × B sont : c 0 a 0 b 0 , c 1 a 0 b 1 + a 1 b 0 ,
c 2 a 2 b 0 + a 1 b 1 + a 2 b 0 ,...
Nous utilisons l’astuce suivante : nous savons que le produit A × B est de degré m + n donc a
(au plus) m + n + 1 coefficients. Partant de (m + 1)(n + 1) produits, chaque addition regroupe deux
termes, et nous devons arriver à m + n + 1 coefficients. Il y a donc (m + 1)(n + 1) − (m + n + 1) mn
additions.
3. Pour la division euclidienne, le principe est de poser une division de polynôme. Par exemple pour
A 2X 4 − X 3 − 2X 2 + 3X − 1 et B X 2 − X + 1.
2X 4 − X 3 − 2X 2 + 3X − 1 X2 − X +1
− 2X 4 − 2X 3 + 2X 2
X 3 − 4X 2 + 3X − 1 2X 2 + X − 3
− X3 − X2 + X
−3X 2 + 2X − 1
− −3X 2 + 3X − 3
−X + 2
Alors on cherche quel monôme P1 fait diminuer le degré de A − P1 B, c’est 2X 2 (le coefficient 2 est
le coefficient dominant de A). On pose ensuite R 1 A − P1 B X 3 − 4X 2 + 3X − 1, Q 1 2X 2 , on
recommence avec R 1 divisé par B, R 2 R 1 − P2 B avec P2 X , Q 2 Q 1 + P2 ,... On arrête lorsque
deg R i deg B.
66
C’est une version un peu simplifiée du code : où P r n X deg R −deg B et où il faut remplacer −P par
[−a 0 , −a 1 , ...]. Si A, B Z[X ] alors le fait que B soit unitaire implique que Q et R sont aussi à
coefficients entiers.
Quelle est la complexité de la division euclidienne ? À chaque étape on effectue une multiplication
de polynômes (P i × B) puis une addition de polynôme (R i − P i B) ; à chaque étape le degré de R i
diminue (au moins) de 1. Donc il y a au plus deg A − deg B + 1 étapes.
Mais dans la pratique c’est plus simple que cela. La multiplication P i × B est très simple : car P i
est un monôme P i p i X i . Multiplier par X i c’est juste un décalage d’indice (comme multiplier
par 10 i en écriture décimale) c’est donc une opération négligeable. Il reste donc à multiplier les
coefficients de B par p i : il y a donc deg B + 1 multiplications de coefficients. La soustraction
aussi est assez simple on retire à R i un multiple de B, donc on a au plus deg B + 1 coefficients à
soustraire : il y a à chaque étape deg B + 1 additions de coefficients.
Bilan : si m deg A et n deg B alors la division euclidienne s’effectue en au plus (m − n + 1)(m + 1)
multiplications et le même nombre d’additions (dans Z ou R).
P P1 + P2 · X n et Q Q1 + Q2 · X n
(P1 + X n P2 ) · (Q 1 + X n Q 2 ) P1 Q 1 + X n · (P1 Q 2 + P2 Q 1 ) + X 2n · P2 Q 2
67
On se ramène ainsi aux quatre multiplications P1 Q 1 , P1 Q 2 , P2 Q 1 et P2 Q 2 entre polynômes de
degrés strictement inférieurs à n, plus deux multiplications par X n et X 2n qui ne sont que des
ajouts de zéros en tête de liste.
2. On sépare les deux étapes de l’algorithme : d’abord la découpe des polynômes (dans laquelle il
ne faut pas oublier de donner n en argument car ce n’est pas forcément le milieu du polynôme,
n doit être le même pour P et Q). Le découpage correspond à l’écriture
n
P P1 + X P2 .
La relation de récurrence qui exprime la complexité de cet algorithme est C(n) 4C(n/2) + O(n) et
elle se résout en C(n) O(n2 ). Voir la question suivante pour une méthode de résolution.
3.
68
4. Notons C(n) la complexité de la multiplication entre deux polynômes de degrés strictement in-
férieurs à n. En plus des trois appels récursifs, il y a des opérations linéaires : deux calculs de
degrés, deux découpes en n/2 puis des additions : deux de taille n/2, une de taille n, une de taille
3n/2 et une de taille 2n. On obtient donc la relation de récurrence suivante :
C(n) 3 · C(n/2) + n
C (2 ) 2 `
où 15
`
puis pour n 2` :
ln 3 ln 3
C(n) C(2` ) 3` ` (3`+1 − 2`+1 ) + (1 − )3` O(3` ) O(2` ln 2 ) O(n ln 2 )
ln 3
La complexité de la multiplication de Karatsuba est donc O(n ln 2 ) ' O(n1.585 ).
6.5 Mini-exercices
1. Faire une fonction qui renvoie le pgcd de deux polynômes.
2. Comparer les complexités des deux méthodes suivantes pour évaluer un polynôme P en une valeur
n −1 n
x0 R : P(x0 ) a 0 + a 1 x0 + · · · + a n−1 x0 + a n x0 et P(x0 ) a 0 + x0 a 1 + x0 a 2 + · · · + x0 (a n−1 + a n x0 )
(méthode de Horner).
3. Comment trouver le maximum d’une liste ? Montrer que votre méthode est de complexité mini-
male (en terme du nombre de comparaisons).
4. Soit f : [a, b] → R une fonction continue vérifiant f (a) · f (b) … 0. Combien d’itérations de la méthode
de dichotomie sont nécessaires pour obtenir une racine de f (x) 0 avec une précision inférieure à
?
5. Programmer plusieurs façons de calculer les coefficients du binôme de Newton nk et les comparer.
6. Trouver une méthode de calcul de 2n qui utilise peu de multiplications. On commencera par écrire
n en base 2.
Auteurs
Rédaction : Arnaud Bodin
Relecture : Jean-François Barraud
Remerciements à Lionel Rieg pour son tp sur l’algorithme de Karatsuba
69
Deuxième partie
70
Exo7
1 Logique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
1.1 Assertions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
1.2 Quantificateurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
1.3 Mini-exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
2 Raisonnements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
2.1 Raisonnement direct . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
2.2 Cas par cas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
2.3 Contraposée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
2.4 Absurde . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
2.5 Contre-exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
2.6 Récurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
2.7 Mini-exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
■
■
Quelques motivations
– Il est important d’avoir un langage rigoureux. La langue française est souvent ambigüe. Prenons
l’exemple de la conjonction « ou » ; au restaurant « fromage ou dessert » signifie l’un ou l’autre mais
pas les deux. Par contre si dans un jeu de carte on cherche « les as ou les cœurs » alors il ne faut pas
exclure l’as de cœur. Autre exemple : que répondre à la question « As-tu 10 euros en poche ? » si l’on
dispose de 15 euros ?
– Il y a des notions difficiles à expliquer avec des mots : par exemple la continuité d’une fonction est
souvent expliquée par « on trace le graphe sans lever le crayon ». Il est clair que c’est une définition peu
satisfaisante. Voici la définition mathématique de la continuité d’une fonction f : I → R en un point
x0 I :
∀ 0 ∃ 0 ∀ x I (| x − x0 | ⇒ | f (x) − f (x0 )| ).
C’est le but de ce chapitre de rendre cette ligne plus claire ! C’est la logique.
– Enfin les mathématiques tentent de distinguer le vrai du faux. Par exemple « Est-ce qu’une aug-
mentation de 20%, puis de 30% est plus intéressante qu’une augmentation de 50% ? ». Vous pouvez
penser « oui » ou « non », mais pour en être sûr il faut suivre une démarche logique qui mène à la
conclusion. Cette démarche doit être convaincante pour vous mais aussi pour les autres. On parle de
raisonnement.
Les mathématiques sont un langage pour s’exprimer rigoureusement, adapté aux phénomènes com-
plexes, qui rend les calculs exacts et vérifiables. Le raisonnement est le moyen de valider — ou d’infirmer
— une hypothèse et de l’expliquer à autrui.
71
1 Logique
1.1 Assertions
Une assertion est une phrase soit vraie, soit fausse, pas les deux en même temps.
Exemples :
– « Il pleut. »
– « Je suis plus grand que toi. »
– « 2+2 4 »
– « 2×3 7 »
– « Pour tout x R, on a x2 0. »
– « Pour tout z C, on a | z| 1. »
Si P est une assertion et Q est une autre assertion, nous allons définir de nouvelles assertions constru-
ites à partir de P et de Q.
L’opérateur logique « et »
L’assertion « P et Q » est vraie si P est vraie et Q est vraie. L’assertion « P et Q » est fausse sinon.
On résume ceci en une table de vérité :
P \Q V F
V V F
F F F
Par exemple si P est l’assertion « Cette carte est un as » et Q l’assertion « Cette carte est cœur » alors
l’assertion « P et Q » est vraie si la carte est l’as de cœur et est fausse pour toute autre carte.
L’opérateur logique « ou »
L’assertion « P ou Q » est vraie si l’une des deux assertions P ou Q est vraie. L’assertion « P ou Q » est
fausse si les deux assertions P et Q sont fausses.
On reprend ceci dans la table de vérité :
P \Q V F
V V V
F V F
Si P est l’assertion « Cette carte est un as » et Q l’assertion « Cette carte est cœur » alors l’assertion « P ou
Q » est vraie si la carte est un as ou bien un cœur (en particulier elle est vraie pour l’as de cœur).
Remarque. Pour définir les opérateurs « ou », « et » on fait appel à une phrase en français utilisant les
mots ou, et ! Les tables de vérités permettent d’éviter ce problème.
La négation « non »
P V F
non P F V
72
L’implication ⇒
P \Q V F
V V F
F V V
L’équivalence ⇐⇒
« P ⇐⇒ Q » est l’assertion « (P ⇒ Q) et (Q ⇒ P) ».
P \Q V F
V V F
F F V
Exemples :
– Pour x, x′ R, l’équivalence « x · x′ 0 ⇐⇒ (x 0 ou x′ 0) » est vraie.
– Voici une équivalence toujours fausse (quelque soit l’assertion P) : « P ⇐⇒ non(P) ».
On s’intéresse davantage aux assertions vraies qu’aux fausses, aussi dans la pratique et en dehors de
ce chapitre on écrira « P ⇐⇒ Q » ou « P ⇒ Q » uniquement lorsque ce sont des assertions vraies. Par
exemple si l’on écrit « P ⇐⇒ Q » cela sous-entend « P ⇐⇒ Q est vraie ». Attention rien ne dit que P et
Q soient vraies. Cela signifie que P et Q sont vraies en même temps ou fausses en même temps.
Proposition 9.
Soient P,Q, R trois assertions. Nous avons les équivalences (vraies) suivantes :
1. P ⇐⇒ non(non(P))
2. (P et Q) ⇐⇒ (Q et P)
3. (P ou Q) ⇐⇒ (Q ou P)
4. non(P et Q) ⇐⇒ (non P) ou (non Q)
5. non(P ou Q) ⇐⇒ (non P) et (non Q)
6. P et (Q ou R) ⇐⇒ (P et Q) ou (P et R)
7. P ou (Q et R) ⇐⇒ (P ou Q) et (P ou R)
73
8. « P ⇒ Q » ⇐⇒ « non(Q) ⇒ non(P) »
Démonstration. Voici des exemples de démonstrations :
4. Il suffit de comparer les deux assertions « non(P et Q) » et « (non P) ou (non Q) » pour toutes les
valeurs possibles de P et Q. Par exemple si P est vrai et Q est vrai alors « P et Q » est vrai donc
« non(P et Q) » est faux ; d’autre part (non P) est faux, (non Q) est faux donc « (non P) ou (non Q) » est
faux. Ainsi dans ce premier cas les assertions sont toutes les deux fausses. On dresse ainsi les deux
tables de vérités et comme elles sont égales les deux assertions sont équivalentes.
P \Q V F
V F V
F V V
6. On fait la même chose mais il y a trois variables : P, Q, R. On compare donc les tables de vérité
d’abord dans le cas où P est vrai (à gauche), puis dans le cas où P est faux (à droite). Dans les deux
cas les deux assertions « P et (Q ou R) » et « (P et Q) ou (P et R) » ont la même table de vérité donc
les assertions sont équivalentes.
Q\R V F Q\R V F
V V V V F F
F V F F F F
1.2 Quanticateurs
Le quanticateur ∀ : « pour tout »
Une assertion P peut dépendre d’un paramètre x, par exemple « x2 1 », l’assertion P(x) est vraie ou
fausse selon la valeur de x.
L’assertion
∀ x E P(x)
est une assertion vraie lorsque les assertions P(x) sont vraies pour tous les éléments x de l’ensemble E.
On lit « Pour tout x appartenant à E, P(x) », sous-entendu « Pour tout x appartenant à E, P(x) est vraie ».
Par exemple :
– « ∀ x [1, +∞[ (x2 1) » est une assertion vraie.
– « ∀ x R (x2 1) » est une assertion fausse.
– « ∀ n N n(n + 1) est divisible par 2 » est vraie.
Le quanticateur ∃ : « il existe »
L’assertion
∃x E P(x)
est une assertion vraie lorsque l’on peut trouver au moins un x de E pour lequel P(x) est vraie. On lit
« il existe x appartenant à E tel que P(x) (soit vraie) ».
Par exemple :
– « ∃ x R (x(x − 1) 0) » est vraie (par exemple x 12 vérifie bien la propriété).
– « ∃ n N n2 − n n » est vraie (il y a plein de choix, par exemple n 3 convient, mais aussi n 10 ou
même n 100, un seul suffit pour dire que l’assertion est vraie).
– « ∃ x R (x2 −1) » est fausse (aucun réel au carré ne donnera un nombre négatif).
74
La négation des quanticateurs
Par exemple la négation de « ∀ x [1, +∞[ (x2 1) » est l’assertion « ∃ x [1, +∞[ (x2 1) ». En effet la
négation de x2 1 est non(x2 1) mais s’écrit plus simplement x2 1.
∀x R ∃y 0 (x + y 10)
sa négation est
∃x R ∀y 0 (x + y … 10).
Remarques
L’ordre des quantificateurs est très important. Par exemple les deux phrases logiques
∀x R ∃y R (x + y 0) et ∃y R ∀x R (x + y 0).
sont différentes. La première est vraie, la seconde est fausse. En effet une phrase logique se lit de gauche
à droite, ainsi la première phrase affirme « Pour tout réel x, il existe un réel y (qui peut donc dépendre de
x) tel que x + y 0. » (par exemple on peut prendre y x + 1). C’est donc une phrase vraie. Par contre la
deuxième se lit : « Il existe un réel y, tel que pour tout réel x, x + y 0. » Cette phrase est fausse, cela ne
peut pas être le même y qui convient pour tous les x !
On retrouve la même différence dans les phrases en français suivantes. Voici une phrase vraie « Pour
toute personne, il existe un numéro de téléphone », bien sûr le numéro dépend de la personne. Par contre
cette phrase est fausse : « Il existe un numéro, pour toutes les personnes ». Ce serait le même numéro
pour tout le monde !
– Pour la négation d’une phrase logique, il n’est pas nécessaire de savoir si la phrase est fausse ou vraie.
Le procédé est algorithmique : on change le « pour tout » en « il existe » et inversement, puis on prend
la négation de l’assertion P.
– Pour la négation d’une proposition, il faut être précis : la négation de l’inégalité stricte « » est l’iné-
galité large « », et inversement.
– Les quantificateurs ne sont pas des abréviations. Soit vous écrivez une phrase en français : « Pour
tout réel x, si f (x) 1 alors x 0. » , soit vous écrivez la phrase logique :
∀x R ( f (x) 1 ⇒ x 0).
Mais surtout n’écrivez pas « ∀ x réel, si f (x) 1 ⇒ x positif ou nul ». Enfin, pour passer d’une ligne
à l’autre d’un raisonnement, préférez plutôt « donc » à « ⇒ ».
– Il est défendu d’écrire 6 ∃, 6⇒ . Ces symboles n’existent pas !
75
1.3 Mini-exercices
1. Écrire la table de vérité du « ou exclusif ». (C’est le ou dans la phrase « fromage ou dessert », l’un
ou l’autre mais pas les deux.)
2. Écrire la table de vérité de « non (P et Q) ». Que remarquez vous ?
3. Écrire la négation de « P ⇒ Q ».
4. Démontrer les assertions restantes de la proposition 9.
5. Écrire la négation de « P et (Q ou R) ».
6. Écrire à l’aide des quantificateurs la phrase suivante : « Pour tout nombre réel, son carré est posi-
tif ». Puis écrire la négation.
7. Mêmes questions avec les phrases : « Pour chaque réel, je peux trouver un entier relatif tel que leur
produit soit strictement plus grand que 1 ». Puis « Pour tout entier n, il existe un unique réel x tel
que exp(x) égale n ».
2 Raisonnements
Voici des méthodes classiques de raisonnements.
Démonstration. Prenons a Q, b Q. Rappelons que les rationnels Q sont l’ensemble des réels s’écrivant
p ∗
q avec p Z et q N .
p p′
Alors a q pour un certain p Z et un certain q N∗ . De même b q′ avec p′ Z et q′ N∗ . Maintenant
p p′ pq′ + q p′
a+b + .
q q′ qq′
Or le numérateur pq′ + q p′ est bien un élément de Z ; le dénominateur qq′ est lui un élément de N∗ .
p′′
Donc a + b s’écrit bien de la forme a + b q′′ avec p′′ Z, q′′ N∗ . Ainsi a + b Q.
x2 − x + 1 − | x − 1| x2 − x + 1 − (x − 1)
x2 − 2x + 2
(x − 1)2 + 1 0.
76
2.3 Contraposée
Le raisonnement par contraposition est basé sur l’équivalence suivante (voir la proposition 9) :
Donc si l’on souhaite montrer l’assertion « P ⇒ Q », on montre en fait que si non(Q) est vraie alors
non(P) est vraie.
Exemple 21. Soit n N. Montrer que si n2 est pair alors n est pair.
Démonstration. Nous supposons que n n’est pas pair. Nous voulons montrer qu’alors n2 n’est pas pair.
Comme n n’est pas pair, il est impair et donc il existe k N tel que n 2k + 1. Alors n2 (2k + 1)2
4k2 + 4k + 1 2` + 1 avec ` 2k2 + 2k N. Et donc n2 est impair.
Conclusion : nous avons montré que si n est impair alors n2 est impair. Par contraposition ceci est
équivalent à : si n2 est pair alors n est pair.
2.4 Absurde
Le raisonnement par l’absurde pour montrer « P ⇒ Q » repose sur le principe suivant : on suppose
à la fois que P est vraie et que Q est fausse et on cherche une contradiction. Ainsi si P est vraie alors Q
doit être vraie et donc « P ⇒ Q » est vraie.
a b
Exemple 22. Soient a, b 0. Montrer que si 1+ b 1+ a alors a b.
Démonstration. Nous raisonnons par l’absurde en supposant que 1+a b 1+b a et a 6 b. Comme 1+a b 1+b a
alors a(1 + a) b(1 + b) donc a + a2 b + b2 d’où a2 − b2 b − a. Cela conduit à (a − b)(a + b) −(a − b).
Comme a 6 b alors a − b 6 0 et donc en divisant par a − b on obtient a + b −1. La somme de deux
nombres positifs ne peut être négative. Nous obtenons une contradiction.
Conclusion : si 1+a b 1+b a alors a b.
Dans la pratique, on peut choisir indifféremment entre un raisonnement par contraposition ou par
l’absurde. Attention cependant de bien écrire quel type de raisonnement vous choisissez et surtout de
ne pas changer en cours de rédaction !
2.5 Contre-exemple
Si l’on veut montrer qu’une assertion du type « ∀ x E P(x) » est vraie alors pour chaque x de E il
faut montrer que P(x) est vraie. Par contre pour montrer que cette assertion est fausse alors il suffit
de trouver x E tel que P(x) soit fausse. (Rappelez-vous la négation de « ∀ x E P(x) » est « ∃ x
E non P(x) »). Trouver un tel x c’est trouver un contre-exemple à l’assertion « ∀ x E P(x) ».
Exemple 23. Montrer que l’assertion suivante est fausse « Tout entier positif est somme de trois carrés ».
(Les carrés sont les 02 , 12 , 22 , 32 ,... Par exemple 6 22 + 12 + 12 .)
Démonstration. Un contre-exemple est 7 : les carrés inférieurs à 7 sont 0, 1, 4 mais avec trois de ces
nombres on ne peut faire 7.
2.6 Récurrence
Le principe de récurrence permet de montrer qu’une assertion P(n), dépendant de n, est vraie pour
tout n N. La démonstration par récurrence se déroule en trois étapes : lors de l’initialisation on
prouve P(0). Pour l’étape d’hérédité, on suppose n 0 donné avec P(n) vraie, et on démontre alors que
l’assertion P(n + 1) au rang suivant est vraie. Enfin dans la conclusion, on rappelle que par le principe
de récurrence P(n) est vraie pour tout n N.
77
Démonstration. Pour n 0, notons P(n) l’assertion suivante :
2n n.
Nous allons démontrer par récurrence que P(n) est vraie pour tout n 0.
Initialisation. Pour n 0 nous avons 20 1 0. Donc P(0) est vraie.
Hérédité. Fixons n 0. Supposons que P(n) soit vraie. Nous allons montrer que P(n + 1) est vraie.
2 n +1 2 n + 2 n
n + 2n car par P(n) nous savons 2n n,
n+1 car 2n 1.
Remarques :
– La rédaction d’une récurrence est assez rigide. Respectez scrupuleusement la rédaction proposée :
donnez un nom à l’assertion que vous souhaitez montrer (ici P(n)), respectez les trois étapes (même si
souvent l’étape d’initialisation est très facile). En particulier méditez et conservez la première ligne de
l’hérédité « Fixons n 0. Supposons que P(n) soit vraie. Nous allons montrer que P(n + 1) est vraie. »
– Si on doit démontrer qu’une propriété est vraie pour tout n n 0 , alors on commence l’initialisation
au rang n 0 .
– Le principe de récurrence est basé sur la construction de N. En effet un des axiomes pour définir N
est le suivant : « Soit A une partie de N qui contient 0 et telle que si n A alors n + 1 A. Alors A N ».
2.7 Mini-exercices
a+ b
p
1. (Raisonnement direct) Soient a, b R+ . Montrer que si a … b alors a … 2 … b et a … ab … b.
2. (Cas par cas) Montrer que pour tout n N, n(n + 1) est divisible par 2 (distinguer les n pairs des n
impairs).
p
3. p
(Contraposée ou absurde) Soient a, b Z. Montrer que si b 6 0 alors a + b 2 Q. (On utilisera que
2 Q.)
p
4. (Absurde) Soit n N∗ . Montrer que n2 + 1 n’est pas un entier.
5. (Contre-exemple) Est-ce que pour tout x R on a x 2 ⇒ x2 4 ?
n( n+1)
6. (Récurrence) Montrer que pour tout n 1, 1 + 2 + · · · + n 2 .
7. (Récurrence) Fixons un réel x 0. Montrer que pour tout entier n 1, (1 + x)n 1 + nx.
Auteurs
Arnaud Bodin
Benjamin Boutin
Pascal Romon
78
Exo7
1 Ensembles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
1.1 Définir des ensembles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
1.2 Inclusion, union, intersection, complémentaire . . . . . . . . . . . . . . . . . . . . . . 81
1.3 Règles de calculs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
1.4 Produit cartésien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
1.5 Mini-exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
2 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
2.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
2.2 Image directe, image réciproque . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
2.3 Antécédents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
2.4 Mini-exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
3 Injection, surjection, bijection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
3.1 Injection, surjection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
3.2 Bijection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
3.3 Mini-exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
4 Ensembles nis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
4.1 Cardinal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
4.2 Injection, surjection, bijection et ensembles finis . . . . . . . . . . . . . . . . . . . . . 88
4.3 Nombres d’applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.4 Nombres de sous-ensembles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
4.5 Coefficients du binôme de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
4.6 Formule du binôme de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
4.7 Mini-exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
5 Relation d’équivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
5.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
5.2 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5.3 Classes d’équivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5.4 L’ensemble Z/ nZ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
5.5 Mini-exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
■
■
■
■
■
79
Motivations
Au début du XXe siècle le professeur Frege peaufinait la rédaction du second tome d’un ouvrage qui
souhaitait refonder les mathématiques sur des bases logiques. Il reçut une lettre d’un tout jeune math-
ématicien : « J’ai bien lu votre premier livre. Malheureusement vous supposez qu’il existe un ensemble
qui contient tous les ensembles. Un tel ensemble ne peut exister. » S’ensuit une démonstration de deux
lignes. Tout le travail de Frege s’écroulait et il ne s’en remettra jamais. Le jeune Russell deviendra l’un
des plus grands logiciens et philosophes de sont temps. Il obtient le prix Nobel de littérature en 1950.
Voici le « paradoxe de Russell » pour montrer que l’ensemble de tous les ensembles ne peut exister. C’est
très bref, mais difficile à appréhender. Par l’absurde, supposons qu’un tel ensemble E contenant tous les
ensembles existe. Considérons
F EE |EE .
Expliquons l’écriture E E : le E de gauche est considéré comme un élément, en effet l’ensemble E
est l’ensemble de tous les ensembles et E est un élément de cet ensemble ; le E de droite est considéré
comme un ensemble, en effet les élément de E sont des ensembles ! On peut donc s’interroger si l’élément
E appartient à l’ensemble E. Si non, alors par définition on met E dans l’ensemble F.
La contradiction arrive lorsque l’on se pose la question suivante : a-t-on F F ou F F ? L’une des deux
affirmation doit être vraie. Et pourtant :
– Si F F alors par définition de F, F est l’un des ensembles E tel que F F. Ce qui est contradictoire.
– Si F F alors F vérifie bien la propriété définissant F donc F F ! Encore contradictoire.
Aucun des cas n’est possible. On en déduit qu’il ne peut exister un tel ensemble E contenant tous les
ensembles.
Ce paradoxe a été popularisé par l’énigme suivante : « Dans une ville, le barbier rase tous ceux qui ne se
rasent pas eux-mêmes. Qui rase le barbier ? » La seule réponse valable est qu’une telle situation ne peut
exister.
Ne vous inquiétez pas, Russell et d’autres ont fondé la logique et les ensembles sur des bases solides.
Cependant il n’est pas possible dans ce cours de tout redéfinir. Heureusement, vous connaissez déjà
quelques ensembles :
– l’ensemble des entiers naturels N {0, 1, 2, 3, . . .}.
– l’ensemble des entiers relatifs Z {. . . , −2, −1, 0, 1, 2, . . .}.
p }
– l’ensemble des rationnels Q q | p Z, q N \ {0} .
p
– l’ensemble des réels R, par exemple 1, 2, π, ln(2),. . .
– l’ensemble des nombres complexes C.
Nous allons essayer de voir les propriétés des ensembles, sans s’attacher à un exemple particulier. Vous
vous apercevrez assez rapidement que ce qui est au moins aussi important que les ensembles, ce sont
les relations entre ensembles : ce sera la notion d’application (ou fonction) entre deux ensembles.
1 Ensembles
80
1.2 Inclusion, union, intersection, complémentaire
– L’inclusion. E ⊂ F si tout élément de E est aussi un élément de F (autrement dit : ∀ x E (x F)). On
dit alors que E est un sous-ensemble de F ou une partie de F.
– L’égalité. E F si et seulement si E ⊂ F et F ⊂ E.
– Ensemble des parties de E. On note P (E) l’ensemble des parties de E. Par exemple si E {1, 2, 3} :
}
P ({1, 2, 3}) ∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} .
– Complémentaire. Si A ⊂ E,
}
ŸE A x E | x A
On le note aussi E \ A et juste Ÿ A s’il n’y a pas d’ambiguïté (et parfois aussi A c ou A).
E A ŸE A
– Union. Pour A, B ⊂ E,
}
A B x E | x A ou x B
A AB B
– Intersection. }
A B x E | x A et x B
A AB B
81
ŸA ŸB
A B A B
Ÿ(A B) Ÿ A ŸB Ÿ(A B) Ÿ A ŸB
A AB B A AB B
Les preuves sont pour l’essentiel une reformulation des opérateurs logiques, en voici quelques-unes :
– Preuve de A (B C) (A B)(A C) : x A (B C) ⇐⇒ x A et x (B C) ⇐⇒ x A et (x B ou x
C) ⇐⇒ (x A et x B) ou (x A et x C) ⇐⇒ (x A B) ou (x A C) ⇐⇒ x (A B) (A C).
– Preuve de Ÿ (A B) Ÿ A ŸB : x Ÿ (A B) ⇐⇒ x (A B) ⇐⇒ non x A B ⇐⇒ non x A et x
B ⇐⇒ non(x A) ou non(x B) ⇐⇒ x A ou x B ⇐⇒ x Ÿ A ŸB.
Remarquez que l’on repasse aux éléments pour les preuves.
Exemple 25.
}
1. Vous connaissez R2 R × R (x, y) | x, y R .
}
2. Autre exemple [0, 1] × R (x, y) | 0 … x … 1, y R
y
x
0 1
}
3. [0, 1] × [0, 1] × [0, 1] (x, y, z) | 0 … x, y, z … 1
y
z
1
1
0 1 x
1.5 Mini-exercices
1. En utilisant les définitions, montrer : A 6 B si et seulement s’il existe a A \ B ou b B \ A.
2. Énumérer P ({1, 2, 3, 4}).
3. Montrer A (B C) (A B) (A C) et Ÿ (A B) Ÿ A ŸB.
82
4. Énumérer {1, 2, 3} × {1, 2, 3, 4}.
5. Représenter les sous-ensembles de R2 suivants : ]0, 1[[2, 3[ × [−1, 1], R \ (]0, 1[[2, 3[ × (R \
[−1, 1]) [0, 2] .
2 Applications
2.1 Dénitions
– Une application (ou une fonction) f : E → F, c’est la donnée pour chaque élément x E d’un unique
élément de F noté f (x).
Nous représenterons les applications par deux types d’illustrations : les ensembles «patates», l’ensem-
ble de départ (et celui d’arrivée) est schématisé par un ovale ses éléments par des points. L’association
x 7→ f (x) est représentée par une flèche.
f
x f (x)
E F
L’autre représentation est celle des fonctions continues de R dans R (ou des sous-ensembles de R).
L’ensemble de départ R est représenté par l’axe des abscisses et celui d’arrivée par l’axe des ordonnées.
L’association x 7→ f (x) est représentée par le point (x, f (x)).
y
f (x)
x
x
– Égalité. Deux applications f , g : E → F sont égales si et seulement si pour tout x E, f (x) g(x). On
note alors f g.
– Le graphe de f : E → F est
Γ f x, f (x) E × F | x E
Γf
E −−−−→ F −−−−→ G
g◦ f
Exemple 26.
1. L’identité, idE : E → E est simplement définie par x 7→ x et sera très utile dans la suite.
2. Définissons f , g ainsi
83
Alors g ◦ f : ]0, +∞[→ R vérifie pour tout x ]0, +∞[ :
1
1 x −1 1− x
g ◦ f (x) g f (x) g 1
− g(x).
x +1 1+ x
x
y
f
E F
A f (A)
f (A)
x
A
f
E F y
B
B
x
f −1 (B) f −1 (B)
Remarque. Ces notions sont plus difficiles à maîtriser qu’il n’y paraît !
– f (A) est un sous-ensemble de F, f −1 (B) est un sous-ensemble de E.
– La notation « f −1 (B)» est un tout, rien ne dit que f est un fonction bijective (voir plus loin). L’image
réciproque existe quelque soit la fonction.
}
– L’image directe d’un singleton f ({ x}) f (x) est un singleton. Par contre l’image réciproque d’un
singleton f −1 { y} dépend de f . Cela peut être un singleton, un ensemble à plusieurs éléments ; mais
cela peut-être E tout entier (si f est une fonction constante) ou même l’ensemble vide (si aucune
image par f ne vaut y).
2.3 Antécédents
Fixons y F. Tout élément x E tel que f (x) y est un antécédent de y.
En termes d’image réciproque l’ensemble des antécédents de y est f −1 ({ y}).
f
y
E x3 F
x1 x2 y y
x
x1 x2 x3
84
2.4 Mini-exercices
1. Pour deux applications f , g : E → F, quelle est la négation de f g ?
4
2. Représenter le graphe de f : N → R définie par n 7→ n +1 .
3. Soient f , g, h : R → R définies par f (x) x2 , g(x) 2x + 1, h(x) x3 − 1. Calculer f ◦ (g ◦ h) et ( f ◦ g) ◦ h.
4. Pour la fonction f : R → R définie par x 7→ x2 représenter et calculer les ensembles suivants :
f ([0, 1[), f (R), f (] − 1, 2[), f −1 ([1, 2[), f −1 ([−1, 1]), f −1 ({3}), f −1 (R \ N).
Dénition 11. f est surjective si pour tout y F, il existe x E tel que y f (x). Autrement dit :
∀ y F ∃x E y f (x)
)
E F F
x
E
E F F
x
E
Remarque. Encore une fois ce sont des notions difficiles à appréhender. Une autre façon de formuler
l’injectivité et la surjectivité est d’utiliser les antécédents.
– f est injective si et seulement si tout élément y de F a au plus 1 antécédent (et éventuellement
aucun).
– f est surjective si et seulement si tout élément y de F a au moins 1 antécédent.
Remarque. Voici deux fonctions non injectives :
f
y
E F
x
x′ y y
x
x x′
85
Ainsi que deux fonctions non surjectives :
f y
F
)
y
E F
x
E
Exemple 27.
1. Soit f 1 : N → Q définie par f 1 (x) 1+1 x . Montrons que f 1 est injective : soit x, x′ N tels que f 1 (x)
f 1 (x′ ). Alors 1+1 x 1+1x′ , donc 1 + x 1 + x′ et donc x x′ . Ainsi f 1 est injective.
Par contre f 1 n’est pas surjective. Il s’agit de trouver un élément y qui n’a pas d’antécédent par f 1 .
Ici il est facile de voir que l’on a toujours f 1 (x) … 1 et donc par exemple y 2 n’a pas d’antécédent.
Ainsi f 1 n’est pas surjective.
2. Soit f 2 : Z → N définie par f 2 (x) x2 . Alors f 2 n’est pas injective. En effet on peut trouver deux
éléments x, x′ Z différents tels que f 2 (x) f 2 (x′ ). Il suffit de prendre par exemple x 2, x′ −2.
f 2 n’est pas non plus surjective, en effet il existe des éléments y N qui n’ont aucun antécédent.
2
Par exemplep y 3 : si y 3 avait un antécédent x par f 2 , nous aurions f 2 (x) y, c’est-à-dire x 3,
d’où x ± 3. Mais alors x n’est pas un entier de Z. Donc y 3 n’a pas d’antécédent et f 2 n’est pas
surjective.
3.2 Bijection
Dénition 12. f est bijective si elle injective et surjective. Cela équivaut à : pour tout y F il existe
un unique x E tel que y f (x). Autrement dit :
∀y F ∃!x E y f (x)
f y
E F F
x
E
Proposition 10.
Soit E, F des ensembles et f : E → F une application.
1. L’application f est bijective si et seulement si il existe une application g : F → E telle que f ◦ g idF
et g ◦ f idE .
2. Si f est bijective alors l’application g est unique et elle aussi est bijective. L’application g s’appelle
−1
la bijection réciproque de f et est notée f −1 . De plus f −1 f.
Remarque.
– f ◦ g idF se reformule ainsi
∀y F f g(y) y.
– Alors que g ◦ f idE s’écrit :
∀x E g f (x) x.
86
– Par exemple f : R →]0, +∞[ définie par f (x) exp(x) est bijective, sa bijection réciproque est g :
]0, +∞[→ R définie par g(y) ln(y). Nous avons bien exp ln(y) y, pour tout y ]0, +∞[ et ln exp(x)
x, pour tout x R.
Démonstration.
1. – Sens ⇒. Supposons f bijective. Nous allons construire une application g : F → E. Comme f est
surjective alors pour chaque y F, il existe un x E tel que y f (x) et on pose g(y) x. On
a f g(y) f (x) y, ceci pour tout y F et donc f ◦ g idF . On compose à droite avec f donc
f ◦ g ◦ f idF ◦ f . Alors pour tout x E on a f g ◦ f (x) f (x) or f est injective et donc g ◦ f (x) x.
Ainsi g ◦ f idE . Bilan : f ◦ g idF et g ◦ f idE .
– Sens ⇐. Supposons que g existe et montrons que f est bijective.
– f est surjective : en effet soit y F alors on note x g(y) E ; on a bien : f (x) f g(y)
f ◦ g(y) idF (y) y, donc f est bien surjective.
– f est injective : soient x, x′ E tels que f (x) f (x′ ). On compose par g (à gauche) alors g ◦ f (x)
g ◦ f (x′ ) donc idE (x) idE (x′ ) donc x x′ ; f est bien injective.
2. – Si f est bijective alors g est aussi bijective car g ◦ f idE et f ◦ g idF et on applique ce que l’on
vient de démontrer avec g à la place de f . Ainsi g−1 f .
– Si f est bijective, g est unique : en effet soit h : F → E une autre application telle que h ◦ f idE
et f ◦ h idF ; en particulier f ◦ h idF f ◦ g, donc pour tout y F, f h(y) f g(y) or f est
injective alors h(y) g(y), ceci pour tout y F ; d’où h g.
Proposition 11.
Soient f : E → F et g : F → G des applications bijectives. L’application g ◦ f est bijective et sa bijection
réciproque est
(g ◦ f )−1 f −1 ◦ g−1
Démonstration. D’après la proposition 10, il existe u : F → E tel que u ◦ f idE et f ◦ u idF . Il existe
aussi v : G → F tel que v◦ g idF et g◦v idG . On a alors (g◦ f )◦(u◦v) g◦( f ◦ u)◦v g◦idF ◦ u g◦ u idE .
Et (u ◦ v) ◦ (g ◦ f ) u ◦ (v ◦ g) ◦ f u ◦ idF ◦ f u ◦ f idE . Donc g ◦ f est bijective et son inverse est u ◦ v.
Comme u est la bijection réciproque de f et v celle de g alors : u ◦ v f −1 ◦ g−1 .
3.3 Mini-exercices
1. Les fonctions suivantes sont-elles injectives, surjectives, bijectives ?
– f 1 : R → [0, +∞[, x 7→ x2 .
– f 2 : [0, +∞[→ [0, +∞[, x 7→ x2 .
– f 3 : N → N, x 7→ x2 .
– f 4 : Z → Z, x 7→ x − 7.
– f 5 : R → [0, +∞[, x 7→ | x|.
1
2. Montrer que la fonction f : ]1, +∞[→]0, +∞[ définie par f (x) x −1 est bijective. Calculer sa bijec-
tion réciproque.
4 Ensembles nis
4.1 Cardinal
Dénition 13. Un ensemble E est fini s’il existe un entier n N et une bijection de E vers {1, 2, . . . , n}.
Cet entier n est unique et s’appelle le cardinal de E (ou le nombre d’éléments) et est noté Card E.
Quelques exemples :
1. E {rouge, noir} est en bijection avec {1, 2} et donc est de cardinal 2.
87
2. N n’est pas un ensemble fini.
3. Par définition le cardinal de l’ensemble vide est 0.
Enfin quelques propriétés :
1. Si A est un ensemble fini et B ⊂ A alors B est un ensemble fini et Card B … Card A.
2. Si A, B sont des ensembles finis disjoints (c’est-à-dire A B ∅) alors Card(A B) Card A +
Card B.
3. Si A est un ensemble fini et B ⊂ A alors Card(A \ B) Card A − Card B.
4. Enfin pour A, B deux ensembles finis quelconques :
Card(A B) Card A + Card B − Card(A B)
Démonstration.
1. Supposons f injective. Notons F ′ f (E) ⊂ F alors la restriction f | : E → F ′ (définie par f | (x) f (x))
est une bijection. Donc pour chaque y F ′ est associé un unique x E tel que y f (x). Donc E
et F ′ ont le même nombre d’éléments. Donc Card F ′ Card E. Or F ′ ⊂ F, ainsi Card E Card F ′ …
Card F.
2. Supposons f surjective. Pour tout élément y F, il existe au moins un élément x de E tel que
y f (x) et donc Card E Card F.
3. Cela découle de (1) et (2) (ou aussi de la preuve du (1)).
Proposition 13.
Soit E, F deux ensembles finis et f : E → F une application. Si
Card E Card F
Démonstration. Le schéma de la preuve est le suivant : nous allons montrer successivement les impli-
cations :
(i) ⇒ (ii) ⇒ (iii) ⇒ (i)
ce qui prouvera bien toutes les équivalences.
88
– (i) ⇒ (ii). Supposons f injective. Alors Card f (E) Card E Card F. Ainsi f (E) est un sous-ensemble
de F ayant le même cardinal que F ; cela entraîne f (E) F et donc f est surjective.
– (ii) ⇒ (iii). Supposons f surjective. Pour montrer que f est bijective, il reste à montrer que f est
injective. Raisonnons par l’absurde et supposons f non injective. Alors Card f (E) Card E (car au
moins 2 éléments ont la même image). Or f (E) F car f surjective, donc Card F Card E. C’est une
contradiction, donc f doit être injective et ainsi f est bijective.
– (iii) ⇒ (i). C’est clair : une fonction bijective est en particulier injective.
Proposition 14.
Si l’on range dans k tiroirs, n k paires de chaussettes alors il existe (au moins) un tiroir contenant (au
moins) deux paires de chaussettes.
Malgré sa formulation amusante, c’est une proposition souvent utile. Exemple : dans un amphi de 400
étudiants, il y a au moins deux étudiants nés le même jour !
Proposition 15.
Le nombre d’applications différentes de E dans F est :
pn
Exemple 28. En particulier le nombre d’applications de E dans lui-même est n n . Par exemple si E
{1, 2, 3, 4, 5} alors ce nombre est 55 3125.
Démonstration. Fixons F et p Card F. Nous allons effectuer une récurrence sur n Card E. Soit (P n )
l’assertion suivante : le nombre d’applications d’un ensemble à n éléments vers un ensemble à p élé-
ments est p n .
– Initialisation. Pour n 1, une application de E dans F est définie par l’image de l’unique élément de
E. Il y a p Card F choix possibles et donc p1 applications distinctes. Ainsi P1 est vraie.
– Hérédité. Fixons n 1 et supposons que P n est vraie. Soit E un ensemble à n + 1 éléments. On choisit
et fixe a E ; soit alors E ′ E \ {a} qui a bien n éléments. Le nombre d’applications de E ′ vers F est
p n , par l’hypothèse de récurrence (P n ). Pour chaque application f : E ′ → F on peut la prolonger en
une application f : E → F en choisissant l’image de a. On a p choix pour l’image de a et donc p n × p
choix pour les applications de E vers F. Ainsi P n+1 est vérifiée.
– Conclusion. Par le principe de récurrence P n est vraie, pour tout n 1.
Proposition 16.
Le nombre d’injections de E dans F est :
p × (p − 1) × · · · × (p − (n − 1)).
Démonstration. Supposons E {a 1 , a 2 , . . . , a n } ; pour l’image de a 1 nous avons p choix. Une fois ce choix
fait, pour l’image de a 2 il reste p − 1 choix (car a 2 ne doit pas avoir la même image que a 1 ). Pour l’image
de a 3 il y a p − 2 possibilités. Ainsi de suite : pour l’image de a k il y p − (k − 1) choix... Il y a au final
p × (p − 1) × · · · × (p − (n − 1)) applications injectives.
89
Proposition 17.
Le nombre de bijections d’un ensemble E de cardinal n dans lui-même est :
n!
Exemple 29. Parmi les 3125 applications de {1, 2, 3, 4, 5} dans lui-même il y en a 5! 120 qui sont
bijectives.
Démonstration. Nous allons le prouver par récurrence sur n. Soit (P n ) l’assertion suivante : le nombre
de bijections d’un ensemble à n éléments dans un ensemble à n éléments est n!
– P1 est vraie. Il n’y a qu’une bijection d’un ensemble à 1 élément dans un ensemble à 1 élément.
– Fixons n 1 et supposons que P n est vraie. Soit E un ensemble à n + 1 éléments. On fixe a E.
Pour chaque b E il y a -par l’hypothèse de récurrence- exactement n! applications bijectives de
E \ {a} → E \ { b}. Chaque application se prolonge en une bijection de E → F en posant a 7→ b. Comme
il y a n + 1 choix de b E alors nous obtenons n! × (n + 1) bijections de E dans lui-même. Ainsi P n+1
est vraie.
– Par le principe de récurrence le nombre de bijections d’un ensemble à n éléments est n!
On aurait aussi pu directement utiliser la proposition 16 avec n p (sachant qu’alors les injections sont
aussi des bijections).
Proposition 18.
Il y a 2Card E sous-ensembles de E :
Card P (E) 2n
Exemple 30. Si E {1, 2, 3, 4, 5} alors P (E) a 25 32 parties. C’est un bon exercice de les énumérer :
– l’ensemble vide : ∅,
– 5 singletons : {1}, {2}, . . .,
– 10 paires : {1, 2}, {1, 3}, . . . , {2, 3}, . . .,
– 10 triplets : {1, 2, 3}, . . .,
– 5 ensembles à 4 éléments : {1, 2, 3, 4}, {1, 2, 3, 5}, . . .,
– et E tout entier : {1, 2, 3, 4, 5}.
90
5
– 5 (il y a 5 singletons),
15
– 10 (il y a 10 paires),
25
– 10,
35
– 5,
45
– 5 1 (la seule partie ayant 5 éléments est l’ensemble tout entier).
Proposition 19.
– n0 1, n1 n, nn 1.
n n
– n− k k
n n n n n
– 0 + 1 +···+ k +···+ n 2
Démonstration.
n
1. Par exemple : 1 n car il y a n singletons.
2. Compter le nombre de parties A ⊂ E ayant k éléments revient aussi à compter le nombre de
n n
parties de la forme Ÿ A (qui ont donc n − k éléments), ainsi n− k k .
n n n n n
3. La formule 0 + 1 + · · · + k + · · · + n 2 exprime que faire la somme du nombre de parties à k
éléments, pour k 0, . . . , n, revient à compter toutes les parties de E.
Proposition 20.
n n−1 n−1
+ 0kn
k k k−1
1 1
1 1 1 1
1 2 1 1 2 1
1 3 3 1 1 3 3 1
1 4 6 4 1 1 4 6 4 1
1 5 10 10 5 1
91
Ce qui fait que cela fonctionne c’est bien sûr la proposition 20 qui se représente ainsi :
n −1 n −1
k −1 k
n
k
Une autre façon de calculer le coefficient du binôme de Newton repose sur la formule suivante :
Proposition 21.
n n!
k k!(n − k)!
Démonstration. Cela se fait par récurrence sur n. C’est clair pour n 1. Si c’est vrai au rang n − 1 alors
−1 n −1 −1 n −1
écrivons nk nk− 1 + k et utilisons l’hypothèse de récurrence pour nk− 1 et k . Ainsi
n n−1 n−1 (n − 1)! (n − 1)!
+ +
k k−1 k (k − 1)!(n − 1 − (k − 1))! k!(n − 1 − k)!
(n − 1)! 1 1 (n − 1)! n
× + ×
(k − 1)!(n − k − 1)! n−k k (k − 1)!(n − k − 1)! k(n − k)
n!
k!(n − k)!
Autrement dit :
n n n 0 n n −1 1 n n− k k n 0 n
(a + b) a ·b + a · b +···+ a · b +···+ a ·b
0 1 k n
Exemple 32.
92
– Hérédité. Fixons n 2 et supposons que P n−1 est vraie.
n n −1 n −1 n − 1 n −1− k k n −1
(a + b) (a + b) · (a + b) a a +···+ a b +···+ b
k
n −1 n − 1 n−1−(k−1) k−1 n −1
+b a +···+ a b +···+ b
k−1
n−1 n−1
···+ + a n− k b k + · · ·
k k−1
n n− k k ∑ n n
···+ a b +··· a n− k · b k
k k 0 k
4.7 Mini-exercices
1. Combien y a-t-il d’applications injectives d’un ensemble à n éléments dans un ensemble à n + 1
éléments ?
2. Combien y a-t-il d’applications surjectives d’un ensemble à n + 1 éléments dans un ensemble à n
éléments ?
3. Calculer le nombre de façons de choisir 5 cartes dans un jeux de 32 cartes.
4. Calculer le nombre de listes à k éléments dans un ensemble à n éléments (les listes sont ordon-
nées : par exemple (1, 2, 3) 6 (1, 3, 2)).
5. Développer (a − b)4 , (a + b)5 .
6. Que donne la formule du binôme pour a −1, b +1 ? En déduire que dans un ensemble à n
éléments il y a autant de parties de cardinal pair que de cardinal impair.
5 Relation d’équivalence
5.1 Dénition
Une relation sur un ensemble E, c’est la donnée pour tout couple (x, y) E × E de «Vrai» (s’ils sont en
relation), ou de «Faux» sinon.
Nous schématisons une relation ainsi : les éléments de E sont des points, une flèche de x vers y signifie
que x est en relation avec y, c’est-à-dire que l’on associe «Vrai» au couple (x, y).
Dénition 15. Soit E un ensemble et R une relation, c’est une relation d’équivalence si :
– ∀ x E, xR x, (réflexivité)
x
– ∀ x, y E, xR y ⇒ yR x, (symétrie)
x y
93
– ∀ x, y, z E, xR y et yR z ⇒ xR z, (transitivité)
y
z
x
5.2 Exemples
Exemple 33. Voici des exemples basiques.
1. La relation R «être parallèle» est une relation d’équivalence pour l’ensemble E des droites affines
du plan.
– réflexivité : une droite est parallèle à elle-même,
– symétrie : si D est parallèle à D ′ alors D ′ est parallèle à D,
– transitivité : si D parallèle à D ′ et D ′ parallèle à D ′′ alors D est parallèle à D ′′ .
2. La relation «être du même âge» est une relation d’équivalence.
3. La relation «être perpendiculaire» n’est pas une relation d’équivalence (ni la réflexivité, ni la tran-
sitivité ne sont vérifiées).
4. La relation … (sur E R par exemple) n’est pas une relation d’équivalence (la symétrie n’est pas
vérifiée).
x′
cl(x)
x
cl(x′ )
cl(x) est donc un sous-ensemble de E, on le note aussi x. Si y cl(x), on dit que y un représentant de
cl(x).
Soit E un ensemble et R une relation d’équivalence.
Proposition 22.
On a les propriétés suivantes :
94
1. cl(x) cl(y) ⇐⇒ xR y.
2. Pour tout x, y E, cl(x) cl(y) ou cl(x) cl(y) ∅.
}
3. Soit C un ensemble de représentants de toutes les classes alors cl(x) | x C constitue une parti-
tion de E.
⋃
Une partition de E est un ensemble {E i } de parties de E tel que E i E i et E i E j ∅ (si i 6 j).
E
...
E2
E1 Ei ...
Ej ...
Exemples :
1. Pour la relation «être du même âge», la classe d’équivalence d’une personne est l’ensemble des
personnes ayant le même âge. Il y a donc une classe d’équivalence formée des personnes de 19
ans, une autre formée des personnes de 20 ans,... Les trois assertions de la proposition se lisent
ainsi :
– On est dans la même classe d’équivalence si et seulement si on est du même âge.
– Deux personnes appartiennent soit à la même classe, soit à des classes disjointes.
– Si on choisit une personne de chaque âge possible, cela forme un ensemble de représentants C.
Maintenant une personne quelconque appartient à une et une seule classe d’un des représen-
tants.
2. Pour la relation «être parallèle», la classe d’équivalence d’une droite est l’ensemble des droites
parallèles. À chaque classe d’équivalence correspond une et une seule direction.
Voici un exemple que vous connaissez depuis longtemps :
5.4 L’ensemble Z/ nZ
Soit n 2 un entier. Définissons la relation suivante sur l’ensemble E Z :
Exemples pour n 7 : 10 ≡ 3 (mod 7), 19 ≡ 5 (mod 7), 77 ≡ 0 (mod 7), −1 ≡ 20 (mod 7).
Cette relation est bien une relation d’équivalence :
95
– Pour tout a Z, a − a 0 0 · n est un multiple de n donc a ≡ a (mod n).
– Pour a, b Z tels que a ≡ b (mod n) alors a − b est un multiple de n, autrement dit il existe k Z tel
que a − b kn et donc b − a (− k)n et ainsi b ≡ a (mod n).
– Si a ≡ b (mod n) et b ≡ c (mod n) alors il existe k, k′ Z tels que a − b kn et b − c k′ n. Alors
a − c (a − b) + (b − c) (k + k′ )n et donc a ≡ c (mod n).
La classe d’équivalence de a Z est notée a. Par définition nous avons donc
}
a cl(a) b Z | b ≡ a (mod n) .
n 0, n + 1 1, n + 2 2, . . .
Remarque. Dans beaucoup de situations de la vie courante, nous raisonnons avec les modulos. Par
exemple pour l’heure : les minutes et les secondes sont modulo 60 (après 59 minutes on repart à zéro),
les heures modulo 24 (ou modulo 12 sur le cadran à aiguilles). Les jours de la semaine sont modulo 7,
les mois modulo 12,...
5.5 Mini-exercices
2 x+ y
1. Montrer que la relation définie sur N par xR y ⇐⇒ 3 N est une relation d’équivalence. Mon-
trer qu’il y a 3 classes d’équivalence.
2. Dans R2 montrer que la relation définie par (x, y)R (x′ , y′ ) ⇐⇒ x + y′ x′ + y est une relation
d’équivalence. Montrer que deux points (x, y) et (x′ , y′ ) sont dans une même classe si et seulement
s’ils appartiennent à une même droite dont vous déterminerez la direction.
3. On définit une addition sur Z/nZ par p + q p + q. Calculer la table d’addition dans Z/6Z (c’est-
à-dire toutes les sommes p + q pour p, q Z/6Z). Même chose avec la multiplication p × q p × q.
Mêmes questions avec Z/5Z, puis Z/8Z.
Auteurs
Arnaud Bodin
Benjamin Boutin
Pascal Romon
96
Troisième partie
Les exercices
97
98
Exo7
Arithmétique dans Z
Exercice 2
Montrer que ∀n ∈ N :
n(n + 1)(n + 2)(n + 3) est divisible par 24,
n(n + 1)(n + 2)(n + 3)(n + 4) est divisible par 120
Exercice 3
Montrer que si n est un entier naturel somme de deux carrés d’entiers alors le reste de la division euclidienne
de n par 4 n’est jamais égal à 3.
Correction H Vidéo [000267]
Exercice 4
Démontrer que le nombre 7n + 1 est divisible par 8 si n est impair ; dans le cas n pair, donner le reste de sa
division par 8.
Indication H Correction H Vidéo [000254]
Exercice 5
Trouver le reste de la division par 13 du nombre 1001000 .
Indication H Correction H Vidéo [000250]
Exercice 6
1. Montrer que le reste de la division euclidienne par 8 du carré de tout nombre impair est 1.
2. Montrer de même que tout nombre pair vérifie x2 = 0 (mod 8) ou x2 = 4 (mod 8)
3. Soient a, b, c trois entiers impairs. Déterminer le reste modulo 8 de a2 +b2 +c2 et celui de 2(ab+bc+ca)
4. En déduire que ces deux nombres ne sont pas des carrés puis que ab + bc + ca non plus.
Indication H Correction H Vidéo [000285]
1
2 pgcd, ppcm, algorithme d’Euclide
Exercice 7
Calculer le pgcd des nombres suivants :
1. 126, 230.
2. 390, 720, 450.
3. 180, 606, 750.
Correction H Vidéo [000290]
Exercice 8
Déterminer les couples d’entiers naturels de pgcd 18 et de somme 360. De même avec pgcd 18 et produit 6480.
Correction H Vidéo [000292]
Exercice 9
Calculer par l’algorithme d’Euclide : pgcd(18480, 9828). En déduire une écriture de 84 comme combinaison
linéaire de 18480 et 9828.
Correction H Vidéo [000296]
Exercice 10
Notons a = 1 111 111 111 et b = 123 456 789.
1. Calculer le quotient et le reste de la division euclidienne de a par b.
2. Calculer p = pgcd(a, b).
3. Déterminer deux entiers relatifs u et v tels que au + bv = p.
Correction H Vidéo [000303]
Exercice 11
Résoudre dans Z : 1665x + 1035y = 45
Indication H Correction H Vidéo [000305]
Exercice 13
Démontrer que, si a et b sont des entiers premiers entre eux, il en est de même des entiers a + b et ab.
Indication H Correction H Vidéo [000337]
Exercice 14
Soient a, b des entiers supérieurs ou égaux à 1. Montrer :
1. (2a − 1)(2ab − 1) ;
2. 2 p − 1 premier ⇒ p premier ;
3. pgcd(2a − 1, 2b − 1) = 2pgcd(a,b) − 1.
Indication H Correction H Vidéo [000336]
Exercice 15
2
n
Soit a ∈ N tel que an + 1 soit premier, montrer que ∃k ∈ N, n = 2k Que penser de la conjecture : ∀n ∈ N, 22 + 1
est premier ?
Indication H Correction H Vidéo [000349]
Exercice 16
Soit p un nombre premier.
1. Montrer que ∀i ∈ N, 0 < i < p on a :
Exercice 17
1. Montrer par récurrence que ∀n ∈ N, ∀k > 1 on a :
( n ) k−1 n+i
− 1 = 22 − 1 × ∏ (22 + 1)
n+k
22
i=0
n
2. On pose Fn = 22 + 1. Montrer que pour m 6= n, Fn et Fm sont premiers entre eux.
3. En déduire qu’il y a une infinité de nombres premiers.
Indication H Correction H Vidéo [000341]
Exercice 18
Soit X l’ensemble des nombres premiers de la forme 4k + 3 avec k ∈ N.
1. Montrer que X est non vide.
2. Montrer que le produit de nombres de la forme 4k + 1 est encore de cette forme.
3. On suppose que X est fini et on l’écrit alors X = p1 , , pn .
Soit a = 4p1 p2 pn − 1. Montrer par l’absurde que a admet un diviseur premier de la forme 4k + 3.
4. Montrer que ceci est impossible et donc que X est infini.
Correction H Vidéo [000348]
1. Écrire n = 2p + 1.
2. Écrire n = 2p et discuter selon que p est pair ou impair.
3. Utiliser la première question.
4. Par l’absurde supposer que cela s’écrive comme un carré, par exemple a2 + b2 + c2 = n2 puis discuter
selon que n est pair ou impair.
1. Écrire
p(p − 1)(p − 2) (p − (i + 1))
Cip =
i!
4
et utiliser le lemme de Gauss ou le lemme d’Euclide.
2. Raisonner avec les modulos, c’est-à-dire prouver a p ≡ a (mod p).
5
Correction de l’exercice 1 N
La seule chose à voir est que pour une division euclidienne le reste doit être plus petit que le quotient. Donc les
divisions euclidiennes s’écrivent : 96842 = 256 × 378 + 74 et 96842 = 258 × 375 + 92.
Correction de l’exercice 2 N
Il suffit de constater que pour 4 nombres consécutifs il y a nécessairement : un diviseur de 2, un diviseur de 3,
un diviseur de 4 (tous distincts). Donc le produit de 4 nombres consécutifs est divisible par 2 × 3 × 4 = 24.
Correction de l’exercice 3 N
Ecrire n = p2 + q2 et étudier le reste de la division euclidienne de n par 4 en distinguant les différents cas de
parité de p et q.
Correction de l’exercice 4 N
Raisonnons modulo 8 :
7 ≡ −1 (mod 8)
Donc
7n + 1 ≡ (−1)n + 1 (mod 8)
Le reste de la division euclidienne de 7n + 1 par 8 est donc (−1)n + 1 donc Si n est impair alors 7n + 1 est
divisible par 8. Et si n est pair 7n + 1 n’est pas divisible par 8.
Correction de l’exercice 5 N
Il sagit de calculer 1001000 modulo 13. Tout d’abord 100 ≡ 9 (mod 13) donc 1001000 ≡ 91000 (mod 13). Or
92 ≡ 81 ≡ 3 (mod 13), 93 ≡ 92 9 ≡ 39 ≡ 1 (mod 13), Or 94 ≡ 93 9 ≡ 9 (mod 13), 95 ≡ 94 9 ≡ 99 ≡ 3
(mod 13). Donc 1001000 ≡ 91000 ≡ 93333+1 ≡ (93 )333 9 ≡ 1333 9 ≡ 9 (mod 13).
Correction de l’exercice 6 N
1. Soit n un nombre impair, alors il s’écrit n = 2p + 1 avec p ∈ N. Maintenant n2 = (2p + 1)2 = 4p2 + 4p +
1 = 4p(p + 1) + 1. Donc n2 ≡ 1 (mod 8).
2. Si n est pair alors il existe p ∈ N tel que n = 2p. Et n2 = 4p2 . Si p est pair alors p2 est pair et donc
n2 = 4p2 est divisible par 8, donc n2 ≡ 0 (mod 8). Si p est impair alors p2 est impair et donc n2 = 4p2
est divisible par 4 mais pas par 8, donc n2 ≡ 4 (mod 8).
3. Comme a est impair alors d’après la première question a2 ≡ 1 (mod 8), et de même c2 ≡ 1 (mod 8),
c2 ≡ 1 (mod 8). Donc a2 + b2 + c2 ≡ 1 + 1 + 1 ≡ 3 (mod 8). Pour l’autre reste, écrivons a = 2p + 1 et
b = 2q + 1, c = 2r + 1, alors 2ab = 2(2p + 1)(2q + 1) = 8pq + 4(p + q) + 2. Alors 2(ab + bc + ca) =
8pq + 8qr + 8pr + 8(p + q + r) + 6, donc 2(ab + bc + ca) ≡ 6 (mod 8).
4. Montrons par l’absurde que le nombre a2 + b2 + c2 n’est pas le carré d’un nombre entier. Supposons qu’il
existe n ∈ N tel que a2 + b2 + c2 = n2 . Nous savons que a2 + b2 + c2 ≡ 3 (mod 8). Si n est impair alors
n2 ≡ 1 (mod 8) et si n est pair alors n2 ≡ 0 (mod 8) ou n2 ≡ 4 (mod 8). Dans tous les cas n2 n’est pas
congru à 3 modulo 8. Donc il y a une contradiction. La conclusion est que l’hypothèse de départ est fausse
donc a2 + b2 + c2 n’est pas un carré. Le même type de raisonnement est valide pour 2(ab + bc + ca).
Pour ab + bc + ca l’argument est similaire : d’une part 2(ab + bc + ca) ≡ 6 (mod 8) et d’autre part si, par
l’absurde, on suppose ab + bc + ca = n2 alors selon la parité de n nous avons 2(ab + bc + ca) ≡ 2n2 ≡ 2
(mod 8) ou à 0 (mod 8). Dans les deux cas cela aboutit à une contradiction. Nous avons montrer que
ab + bc + ca n’est pas un carré.
Correction de l’exercice 7 N
Il s’agit ici d’utiliser la décomposition des nombres en facteurs premiers.
1. 126 = 232 7 et 230 = 2523 donc le pgcd de 126 et 230 est 2.
6
2. 390 = 23513, 720 = 24 32 5, 450 = 232 52 et donc le pgcd de ces trois nombres est 235 = 30.
3. pgcd(180, 606, 750) = 6.
Correction de l’exercice 8 N
Soient a, b deux entiers de pgcd 18 et de somme 360. Soit a′ , b′ tel que a = 18a′ et b = 18b′ . Alors a′ et b′ sont
premiers entre eux, et leur somme est 36018 = 20.
Nous pouvons facilement énumérer tous les couples d’entiers naturels (a′ , b′ ) (a′ 6 b′ ) qui vérifient cette condi-
tion, ce sont les couples :
(1, 19), (3, 17), (7, 13), (9, 11)
Pour obtenir les couples (a, b) recherchés (a 6 b), il suffit de multiplier les couples précédents par 18 :
Correction de l’exercice 9 N
1. pgcd(18480, 9828) = 84 ;
2. 25 × 18480 + (−47) × 9828 = 84.
Correction de l’exercice 10 N
1. a = 9b + 10.
2. Calculons le pgcd par l’algorithme d’Euclide. a = 9b + 10, b = 12345678 × 10 + 9, 10 = 1 × 9 + 1. Donc
le pgcd vaut 1 ;
3. Nous reprenons les équations précédentes en partant de la fin : 1 = 10 − 9, puis nous remplaçons 9 grâce
à la deuxième équation de l’algorithme d’Euclide : 1 = 10 − (b − 12345678 × 10) = −b + 1234679 ×
10. Maintenant nous remplaçons 10 grâce à la première équation : 1 = −b + 12345679(a − 9b) =
12345679a − 111111112b.
Correction de l’exercice 11 N
En divisant par 45 (qui est le pgcd de 1665, 1035, 45) nous obtenons l’équation équivalente :
Comme le pgcd de 37 et 23 est 1, alors d’après le théorème de Bézout cette équation (E) a des solutions.
L’algorithme d’Euclide pour le calcul du pgcd de 37 et 23 fourni les coefficients de Bézout : 37 × 5 + 23 ×
(−8) = 1. Une solution particulière de (E) est donc (x0 , y0 ) = (5, −8).
Nous allons maintenant trouver l’expression générale pour les solutions de l’équation (E). Soient (x, y) une
solution de l’équation 37x + 23y = 1. Comme (x0 , y0 ) est aussi solution, nous avons 37x0 + 23y0 = 1. Faisons
la différence de ces deux égalités pour obtenir 37(x − x0 ) + 23(y − y0 ) = 0. Autrement dit
On en déduit que 3723(y − y0 ), or pgcd(23, 37) = 1 donc par le lemme de Gauss, 37(y − y0 ). (C’est ici qu’il
est important d’avoir divisé par 45 dès le début !) Cela nous permet d’écrire y − y0 = 37k pour un k ∈ Z.
Repartant de l’égalité (∗) : nous obtenons 37(x − x0 ) = −23 × 37 × k. Ce qui donne x − x0 = −23k. Donc si
(x, y) est solution de (E) alors elle est de la forme : (x, y) = (x0 − 23k, y0 + 37k), avec k ∈ Z.
Réciproquement pour chaque k ∈ Z, si (x, y) est de cette forme alors c’est une solution de (E) (vérifiez-le !).
Conclusion : les solutions sont { }
(5 − 23k, −8 + 37k) k ∈ Z
7
Correction de l’exercice 12 N
Écrivons la décomposition de 15! = 1234 15 en facteurs premiers. 15! = 211 36 53 72 1113. Un diviseur de
15! s’écrit d = 2 3 5 7 11 13η avec 0 ≤ ≤ 11, 0 ≤ ≤ 6, 0 ≤ ≤ 3, 0 ≤ ≤ 2, 0 ≤ ≤ 1, 0 ≤ η ≤ 1.
De plus tout nombre d de cette forme est un diviseur de 15!. Le nombre de diviseurs est donc (11 + 1)(6 +
1)(3 + 1)(2 + 1)(1 + 1)(1 + 1) = 4032.
Correction de l’exercice 13 N
Soit a et b des entiers premiers entre eux. Raisonnons par l’absurde et supposons que ab et a + b ne sont pas
premiers entre eux. Il existe alors un nombre premier divisant ab et a + b. Par le lemme d’Euclide comme pab
alors pa ou pb. Par exemple supposons que pa. Comme pa + b alors p divise aussi (a + b) − a, donc pb.
ne divise pas b cela implique que et b sont premiers entre eux.
D’après le lemme de Gauss, comme divise ab et premier avec b alors divise a. Donc p est un facteur
premier de a et de b ce qui est absurde.
Correction de l’exercice 14 N
1. Nous savons que
xb − 1 = (x − 1)(xb−1 + · · · + x + 1),
pour x = 2a nous obtenons :
( )
2ab − 1 = (2a )b − 1 = (2a − 1) 2a(b−1) + · · · + 2a + 1
Correction de l’exercice 15 N
1. Supposons que an + 1 est premier. Nous allons montrer la contraposée. Supposons que n n’est pas de la
forme 2k , c’est-à-dire que n = p × q avec p un nombre premier > 2 et q ∈ N. Nous utilisons la formule
x p + 1 = (x + 1)(1 − x + x2 − x3 + + x p−1 )
avec x = aq :
8
Donc aq + 1 divise an + 1 et comme 1 < aq + 1 < an + 1 alors an + 1 n’est pas premier. Par contraposition
si an + 1 est premier alor n = 2k .
2. Cette conjecture est fausse, mais pas facile à vérifier sans une bonne calculette ! En effet pour n = 5 nous
obtenons :
5
22 + 1 = 4294967297 = 641 × 6700417
Correction de l’exercice 16 N
Comme Cip est un entier alors i! divise p(p − 1) (p − (i + 1)). Mais i! et p sont premiers entre eux (en
utilisant l’hypothèse 0 < i < p). Donc d’après le théorème de Gauss : i! divise (p − 1) (p − (i + 1)),
autrement dit il existe k ∈ Z tel que ki! = (p − 1) (p − (i + 1)). Maintenant nous avons Cip = pk donc
p divise Cip .
2. Il s’agit de montrer le petit théorème de Fermat : pour p premier et a ∈ N∗ , alors a p ≡ a (mod p). Fixons
p. Soit l’assertion
(Ha ) a p ≡ a (mod p)
Pour a = 1 cette assertion est vraie ! Étant donné a ≥ 1 supposons que Ha soit vraie. Alors
p
(a + 1) p = ∑ Cip ai
i=0
Mais d’après la question précédente pour 0 < i < p, p divise Cip . En termes de modulo nous obtenons :
(a + 1) p ≡ a + 1 (mod p)
Nous venons de prouver que Ha+1 est vraie. Par le principe de récurrence alors quelque soit a ∈ N∗ nous
avons :
a p ≡ a (mod p)
Correction de l’exercice 17 N
1. Fixons n et montrons la récurrence sur k ∈ N. La formule est vraie pour k = 0. Supposons la formule
vraie au rang k. Alors
k k−1
(22 − 1) × ∏ (22 + 1) = (22 − 1) × ∏ (22
n n+i n n+i n+k
+ 1) × (22 + 1)
i=0 i=0
n+k n+k n+k n+k+1
= (22 − 1) × (22 + 1) = (22 )2 − 1 = 22 − 1
Nous avons utiliser l’hypothèse de récurrence dans ces égalités. Nous avons ainsi montrer la formule au
rang k + 1. Et donc par le principe de récurrence elle est vraie.
9
2. Écrivons m = n + k, alors l’égalité précédente devient :
m−1
Fm + 2 = (22 − 1) × ∏ Fi
n
i=n
Soit encore :
m−1
∏
n
Fn × (22 − 1) × Fi − Fm = 2
i=n+1
Si d est un diviseur de Fn et Fm alors d divise 2 (ou alors on peut utiliser le théorème de Bézout). En
conséquent d = 1 ou d = 2. Mais Fn est impair donc d = 1. Nous avons montrer que tous diviseurs de Fn
et Fm est 1, cela signifie que Fn et Fm sont premiers entre eux.
3. Supposons qu’il y a un nombre fini de nombres premiers. Nous les notons alors p1 , , pN . Prenons
alors N + 1 nombres de la famille Fi , par exemple F1 , , FN+1 . Chaque Fi , i = 1, , N + 1 est divisible
par (au moins) un facteur premier p j , j = 1, , N. Nous avons N + 1 nombres Fi et seulement N facteurs
premiers p j . Donc par le principe des tiroirs il existe deux nombres distincts Fk et Fk′ (avec 1 ≤ k, k′ ≤
N + 1) qui ont un facteur premier en commun. En conséquent Fk et Fk′ ne sont pas premiers entre eux. Ce
qui contredit la question précédente. Il existe donc une infinité de nombres premiers.
Correction de l’exercice 18 N
1. X est non vide car, par exemple pour k = 2, 4k + 3 = 11 est premier.
2. (4k + 1)(4` + 1) = 16k` + 4(k + `) + 1 = 4(4k` + k + `) + 1. Si l’on note l’entier k′ = 4k` + k + ` alors
(4k + 1)(4` + 1) = 4k′ + 1, ce qui est bien de la forme voulue.
3. Remarquons que 2 est le seul nombre premier pair, les autres sont de la forme 4k + 1 ou 4k + 3. Ici a
n’est pas divisible par 2, supposons –par l’absurde– que a n’a pas de diviseur de la forme 4k + 3, alors
tous les diviseurs de a sont de la forme 4k + 1. C’est-à-dire que a s’écrit comme produit de nombre de
la forme 4k + 1, et par la question précédente a peut s’écrire a = 4k′ + 1. Donc a ≡ 1 (mod 4). Mais
comme a = 4p1 p2 pn − 1, a ≡ −1 ≡ 3 (mod 4). Nous obtenons une contradiction. Donc a admet une
diviseur premier p de la forme p = 4` + 3.
4. Dans l’ensemble X = p1 , , pn il y a tous les nombres premiers de la formes 4k + 3. Le nombre p
est premier et s’écrit p = 4` + 3 donc p est un élément de X, donc il existe i ∈ 1, , n tel que p = pi .
Raisonnons modulo p = pi : a ≡ 0 (mod p) car p divise a. D’autre part a = 4p1 pn − 1 donc a ≡ −1
(mod p). (car pi divise p1 pn ). Nous obtenons une contradiction, donc X est infini : il existe une infinité
de nombre premier de la forme 4k + 3. Petite remarque, tous les nombres de la forme 4k + 3 ne sont pas
des nombres premiers, par exemple pour k = 3, 4k + 3 = 15 n’est pas premier.
10
Exo7
1 Logique
Exercice 1
Compléter les pointillés par le connecteur logique qui s’impose : ⇔, ⇐, ⇒
1. x ∈ R x2 = 4 x = 2 ;
2. z ∈ C z = z z ∈ R ;
3. x ∈ R x = π e2ix = 1.
Correction H Vidéo [000108]
Exercice 2
Soient les quatre assertions suivantes :
Exercice 3
Dans R2 , on définit les ensembles F1 = (x, y) ∈ R2 , y ≤ 0 et F2 = (x, y) ∈ R2 , xy ≥ 1, x ≥ 0. On note
M1 M2 la distance usuelle entre deux points M1 et M2 de R2 . Évaluer les propositions suivantes :
1. ∀ε ∈]0, +∞[ ∃M1 ∈ F1 ∃M2 ∈ F2 M1 M2 < ε
2. ∃M1 ∈ F1 ∃M2 ∈ F2 ∀ε ∈]0, +∞[ M1 M2 < ε
3. ∃ε ∈]0, +∞[ ∀M1 ∈ F1 ∀M2 ∈ F2 M1 M2 < ε
4. ∀M1 ∈ F1 ∀M2 ∈ F2 ∃ε ∈]0, +∞[ M1 M2 < ε
Quand elles sont fausses, donner leur négation.
Indication H Correction H Vidéo [000109]
Exercice 4
Nier la proposition : “tous les habitants de la rue du Havre qui ont les yeux bleus gagneront au loto et prendront
leur retraite avant 50 ans”.
Correction H Vidéo [000110]
Exercice 5
Nier les assertions suivantes :
1. tout triangle rectangle possède un angle droit ;
2. dans toutes les écuries, tous les chevaux sont noirs ;
1
3. pour tout entier x, il existe un entier y tel que, pour tout entier z, la relation z < x implique le relation
z < x+1;
4. ∀ε > 0 ∃α > 0 (x − 75 < α ⇒ 5x − 7 < ε).
Correction H Vidéo [000112]
Exercice 6
Soient f , g deux fonctions de R dans R. Traduire en termes de quantificateurs les expressions suivantes :
1. f est majorée ;
2. f est bornée ;
3. f est paire ;
4. f est impaire ;
5. f ne s’annule jamais ;
6. f est périodique ;
7. f est croissante ;
8. f est strictement décroissante ;
9. f n’est pas la fonction nulle ;
10. f n’a jamais les mêmes valeurs en deux points distincts ;
11. f atteint toutes les valeurs de N ;
12. f est inférieure à g ;
13. f n’est pas inférieure à g.
Correction H Vidéo [000120]
Exercice 7
Soit f une application de R dans R. Nier, de la manière la plus précise possible, les énoncés qui suivent :
1. Pour tout x ∈ R f (x) ≤ 1.
2. L’application f est croissante.
3. L’application f est croissante et positive.
4. Il existe x ∈ R+ tel que f (x) ≤ 0.
5. Il existe x ∈ R tel que quel que soit y ∈ R, si x < y alors f (x) > f (y).
On ne demande pas de démontrer quoi que ce soit, juste d’écrire le contraire d’un énoncé.
Correction H Vidéo [000107]
Exercice 8
Montrer que
2n + 1
∀ε > 0 ∃N ∈ N tel que (n ≥ N ⇒ 2 − ε < < 2 + ε)
n+2
2 Ensembles
Exercice 9
Soit A, B deux ensembles, montrer {(A B) = {A {B et {(A B) = {A {B.
Indication H Correction H Vidéo [000123]
Exercice 10
Montrer par contraposition les assertions suivantes, E étant un ensemble :
2
1. ∀A, B ∈ P(E) (A B = A B) ⇒ A = B,
2. ∀A, B,C ∈ P(E) (A B = A C et A B = A C) ⇒ B = C.
Correction H Vidéo [000122]
Exercice 11
Soient E et F deux ensembles, f : E → F. Démontrer que :
∀A, B ∈ P(E) (A ⊂ B) ⇒ ( f (A) ⊂ f (B)),
∀A, B ∈ P(E) f (A B) ⊂ f (A) f (B),
∀A, B ∈ P(E) f (A B) = f (A) f (B),
∀A, B ∈ P(F) f −1 (A B) = f −1 (A) f −1 (B),
∀A ∈ P(F) f −1 (F \ A) = E \ f −1 (A).
Correction H Vidéo [000124]
Exercice 12
Montrez que chacun des ensembles suivants est un intervalle que vous calculerez.
+∞ [ [ +∞ [ ]
1 1 1
I= − ,2+ et J= 1+ ,n
n=1
n n n=2
n
3 Absurde et contraposée
Exercice 13
Soit ( fn )n∈N une suite d’applications de l’ensemble N dans lui-même. On définit une application f de N dans
N en posant f (n) = fn (n) + 1. Démontrer qu’il n’existe aucun p ∈ N tel que f = f p .
Indication H Correction H Vidéo [000150]
Exercice 14
1. Soit p1 , p2 , , pr , r nombres premiers. Montrer que l’entier N = p1 p2 pr + 1 n’est divisible par aucun
des entiers pi .
2. Utiliser la question précédente pour montrer par l’absurde qu’il existe une infinité de nombres premiers.
Indication H Correction H Vidéo [000151]
4 Récurrence
Exercice 15
Montrer :
n
n(n + 1)
1. ∑k= 2
∀n ∈ N∗
k=1
n
n(n + 1)(2n + 1)
2. ∑ k2 = 6
∀n ∈ N∗
k=1
Correction H Vidéo [000153]
Exercice 16
Soit X un ensemble. Pour f ∈ F (X, X), on définit f 0 = id et par récurrence pour n ∈ N f n+1 = f n ◦ f .
1. Montrer que ∀n ∈ N f n+1 = f ◦ f n .
3
2. Montrer que si f est bijective alors ∀n ∈ N ( f −1 )n = ( f n )−1 .
Indication H Correction H Vidéo [000157]
Exercice 17
2xn2 − 3
Soit la suite (xn )n∈N définie par x0 = 4 et xn+1 = .
xn + 2
1. Montrer que : ∀n ∈ N xn > 3.
2. Montrer que : ∀n ∈ N xn+1 − 3 > 32 (xn − 3).
n
3. Montrer que : ∀n ∈ N xn > 32 + 3.
4. La suite (xn )n∈N est-elle convergente ?
Indication H Correction H Vidéo [000155]
2n + 1
2−ε <
n+2
soit vraie.
5
Correction de l’exercice 1 N
1. ⇐
2. ⇔
3. ⇒
Correction de l’exercice 2 N
1. (a) est fausse. Car sa négation qui est ∀x ∈ R ∃y ∈ R x + y ≤ 0 est vraie. Étant donné x ∈ R il existe
toujours un y ∈ R tel que x + y ≤ 0, par exemple on peut prendre y = −(x + 1) et alors x + y = x − x − 1 =
−1 ≤ 0.
2. (b) est vraie, pour un x donné, on peut prendre (par exemple) y = −x + 1 et alors x + y = 1 > 0. La
négation de (b) est ∃x ∈ R ∀y ∈ R x + y ≤ 0.
3. (c) : ∀x ∈ R ∀y ∈ R x + y > 0 est fausse, par exemple x = −1, y = 0. La négation est ∃x ∈ R ∃y ∈
R x + y ≤ 0.
4. (d) est vraie, on peut prendre x = −1. La négation est : ∀x ∈ R ∃y ∈ R y2 ≤ x.
Correction de l’exercice 3 N
1. Cette proposition est vraie. En effet soit ε > 0, définissons M1 = ( ε2 , 0) ∈ F1 et M2 = ( ε2 , ε2 ) ∈ F2 , alors
M1 M2 = ε2 < ε. Ceci étant vrai quelque soit ε > 0 la proposition est donc démontrée.
2. Soit deux points fixés M1 , M2 vérifiant cette proposition, la distance d = M1 M2 est aussi petite que l’on
veut donc elle est nulle, donc M1 = M2 ; or les ensembles F1 et F2 sont disjoints. Donc la proposition est
fausse. La négation de cette proposition est :
C’est-à-dire que l’on peut trouver deux points aussi éloignés l’un de l’autre que l’on veut.
4. Cette proposition est vraie, il suffit de choisir ε = M1 M2 + 1. Elle signifie que la distance entre deux
points donnés est un nombre fini !
Correction de l’exercice 4 N
“Il existe un habitant de la rue du Havre qui a les yeux bleus, qui ne gagnera pas au loto ou qui prendra sa
retraite après 50 ans.”
Correction de l’exercice 5 N
1. “Il existe un triangle rectangle qui n’a pas d’angle droit." Bien sûr cette dernière phrase est fausse !
2. “Il existe une écurie dans laquelle il y a (au moins) un cheval dont la couleur n’est pas noire."
3. Sachant que la proposition en langage mathématique s’écrit
la négation est
∃x ∈ Z ∀y ∈ Z ∃z ∈ Z (z < x et z ≥ x + 1)
6
4. ∃ε > 0 ∀α > 0 (x − 75 < α et 5x − 7 ≥ ε)
Correction de l’exercice 6 N
1. ∃M ∈ R ∀x ∈ R f (x) ≤ M ;
2. ∃M ∈ R ∃m ∈ R ∀x ∈ R m ≤ f (x) ≤ M ;
3. ∀x ∈ R f (x) = f (−x) ;
4. ∀x ∈ R f (x) = − f (−x) ;
5. ∀x ∈ R f (x) 6= 0 ;
6. ∃a ∈ R∗ ∀x ∈ R f (x + a) = f (x) ;
7. ∀(x, y) ∈ R2 (x ≤ y ⇒ f (x) ≤ f (y)) ;
8. ∀(x, y) ∈ R2 (x < y ⇒ f (x) > f (y)) ;
9. ∃x ∈ R f (x) 6= 0 ;
10. ∀(x, y) ∈ R2 (x 6= y ⇒ f (x) 6= f (y)) ;
11. ∀n ∈ N ∃x ∈ R f (x) = n ;
12. ∀x ∈ R f (x) ≤ g(x) ;
13. ∃x ∈ R f (x) > g(x).
Correction de l’exercice 7 N
Dans ce corrigé, nous donnons une justification, ce qui n’était pas demandé.
1. Cette assertion se décompose de la manière suivante : ( Pour tout x ∈ R) ( f (x) ≤ 1). La négation de “(
Pour tout x ∈ R)" est “Il existe x ∈ R" et la négation de “( f (x) ≤ 1)" est f (x) > 1. Donc la négation de
l’assertion complète est : “Il existe x ∈ R, f (x) > 1".
2. Rappelons comment se traduit l’assertion “L’application f est croissante" : “pour tout couple de réels
(x1 , x2 ), si x1 ≤ x2 alors f (x1 ) ≤ f (x2 )". Cela se décompose en : “(pour tout couple de réels x1 et x2 )
(x1 ≤ x2 implique f (x1 ) ≤ f (x2 ))". La négation de la première partie est : “(il existe un couple de réels
(x1 , x2 ))" et la négation de la deuxième partie est : “(x1 ≤ x2 et f (x1 ) > f (x2 ))". Donc la négation de
l’assertion complète est : “Il existe x1 ∈ R et x2 ∈ R tels que x1 ≤ x2 et f (x1 ) > f (x2 )".
3. La négation est : “l’application f n’est pas croissante ou n’est pas positive". On a déjà traduit “l’applica-
tion f n’est pas croissante", traduisons “l’application f n’est pas positive" : “il existe x ∈ R, f (x) < 0".
Donc la négation de l’assertion complète est : “ Il existe x1 ∈ R et x2 ∈ R tels que x1 < x2 et f (x1 ) ≥ f (x2 ),
ou il existe x ∈ R, f (x) < 0".
4. Cette assertion se décompose de la manière suivante : “(Il existe x ∈ R+ ) ( f (x) ≤ 0)". La négation de la
première partie est : “(pour tout x ∈ R+ )", et celle de la seconde est :“( f (x) > 0)". Donc la négation de
l’assertion complète est : “Pour tout x ∈ R+ , f (x) > 0".
5. Cette assertion se décompose de la manière suivante : “(∃x ∈ R)(∀y ∈ R)(x < y ⇒ f (x) > f (y))". La
négation de la première partie est “(∀x ∈ R)", celle de la seconde est “(∃y ∈ R)", et celle de la troisième
est “(x < y et f (x) ≤ f (y))". Donc la négation de l’assertion complète est : “ ∀x ∈ R, ∃y ∈ Rtelsquex <
y et f (x) ≤ f (y)".
Correction de l’exercice 8 N
2n+1
Remarquons d’abord que pour n ∈ N, n+2 ≤ 2 car 2n + 1 ≤ 2(n + 2). Étant donné ε > 0, nous avons donc
2n + 1
∀n ∈ N < 2+ε
n+2
Maintenant nous cherchons une condition sur n pour que l’inégalité
2n + 1
2−ε <
n+2
7
soit vraie.
2n + 1
2−ε < ⇔ (2 − ε)(n + 2) < 2n + 1
n+2
⇔ 3 < ε(n + 2)
3
⇔ n > −2
ε
Ici ε nous est donné, nous prenons un N ∈ N tel que N > ε3 − 2, alors pour tout n ≥ N nous avons n ≥ N > ε3 − 2
et par conséquent : 2 − ε < 2n+1
n+2 . Conclusion : étant donné ε > 0, nous avons trouvé un N ∈ N tel que pour tout
n ≥ N on ait 2 − ε < n+2 et 2n+1
2n+1
n+2 < 2 + ε.
En fait nous venons de prouver que la limite de la suite de terme (2n + 1)(n + 2) tend vers 2 quand n tend vers
+∞.
Correction de l’exercice 9 N
x ∈ {(A B) ⇔ x ∈
AB
⇔x∈
A et x ∈
B
⇔ x ∈ {A et x ∈ {B
⇔ x ∈ {A {B
x ∈ {(A B) ⇔ x ∈
AB
⇔x∈
A ou x ∈
B
⇔ x ∈ {A ou x ∈ {
⇔ x ∈ {A {B
Correction de l’exercice 10 N
Nous allons démontrer l’assertion 1 de deux manières différentes.
1. Tout d’abord de façon “directe". Nous supposons que A et B sont tels que A B = A B. Nous devons
montrer que A = B.
Pour cela étant donné x ∈ A montrons qu’il est aussi dans B. Comme x ∈ A alors x ∈ A B donc x ∈ A B
(car A B = A B). Ainsi x ∈ B.
Maintenant nous prenons x ∈ B et le même raisonnement implique x ∈ A. Donc tout élément de A est
dans B et tout élément de B est dans A. Cela veut dire A = B.
2. Ensuite, comme demandé, nous le montrons par contraposition. Nous supposons que A 6= B et non devons
montrer que A B 6= A B.
Si A 6= B cela veut dire qu’il existe un élément x ∈ A \ B ou alors un élément x ∈ B \ A. Quitte à échanger
A et B, nous supposons qu’il existe x ∈ A \ B. Alors x ∈ A B mais x ∈ A B. Donc A B 6= A B.
Correction de l’exercice 11 N
Montrons quelques assertions.
f (A B) ⊂ f (A) f (B).
Si y ∈ f (A B), il existe x ∈ A B tel que y = f (x), or x ∈ A donc y = f (x) ∈ f (A) et de même x ∈ B donc
y ∈ f (B). D’où y ∈ f (A) f (B). Tout élément de f (A B) est un élément de f (A) f (B) donc f (A B) ⊂
f (A) f (B).
8
Remarque : l’inclusion réciproque est fausse. Exercice : trouver un contre-exemple.
f −1 (F \ A) = E \ f −1 (A).
x ∈ f −1 (F \ A) ⇔ f (x) ∈ F \ A
⇔ f (x) ∈
A
f −1 (A)
⇔x∈ car f −1 (A) = x ∈ E f (x) ∈ A
⇔ x ∈ E \ f −1 (A)
Correction de l’exercice 12 N
I = [0, 2] et J = ]1, +∞[
Correction de l’exercice 13 N
Par l’absurde, supposons qu’il existe p ∈ N tel que f = f p . Deux applications sont égales si et seulement si
elles prennent les mêmes valeurs.
∀n ∈ N f (n) = f p (n)
En particulier pour n = p, f (p) = f p (p). D’autre part la définition de f nous donne f (p) = f p (p) + 1. Nous
obtenons une contradiction car f (p) ne peut prendre deux valeurs distinctes. En conclusion, quelque soit p ∈ N,
f 6= f p .
Correction de l’exercice 14 N
1. Montrons en fait la contraposée.
S’il existe i tel que pi divise N = p1 p2 pr + 1 (i est fixé) alors il existe k ∈ Z tel que N = kpi donc
pi (k − p1 p2 pi−1 pi+1 pr ) = 1
Correction de l’exercice 15 N
Rédigeons la deuxième égalité. Soit An , n ∈ N∗ l’assertion suivante :
n
n(n + 1)(2n + 1)
(An ) ∑ k2 = 6
k=1
9
– Étant donné n ∈ N∗ supposons que An soit vraie. Alors
n+1 n
∑ k2 = ∑ k2 + (n + 1)2
k=1 k=1
n(n + 1)(2n + 1)
= + (n + 1)2
6
n(n + 1)(2n + 1) + 6(n + 1)2
=
6
(n + 1)(n(2n + 1) + 6(n + 1))
=
6
(n + 1)(n + 2)(2(n + 1) + 1)
=
6
Correction de l’exercice 16 N
1. Montrons la proposition demandée par récurrence : soit An l’assertion f n+1 = f ◦ f n . Cette assertion est
vraie pour n = 0. Pour n ∈ N supposons An vraie. Alors
Nous avons utiliser la definition de f n+2 , puis la proposition An , puis l’associativité de la composition,
puis la définition de f n+1 . Donc An+1 est vraie. Par le principe de récurrence
∀ ∈ N f n ◦ f = f ◦ f n
2. On procède de même par récurrence : soit An l’assertion ( f −1 )n = ( f n )−1 . Cette assertion est vraie pour
n = 0. Pour n ∈ N supposons An vraie. Alors
∀ ∈ N ( f −1 )n = ( f n )−1
Correction de l’exercice 17 N
1. Montrons par récurrence ∀n ∈ N xn > 3. Soit l’hypothèse de récurrence :
(Hn ) : xn > 3
10
2. Montrons que xn+1 − 3 − 32 (xn − 3) est positif.
3 2xn 2 − 3 3 1 xn 2 + 3xn + 12
xn+1 − 3 − (xn − 3) = − (xn − 3) =
2 xn + 2 2 2 xn + 2
Ce dernier terme est positif car xn > 3.
n
3. Montrons par récurrence ∀n ∈ N xn > 32 + 3. Soit notre nouvelle l’hypothèse de récurrence :
( )n
3
(Hn ) xn > + 3
2
11