MI-Université d’Antananarivo
TD d’Algèbre I- Logique et Raisonnement - Année 2024
Exercice 1. Logique
1. Vérifier à partir de la table de vérité que pour toutes assertions P, Q et R, on a:
i). [P ⇒ (Q ⇒ R)] ⇔ ((P ∧ Q) ⇒ R);
ii). (P ⇒ Q ∨ R) ⇔ (P ∧ ¬Q ⇒ R);
iii). [(P ∨ Q) ⇒ R] ⇔ ((P ⇒ R) ∧ (Q ⇒ R));
iv). Un connecteur binaire noté par, /, est dit associatif si, pour toutes assertions P, Q et R
de la théorie donnée, on a la proposition:
((P / Q) / R) ⇔ (P / (Q / R)).
Vérifier, à partir d’une table de vérité, la non-associativité du connecteur d’implication
et l’associativité du connecteur d’équivalence.
Chercher l’expression de (P ⇒ (Q ⇒ ¬R)) en fonction des seuls connecteurs ¬ et ∨.
Exercice 2. Raisonnement par récurrence:
1. Soit S un ensemble d’entiers naturels qui satisfait les deux conditions suivantes:
i). 0 appartient à S;
ii). Si n est un entier naturel tel que 1, 2, . . . , n appartiennent à S, alors n + 1 est aussi un
élément de S.
Montrer que S = N.
2. Soient n0 un entier naturel et {Pn0 +n }n∈N une famille de propositions qui satisfait les deux
conditions suivantes:
i). Pn0 est vraie;
ii). Si pour n ≥ n0 la proposition Pn est vraie, alors la proposition Pn+1 est aussi vraie.
Montrer que pour tout n ≥ n0 , la proposition Pn est vraie.
3. Soient n ∈ N? , a, b ∈ R et k ∈ {1, 2, . . . , n} . Montrer que:
a). nk + k−1n
= n+1
k .
b). [Binôme de Newton](a + b)n = nk=0 nk ak bn−k .
P
4. Soit p un nombre premier. Montrer que pour tout entier a, le nombre premier p divise ap − a.
5. Montrer que tout entier supérieur ou égal à 2 est un produit des nombres premiers. En
particulier, tout entier ≥ 2 admet un diviseur premier.
1
Exercice 3. Raisonnement par l’absurde: (P ⇒ Q) ⇔ (P ∧ ¬Q ⇒ Faux)
√ √
1. Soient x et y deux nombres rationnels tels que x et y soient irrationnels. Montrer que
√ √
x + y est irrationnel.
√
2. Monter que 2 est un nombre irrationnel. En déduire qu’il existe deux nombres irrationnels
a et b tels que ab est rationnel.
√
3. Soit q un nombre rationnel sans facteur carré. Montrer que n q est irrationnel où n est un
entier supérieur ou égal à 2.
4. Soit n un nombre composé (non premier). Montrer que n possède un diviseur premier p tel
que p2 ≤ n.
5. Montrer qu’il existe un infinité de nombres premiers.
Exercice 4. Raisonnement par contraposée: (P ⇒ Q) ⇔ (¬Q ⇒ ¬P )
1. Montrer que si n est un entier dont le carré est pair, alors n est pair.
2. Soit n un entier naturel. Montrer que si 2n − 1 est premier, le nombre n est aussi premier.
Montrer que la réciproque est fausse.
3. Montrer que si 2n + 1 est premier, alors n est un puissance de 2.
4. Soit n un entier. Montrer que si 8 ne divise pas n2 − 1, l’entier n est pair.
Exercice 5. Raisonnement par disjonction de cas:
Montrer que, pour tout entier naturel n, le nombre 61 n(n + 1)(2n + 1) est un entier.
Exercice 6. (P ⇒ Q ∨ R) ⇔ (P ∧ ¬Q ⇒ R)
Soit p un nombre entier. Montrer que p est premier si et seulement si pour tout nombre entier
a et b tels que p divise ab, on a: p divise a ou p divise b.
Problème 1.
Le but de ce problème est de démontrer le théorème de la division euclidienne qui suit:
Soient a et b deux entiers tels que b 6= 0. Il existe un unique couple d’entiers (q, r) tel que:
a = bq + r ; 0 ≤ r ≤ |b| − 1.
Considérons l’ensemble
A:= {a − bk|k ∈ Z} ∩ N.
1. Montrer que toute partie non vide de N admet un plus petit élément.
2. En déduire que A admet un plus petit élément qu’on notera par r et qu’il existe un entier q
tel que a = bq + r.
2
3. Montrer qu’on a: 0 ≤ r ≤ |b| − 1.
4. Montrer l’unicité du couple (q, r) puis conclure.
Problème 2.
Le but de ce problème est de démontrer le théorème fondamental de l’arithmétique:
Soit N un entier non nul. L’entier N peut s’écrire de manière unique sous la forme:
k
Y
N = pei i
i=1
où les pi sont des nombres premiers et les ei sont des entiers naturels avec p1 < p2 < . . . < pk .
On rappelle qu’un nombre p ≥ 2 est premier si les seuls diviseurs positifs possibles de p sont 1 et p.
1. Soit p un nombre entier. Montrer que p est premier si et seulement si p n’est pas le produit
de deux entiers plus grands que 1.
2. Supposons que N ≥ 2. Montrer que N est un produit de nombres [Link] particulier, N
admet un diviseur premier.
3. Montrer l’unicité de l’écriture.
4. Conclure.
