Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

Chapitre 1
Eléments de logique et méthodes de
démonstration

1
...
1
...
1
...
Une assertion p (ou proposition) est une phrase déclarative exclusivement vraie

ou fausse
...
1
...


p
(F) : V
F

Une table de vérité associe à l'assertion p les deux possibilités : vrai (V) ou faux

On considère les phrases suivantes :
1
...

2
...

3
...
x+y=z
...
3) et 4) ne sont pas des assertions
...
1
...


1
...
2 Connecteurs logiques élémentaires

A partir d'assertions p, q, r,
...
1
...
Soit p et q deux assertions
...
1
...
L'assertion p et q (resp
...
p ∨ q)
...
1
...


1
...
La négation de p est
l'assertion ¬p : "Au plus 99 étudiants assistent au cours d'Algèbre"
...
On considère l'assertion p : "Aujourd'hui c'est jeudi" et l'assertion q : "Il pleut aujourd'hui"
...

Remarque 1
...
7
...
Le connecteur "ou exclusif" est le connecteur, noté
p q p⊕q
V V F
V
p ⊕ q , déni par la table de vérité suivante : V F
F V V
F F F
1
...
3 Implication et équivalence
Dénition 1
...
8
...
On appelle implication de q par p l'assertion (¬p) ∨ q
...

Remarques 1
...
9
...
Sa table de vérité est la table
p q p⇒q
V V V
suivante : V F F
F V V
F F V
 L'implication p ⇒ q se lit aussi : "si p, alors q" ou "p est une condition susante pour avoir
q "
...

 L'implication q ⇒ p est appelée la réciproque de l'implication p ⇒ q
...

Exemple 1
...
10
...
l'assertion : p ⇒ q , i
...
, "Si ABC est un triangle équilatéral, alors
ABC est un triangle isocèle" est une assertion vraie
...
1
...
Soit p et q deux assertions
...
Cette assertion est notée p ⇔ q et se lit p est équivalent à q
...
1
...


1
...

p q p⇔q
V V V
Sa table de vérité est la table suivante : V F F
F V F
F F V
2
...
Une
est une assertion formée par une combinaison de plusieurs assertions
en utilisant des connecteurs logiques
...
1
...
En considérant les assertions p, q de l'exemple précédent, l'assertion : p ⇔ q, i
...
,
" ABC est un triangle équilatéral si et seulement si ABC est un triangle isocèle" est une assertion
fausse
...
1
...

 Une tautologie est une assertion composée qui est toujours vraie quelles que soient les valeurs

de vérité des assertions qui la composent
...

Exemples 1
...
15
...

1
...

2
...

En mathématique, les résultats portent les noms suivants :
 théorèmes : sont les résultats fondamentaux,
 Propositions : sont des résulats moins fondamentaux que les théorèmes
...

 Corollaires : sont des déductions des résultats précédents
...
1
...
Soit p, q et r des assertions
...
(p ∧ p) ⇔ p
...
(p ∨ p) ⇔ p
...
(p ∧ q) ⇔ (q ∧ p) (Commutativité de )
...
(p ∨ q) ⇔ (q ∨ p) (Commutativité de )
...
[(p ∧ q) ∧ r] ⇔ [p ∧ (q ∧ r)] (associativité de )
...
[(p ∨ q) ∨ r] ⇔ [p ∨ (q ∨ r)] (associativité de )
...
[p ∧ (q ∨ r)] ⇔ [(p ∧ q) ∨ (p ∧ r)] (distributivité de par rapport à )
...
[p ∨ (q ∧ r)] ⇔ [(p ∨ q) ∧ (p ∨ r)] (distributivité de par rapport à )
...
[¬(¬p)] ⇔ p
...
[¬(p ∧ q)] ⇔ [(¬p) ∨ (¬q)]
...
[¬(p ∨ q)] ⇔ [(¬p) ∧ (¬q)]
...
(p ⇒ q) ⇔ [(¬q) ⇒ (¬p)] (principe de la contraposition)
...
[(p ⇒ q) ∧ (q ⇒ r)] ⇒ (p ⇒ r) (transitivité de l'implication)
...
[(p ⇒ q) ∧ (q ⇒ r) ∧ (r ⇒ p)] ⇔ [(p ⇔ q) ∧ (q ⇔ r) ∧ (p ⇔ r)]
...
[p ∧ (p ⇒ q)] ⇒ q (principe de la déduction )
...
1
...
Au lieu de dire qu'une assertion p est vraie, on dit : "on a p"
...

Exercice 1
...
18
...

1
...

2
...

et

ou

et

ou

1
...
4 Ensembles

et

ou

ou

et

Intuitivement, on appelle ensemble une collection E d'objets
...
Généralement, on note les ensembles avec des lettres majuscules (par exemple,
E, F,
...

Soit x, y deux éléments d'un ensemble E
...

x 6= y signie [¬(x = y)]
...

x∈
/ E signie que [¬(x ∈ E)]
...
On note ∅ l'ensemble vide
...

3

1
...
5 Quanticateurs et prédicats

En mathématiques, on utilise, souvent, des expressions de la forme : "pour tout
...
", "il existe au moins
...
Ces expressions précisent comment
les éléments d'un ensemble peuvent vérier une certaine propriété
...

On distingue deux types de quanticateurs :
 Le quanticateur universel, noté ∀, se lit "quel que soit", "pour tout",
...
La notation ∃! signie "il existe un, et
un seul"
...
1
...
Soit E = {n ∈ N/n > 2}
...

L'assertion : ∀x ∈ E, x > 2 est une assertion vraie; cependant, l'assertion : ∃x ∈ E : x ≤ 2 est une
assertion fausse
...
e
...

Exemples 1
...
20
...
Soit P (x) l'expression x > 4
...

2
...

Remarque 1
...
21
...

Proposition 1
...
22
...
Alors, on a les équivalences suivantes :
1
...

2
...

3
...

4
...

Exemple 1
...
23
...

 (u ) est convergente ⇔ (∃l ∈ R) tel que (∀ > 0), (∃N ∈ N) : (∀n ∈ N)
n ≥ N ⇒ |u − l| ≤ 
...

n n∈N

n

n

n

et

n

Remarques 1
...
24
...
L'ordre des quanticateurs dans une assertion est très important
...

2
...

?

?

?

4

?

Exercice 1
...
25
...

Q(x)) l'expression "x parle l'anglais" (resp
...
En utilisant les
connecteurs logiques et les quanticateurs, écrire les expressions suivantes :
1
...

2
...

3
...

1
...

1
...
1 Démonstration directe

Une démonstration directe de p ⇒ q consiste à supposer que p est vraie et utiliser la transitivité
de l'implication pour prouver que q est vraie, i
...
, en supposant que p est vraie et si les implications
p ⇒ r , r ⇒ r ,
...
, r sont des assertions, alors q est vraie
...
2
...
Montrons que si m et n sont des entiers impairs, alors mn est un entier impair :
supposons que n et m sont des entiers impairs, alors il existe k, h ∈ Z tels que m = 2h+1 et n = 2k+1
d'où mn = (2h + 1)(2k + 1) = 2(2hk + h + k) + 1 et ainsi mn est un entier impair
...
2
...

Exemple 1
...
2
...
Montrons que
∈ N : puisque n ∈ N, alors n est pair ou n est
impair, ainsi on distingue les deux cas suivants :
= (n + 1) ∈ N
...

n(n+1)
2

n
2

n(n+1)
2

n
2
n+1
2

n(n+1)
2

n+1
2

1
...
3 Démonstration par contraposition

Puisque l'implication p ⇒ q est équivalente à ¬q ⇒ ¬p, une démonstration par contraposition de
p ⇒ q consiste à donner une démonstration directe de ¬q ⇒ ¬p
...
2
...
√Soit m, n ∈ N
...


1
...
4 Démonstration par contre-exemple

Si l'assertion est : "tout élément d'un ensemble E vérie la proriété P ", l'existence d'un seul
élément de E qui ne vérie pas P montre que l'assertion est fausse
...
2
...
Soit E = {n ∈ N/n > 1}
...

Exercice 1
...
5
...
Donner un contre-exemple pour montrer que les assertions [(∀x ∈ E, P (x)) ∨ (∀x ∈ E, Q(x))]
et [∀x ∈ E, (P (x) ∨ Q(x)] ne sont pas équivalentes
...
Donner un contre-exemple pour montrer que les assertions [(∃x ∈ E, P (x)) ∧ (∃x ∈ E, Q(x))]
et [∃x ∈ E, (P (x) ∧ Q(x)] ne sont pas équivalentes
...
2
...
Ainsi, pour montrer, par l'absurde, l'implication q ⇒ r,
on suppose que r est fausse et que q est vraie (i
...
, q ⇒ r est fausse) et on montre que l'on aboutit à
une contradiction
...
2
...


1
...
e
...

2
...
Montrons par l'absurde que si 3n + 2 est impair, alors n est impair :
supposons alors que n est pair et que 3n + 2 est impair; puisque n est pair, 3n + 2 est pair et
on obtient ainsi que 3n + 2 est pair et 3n + 2 est impair, contradiction
...
2
...
Il est composé de
deux étapes :
1
...

2
...

Exemple 1
...
7
...
Montrons que f est la somme d'une fonction paire
et d'une fonction impaire :
1
...

2
...
e
...

On conclut qu'il existe un unique couple (g, h) tel que f = g + h, avec g paire et h impaire
...
Ces objets s'appellent
les éléments de l'ensemble E
...

2
...
1
...
1
...
On dit que F est inclus dans E ou que F

est une partie de E si tout élément de
F est élément de E
...

On écrit F ⊂ E ou encore E ⊃ F
...
1
...
l'ensemble des parties de E est noté P(E) , i
...
, P(E) = {A/A ⊂ E}
...
1
...


 A ∈ P(E) si, et seulement si, A ⊂ E si, et seulement si, ∀x ∈ A, x ∈ E
...

 Si A, B et C sont des parties de E, alors :
 A ⊂ B ⇔ ∀x ∈ E, (x ∈ A ⇒ x ∈ B)
...

 A = B ⇔ A ⊂ B et B ⊂ A
...

Exemple 2
...
4
...
Alors, P(E) = {∅, {a}, {b}, E}
...
1
...

 L'intersection

de E et F , notée E ∩ F , est l'ensemble déni par E ∩ F := {x/x ∈ E et
 La réunion de E et F , notée E ∪ F , est l'ensemble déni par E ∪ F := {x/x ∈ E ou x ∈ F }
...

 Si F ⊂ E, l'ensemble E \ F est appelé complémentaire de F dans E et est noté {
...

x ∈ F}


...
1
...


 Si E ∩ F = ∅, on dit que E et F sont

...

 Si A et B sont deux parties de E, alors A \ B = A ∩ B, où B = {
...
1
...
Soit E = {x ∈ R/|x| ≤ 1} et F = {x ∈ R/|x + 1| ≤ 1}
...

7
disjoints

B
E

on a :
 E ∩ F ⊂ E et E ∩ F ⊂ F
...

 E ∩ F = F ∩ E (commutativité de l'intersection)
...

 E ∩ (F ∩ G) = (E ∩ F ) ∩ G (associativité de l'intersection)
...

 E ∩ ∅ = ∅ (l'ensemble vide est absorbant pour l'intersection)
...

 E ∩ E = E et E ∪ E = E
...

 E ∩ (F ∪ G) = (E ∩ F ) ∪ (E ∩ G) (l'intersection est distributive par rapport à la réunion)
...

Proposition 2
...
9
...

 A = A
...

 A ∪ B = A ∩ B
...
1
...
Soit A et B deux parties de E
...
Vérier que
1
...

2
...

3
...

4
...

Propriétés 2
...
8
...
1
...
1
...

 Le produit cartésien de deux ensembles E et F

est l'ensemble noté E × F := {(x, y)/x ∈ E
et y ∈ F }
...

 Plus généralemet, si E ,
...
, x )/∀i ∈
{1,
...
L'ensemble E × E × · · · × E est noté aussi
E et (x ,
...

Si E = · · · = E , on note E × E × · · · × E = E × E × · · · × E = E
...
1
...
On considère les deux ensembles suivants : E = {a, b} et F = {1, 2}, alors E ×F =
{(a, 1), (a, 2), (b, 1), (b, 2)} et E = {(a, a), (a, b), (b, a), (b, b)}
...
2

Applications

2
...
1 Dénitions
Dénition 2
...
1
...

Si (x, y) est un élément de Γ, y est appeleé une image de x par f et x est dit un antécédent de y
par f
...

Γ est appelé le graphe de f
...
2
...


 si f = (E, F, Γ) est une correspondance, on écrit x f y si (x, y) ∈ Γ
...
La correspondance f est notée aussi E → F
...
2
...
Soit f : R → R, x 7→ y, avec y est un réel tel que y = x
...
Cependant, si x ∈ R , x n'a
pas d'image
...
2
...
Soit f : E → F une correspondance
...
e
...

Si y = f (x), y est dit l'image de x par f et on dit aussi que x est un antécédent de y
...
2
...


1
...

2
...

3
...

4
...


5
...
L'application χ : E → {0, 1}, x 7→ 10 sisi xx ∈∈/ AA est appelée
(ou
) de A
...
2
...


 Soit f : E → F et g : G → H deux applications
...

 Soit A une partie de E et f : E → F une application
...

 Soit G un ensemble contenant E et f : E → F une application
...

Notation 2
...
7
...

A

restriction

A

prolongement

E

2
...
2 Composition des applications
Proposition et Dénition 2
...
8
...
L'application de
E vers G qui à tout élément x de E associe l'élément g(f (x)) de G est appelée composée de f et g et
est notée g ◦ f , i
...
, g ◦ f est l'application g ◦ f : E → G, x 7→ g ◦ f (x) = g(f (x))
...
2
...
Soit f : R → R , x 7→ x + 1 et g : R → R, x 7→ x, alors g ◦ f : R → R, x 7→
√
x + 1
...
2
...
si f : E → F , g : F → G et h : G → H sont des applications, alors
h ◦ (g ◦ f ) = (h ◦ g) ◦ f (◦ est associative)
...
2
...
La composition des applications n'est pas commutative, en eet, soit E est un
ensemble contenant deux éléments a et b distincts, f, g ∈ E telles que f (a) = b, f (b) = a et g(a) =
b, g(b) = b, alors g ◦ f (a) = b tandis que f ◦ g(a) = a
...
2
...
Soit A et B deux parties de E
...
A ⊂ B si, et seulement si, χ ≤ χ
...
A = B si, et seulement si, χ = χ
...

9
+

2

+

2

E

2
A

A

A

B

A

B

4
...
χ = 1 − χ , où 1 : E → {0, 1}, x 7→ 1
...

7
...

8
...
2
...
Soit E et F deux ensembles nis
...

A∩B

A B
A

A

A∪B

A

A\B

A

B

B

A

A4B
E

A B

B

n

2
...
3 Familles
Dénition 2
...
14
...
Une famille d'éléments de E indexée par I est une application

f : I → E, i 7→ f (i) = xi


...

i i∈I

Exemples 2
...
15
...
Une suite (u ) réelle est une famille de nombres réels indexée par N
...
Si I = {1,
...
, x ), où x ∈ E, ∀i ∈ I
...
2
...
Lorsque I est ni, on dit que (x ) est une famille nie
...
2
...

une famille de parties de E indexée par I
...

 la partie T E = {x ∈ E/∀i ∈ I, x ∈ E } est appelée intersection de la famille (E )
...
2
...
Si A est une partie de E et (E ) une famille de parties de E indexée par I ,
on peut vérier
facilement que :
 A ∪ ( S E ) = S (A ∪ E )
...

 A ∩ ( S E ) = S (A ∩ E )
...

n n∈N

1

n

i

i i∈I

i i∈I

i

i

i

i

i i∈I

i∈I

i i∈I

i∈I

i i∈I

i

i

i∈I

i∈I

i

i

i∈I

i∈I

i

i

i∈I

i∈I

i

i

i∈I

i∈I

2
...
4 Partition
Dénitions 2
...
19
...

 On dit que (E ) est une partition de E si elle vérie les propriétés suivantes :
i) ∀i ∈ I, E 6= ∅
...

S
iii) E = E
...
On dit que (E )
E , i
...
, ∀x ∈ A, ∃i ∈ I : x ∈ E
...
2
...
Une partition de E est un recouvrement de E
...
2
...


1
...

2
...
Alors, la famille (A ) , où A = {x}, est une partition de E
...
La famille (A ) , où A = {0,
...

10
1

+

?−

2

1

2

x x∈E

n n∈N

n

x

n n∈N

2
...
5 Image directe et image réciproque
Dénitions 2
...
22
...
L'ensemble des éléments
de F admettant un antécédent par f dans A, noté f (A), est appelé image de A par f , i
...
, f (A) =
{y ∈ F/∃x ∈ A, f (x) = y} = {f (x)/x ∈ A}

image de f
...
En particulier, si A = E, f (E), noté aussi Imf , est dit

Soit f = sin : R → R, x 7→ sin(x) ; alors Imf = [−1, 1] et f ([0, ]) = [0, 1]
...
2
...
Soit A, B deux parties de E et f : E → F une application
...

 Si A ⊂ B, alors f (A) ⊂ f (B)
...
Plus généralement, si (E ) est une famille de parties de E, alors
f( E ) =
f (E )
...
Plus généralement, si (E ) est une famille de parties de E, alors
f( E ) ⊂
f (E )
...
2
...
Soit f : E → F une application et B une partie de F
...
e
...

Exemple 2
...
26
...

Propriétés 2
...
27
...

 f (∅) = ∅
...

 Si A ⊂ B, alors f (A) ⊂ f (B)
...
Plus généralement, si (E ) est une famille de parties de
E , alors f ( E ) =
f (E )
...
Plus généralement, si (E ) est une famille de parties de
f (E )
...
2
...


π
2

i i∈I

i

i

i∈I

i∈I

i i∈I

i

i

i∈I

i∈I

−1

−1

−1

2

?−

−1

−1

−1

−1

−1

−1

−1

−1

−1

i∈I

−1

i

i∈I

−1

−1

i i∈I

−1

i

−1

i

i∈I

i i∈I

−1

i

i∈I

2
...
6 Injections, surjections et bijections
Dénitions 2
...
28
...

 On dit que f est surjective (ou une surjection) si tout élément de F

admet un antécédent,
i
...
, ∀y ∈ F, ∃x ∈ E : f (x) = y
...
e
...

 On dit que f est bijective (ou une bijection) si f est à la fois surjective et injective (i
...
, f
est une surjection et une injection)
...
2
...


1
...

2
...

3
...
L'application i : A → E, x 7→ x est une application injective appelée
de A dans E
...

Remarque 2
...
30
...
f est surjective si, et seulement si, Imf = F
...
2
...


 La composée de deux injections est une injection
...

 La composée de deux bijections est une bijection
...
2
...
Soit f : E → F et g : F → G deux applications
...

 Si g ◦ f est surjective, alors g est surjective
...
2
...
Soit f : E → F une bijection
...
e
...

Proposition 2
...
34
...

Proposition 2
...
35
...
Si f ◦ g = id et g ◦ f = id ,
alors f et g sont bijectives, g = f et f = g
...
2
...


 Si f : E → F est bijective, alors f est bijective et (f ) = f
...

−1

−1

−1

−1 −1

−1

Exemples 2
...
37
...
Soit a ∈ R et b ∈ R
...

2
...

?

−1

x−b
a

?+

2
...
3
...
3
...
Une relation binaire R sur E

est une correspondance de E vers E, i
...
, R =
, où Γ est une partie de E × E
...
3
...
Soit R sur E et x, y ∈ E
...

Exemple 2
...
3
...

Dénitions 2
...
4
...

 On dit que la relation R est réexive si pour tout x ∈ E, xRx
...

 On dit que la relation R est transitive si pour tout x, y, z ∈ E, si xRy et yRz, alors xRz
...

 On dit que la relation R est ue relation d'équivalence si R est réexive, symétrique et transitive
...

Exemples 2
...
5
...
Alors,
 R est réexive, antisymétrique et transitive, mais non symétrique
...

 R n'est ni réexive, ni symétrique, et R est antisymétrique
...

 R est une relation d'équivalece et R n'est pas antisymétrique
...

 Soit a ∈ E
...

 L'ensemble des classes d'équivalence modulo R, noté E/R, est appelé ensemble quotient de
E par R ou simplement ensemble quotient, i
...
, E/R = {a/a ∈ E}
...
3
...
Soit x, y ∈ R et R la relation dénie sur R par xRy si x = y
...

Remarque 2
...
8
...
L'application s : E → E/R, x 7→ x est
une surjection appelée la

...
3
...
Soit x, y ∈ E et R une relation d'équivalence sur E
...
xRy
...
x = y
...
x ∩ y 6= ∅
...
3
...
Soit n ∈ N \ {0, 1}, x, y ∈ Z et R la relation dénie sur Z par xRy si n divise
x − y
...
, n − 1}
...
Aussi, au lieu décrire xRy,
on écrit x ≡ y ( mod n) et on dit que x est congru à y modulo n
...

Dénitions 2
...
6
...
3
...


 Si R une relation déquivalence sur E, alors la famille (x) forme une partition de E
 Réciproquement, si une famille (A ) de parties de E, où I est un ensemble, est une partition
de E, alors la relation R dénie sur E par xRy s'il existe i ∈ I : x, y ∈ A est une relation
d'équivalence sur E
...
3
...
(
) Si f : E → F est une application, alors :
 La relation R dénie sur E par xRy si f (x) = f (y), où x, y ∈ E, est une relation d'équivalence
...
s : E → E/R) est l'injection canonique (resp
...

La décomposition f = i ◦ f ◦ s est appelée
f
...
3
...
Soit f : R → R, x 7→ x
...

x∈E/R

i i∈I

i

Décomposition canonique d'une application

la décomposition canonique de

2

+

2

+

2
...
2 Relations d'ordre
Dénitions et exemples
Dénition 2
...
14
...
On dit que R est une relation d'ordre (ou

un ordre) sur E si R est réexive, antisymétrique et transitive
...
3
...
Soit R une relation d'ordre sur E et x, y ∈ E
...

Remarques 2
...
16
...

 Soit (E, ) un ensemble ordonné
...

13
ensemble ordonné

 Une relation binaire dans E qui est réexive et transitive et dite un

préordre

sur E
...
3
...


1
...

2
...

3
...
Alors (N , |) est un ensemble ordonné
...
Dans Z, | n'est pas une relation d'ordre; | est un préordre sur Z
...
Dans C, la relation R dénie par zRz si |z| ≤ |z | est un préordre
...
3
...
Soit R un préordre dans E
...
Montrer que S est une relation d'équivalence
...
3
...
Soit  un ordre dans E
...
e
...

 Si l'ordre  n'est pas total, on dit que  est un ordre partiel
...
3
...


1
...

2
...

3
...

?

Eléments remarquables
Dénitions 2
...
21
...


et m deux éléments de

 On dit que M est un majorant de A dans E si ∀x ∈ A, x  M
...

 On dit que A est majorée (resp
...
minorant)
dans E
...

 On dit que m est un plus petit élément de A si
i) m ∈ A
ii) ∀x ∈ A, m  x
...
3
...
Soit (E, ) un ensemble ordonné
...
un plus petit élément)
...
3
...


1
...
Aussi, la partie A = {2, 6, 10} est minorée dans N (par exemple, 2 est un minorant
de A dans N
...
Dans (N , |), 2 est le plus petit élément de A = {2, 6, 10}
...
Dans (P(E), ⊂), si X, Y ∈ P(E), la partie A = {X, Y } est minorée et majorée dans P(E)
(X ∩ Y (resp
...
un majorant) de A dans P(E))
...
La partie A =]0, 1[ de R ordonné par l'ordre usuel est une partie majorée et minorée de R, mais
A n'admet ni un plus grand élément ni un plus petit élément
...
3
...
Soit (E, ) un ensemble ordonné et A une partie de E
...

ii) Soit M ∈ E
...

 La borne inférieure de A dans E, si elle existe, est l'élément, noté inf A (ou inf A) vériant :
i) inf A est un minorant de A dans E
...
Si m est un minorant de A dans E, alors m  inf A
...
3
...
Soit (E, ) un ensemble ordonné et A une partie de E
...

 inf A est le plus grand élément, lorsqu'il existe, de l'ensemble des minorants de A dans E
...
3
...


1
...

2
...

Dénitions 2
...
27
...

 On dit que M est un élément maximal de A si ∀x ∈ A, (M  x ⇒ x = M )
...

?

Exemples 2
...
28
...
Dans (N , |), on considère A = {2, 3, 4, 5, 6, 7, 8, 9}, alors, 5, 6, 7, 8, 9 sont des éléments maximaux de A et 2, 3, 5 et 7 sont des éléments minimaux de A
...
Dans (N , |), on considère A = N \{1}, alors les nombres premiers sont des éléments minimaux
de A
...
1

Z

Ensemble des entiers naturels

3
...
1 Dénitions

On admet l'existence d'un ensemble ordonné non vide (N, ≤) vériant les trois propriétés suivantes :
i) Toute partie non vide de N possède un plus petit élément
...

iii) N n'a pas de plus grand élément
...
1
...


 L'ensemble N est totalement ordonné
...

 0 est le plus petit élément de N
...

 Si n ∈ N, n + 1 est appelé successeur de n
...

Théorème 3
...
2
...

?

?

?

Propriété d'archimède

3
...
2 Raisonnement par récurrence
Théorème 3
...
3
...
Si
1
...
Pour tout entier n ≥ n , si P (n) est vraie, alors P (n + 1) est vraie,
alors Pour tout entier n ≥ n , P (n) est vraie
...
1
...

1
...

2
...

Théorème 3
...
5
...
Si
1
...
Pour tout entier n ≥ n , P (n) et P (n + 1) sont vraies implique P (n + 2) est vraie,
alors Pour tout entier n ≥ n , P (n) est vraie
...
1
...
Soit (u ) la suite réelle dénie par u = 2, u = 5 et pour tout entier n ≥ 0,
u
= 5u
− 6u
...

Théorème 3
...
7
...
Si
1
...
Pour tout entier n ≥ n , si pour tout entier k tel que n ≤ k ≤ n, P (k) est vraie implique
P (n + 1) est vraie,
alors Pour tout entier n ≥ n , P (n) est vraie
...
1
...
Soit n un entier naturel non nul
...

n

n+2

n+1

0

1

n

n

n

(Récurrence forte)

n

0

0

0

0

0

k

3
...
2
...


Z

tel que a = bq + r, avec 0 ≤ r < |b|
...
2
...

N×N

tel que a = bq + r, avec 0 ≤ r < b
...


le reste

(Thóerème de la division euclidienne dans

,

N) ∀(a, b) ∈ N × N? ∃!(q, r) ∈

Exemples 3
...
3
...
Pour a = 2015 et b = 15, on a q = [ ] = 134 et r = a − bq = 5
...
Pour a = −2016 et b = 67, on a q = [ ] = −31 et r = a − bq = 61
...
2
...
Soit a, b ∈ Z
...
Lorsque a
divise b, on écrit a | b
...
2
...
Soit a, b ∈ Z
...

Propriétés 3
...
6
...

i) a | 0 et si 0 |b, alors b = 0
...

iii) a | b et b | a si, et seulement si, a = ±b
...

v) Si a | b et b | c, alors a | c
...

vii) Si a | b et a | c ; alors pour tout (x, y) ∈ Z, a | bx + cy
...
2
...
La relation de divisibilité dans Z est réexive et transitive mais n'est pas antisymétrique
...
3

Pgcd et Ppcm

− {(0, 0)}
...


Théorème et Dénition 3
...
1
...
d est noté a ∧ b ou

...
3
...


1
...

2
...
e
...

Théorème 3
...
3
...
d = a ∧ b si, et seulement si,
i) d | a et d | b,
ii) Si c est un entier tel que c | a et c | b, alors c | d
...
3
...
Soit (a, b) ∈ Z − {(0, 0)}
...

Théorème 3
...
5
...
a et b sont premiers entre eux
si, et seulement si, il existe x, y ∈ Z tels que 1 = ax + by
...
3
...
Soit (a, b) ∈ Z − {(0, 0)}
...

Corollaire 3
...
7
...
Si a ∧ b = 1, alors ab | c
...
3
...
(
) Soit a, b, c ∈ Z tels que a | bc
...

2

2

1

1

n−1

n

n

2

(Théorème de Bézout)

a
d

b
d

Lemme de Gauss

3
...
4
...
Soit a ∈ Z, b ∈ Z?
...

Algorithme 3
...
2
...
Puisque a ∧ b = |a| ∧ |b|, on peut

supposer que 0 < b ≤ a
...
Si r = 0, alors a ∧ b = b
...
Si r = 0, alors a ∧ b = b ∧ r = r
...
On obtient ainsi :
a = bq + r , avec 0 ≤ r < b
b = q r + r , avec 0 ≤ r < r
r = q r + r , avec 0 ≤ r < r

...

Exemple 3
...
3
...
360 + 288, 360 = 288
...
4 ainsi 1008 ∧ 360 = 72
...
4
...

Soit a et b deux entiers et d = a ∧ b
...
e
...

Exemple 3
...
5
...
1 = 360 − (1008 − 2
...
1008 + 3
...

18
1

1

2

n−1

n

n

(Algorithme d'Euclide étendu)

n

n−2

n n−1

n−2

1

n−3

Corollaire 3
...
6
...

Théorème et Dénition 3
...
7
...
Il existe un unique entier positif m tel que

i) a | m et b | m,
ii) Si c est un entier tel que a divise c et b divise c, alors m divise c
...
m est noté a ∨ b ou
m = ppcm(a, b)
...
4
...
On vérie que si a, b et c sont des entiers non nuls, alors (a ∨ b) ∨ c = a ∨ (b ∨ c)
et ainsi on peut généraliser, par récurrence, à un nombre ni quelconque d'entiers non nuls, i
...
,
a ∨ · · · ∨ a = (a ∨ · · · ∨ a
)∨a
...
4
...
Soit a, b, c ∈ Z − {0}
...

Exercice 3
...
10
...
Alors ab ∨ ac = |a|(b ∨ c)
...
5

n

1

n−1

n

Nombres premiers

Soit p > 1 un entier
...
Un entier > 1 qui n'est pas premier est dit composé
...
5
...
Soit a, b ∈ Z et p un nombre premier
...

Corollaire 3
...
3
...

1
...
, a ∈ Z
...
a , alors il existe k ∈ {1,
...

2
...
, p des nombres premiers
...
p , alors il existe k ∈ {1,
...

Théorème 3
...
4
...
p , avec pour tout i = 1,
...

Théorème 3
...
5
...

Exercice √3
...
6
...

Dénition 3
...
1
...
6

Congruences

Soit n ∈ N
...
La relation a ≡ b ( mod n) est appelée congruence modulo
Remarque 3
...
2
...
Si n = 1, la relation
a ≡ b ( mod n) est vraie pour tout (a, b) ∈ Z
...

Théorème 3
...
3
...
La relation a ≡ b ( mod n) dénie sur Z est une relation
d'équivalence
...
6
...


note a ≡ b (
n
...
6
...


1
...

2
...
, n − 1}, i
...
, si x ∈ Z/nZ, ∃!a ∈ x tel que a ∈ {0, 1
...

Théorème 3
...
5
...

1
...
Si a ≡ b ( mod n) et a ≡ b ( mod n), alors a a ≡ b b ( mod n) (
mod n
Z)
19
n

1

1
1
de la congruence
1

1

congruence

2

2

2

1

2

2
1
avec l'addition dans
2

1 2

avec la multiplication dans

2

1

1 2

2

Compatibilité

Compatibilité de la

3
...

 Multiplication : Soit x, y ∈ Z/nZ, on dénit x
...

Théorème 3
...
1
...
Cet anneau admet 0 pour élément nul et 1 pour unité
...
7
...
La correspondance f : {0, 1,
...

Théorème 3
...
3
...

Théorème 3
...
4
...
Si p ne divise
pas a, alors a ≡ 1( mod p)
...
7
...
Si p est un nombre premier, alors pour tout a ∈ Z, a ≡ a( mod p)
...
7
...
Soit n > 1 un entier, a, b, c ∈ Z
...
Montrer que si a ≡ b ( mod n), alors a ≡ b ( mod n), pour tout entier k > 0
...
On suppose que a, b et c sont non nuls
...

(Petit théorème de Fermat)

p−1

p

k

k

n
d

3
...
, n − 1}
tels que k ∧ n = 1, i
...
, ϕ(n) = card{k ∈ {0, 1,
...
L'application ϕ est appelée la
fonction indicatrice d'Euler ou l'indicateur d'Euler et ϕ(n) est dit indicateur d'Euler de n
...
8
...
On a ϕ(1) = 1, ϕ(2) = 1, ϕ(10) = 4
...
8
...
Si p est un nombre premier et k > 0 est un entier, alors ϕ(p ) = p − p
...
8
...
Soit a, b, c ∈ N
...

Théorème 3
...
5
...
Si m et n sont premiers entre eux, alors ϕ(mn) =
ϕ(m)ϕ(n)
...
8
...
Soit n > 1 un entier et n = p
...
, p des nombres premiers et
k ,
...
(p − p
) = n(1 − )
...

Exemple 3
...
7
...

Dénition 3
...
1

---